I am trying to write a proof that shows that $\gcd(4,10)≠1$ using only the definition of gcd below.
$$\gcd(a,b) = \min(\{k∈\mathbb N : k = ax + by \text{ for some } x,y ∈ \mathbb Z\}) $$
Here is what I have so far:
By the definition,
Let $S$ be the set where $\gcd(4,10) = \min(\{k∈\mathbb N : k = 4x + 10y \text{ for some }x,y∈\mathbb Z\}).$
I am trying to prove that $\gcd(4,10)=2$ by proving that $\gcd(4,10)\ne1$ and that $2∈S$. I am doing this because $1∈\mathbb N$ and $1$ is the smallest value of $\mathbb N$. If $1$ is not an element of the set $S$, and $2$ is an element of the set, then $2$ is the minimum value of the set because it is the smallest element of $\mathbb N$ possible. And so, $\gcd(4,10) = 2$. I can prove that $2∈S$ by simply plugging in $4x+10y=2$ with $x=-2$ and $y=1$.
So, I need to prove first that $1≠\gcd(4,10)$. To do so, I am trying to show that $1$ is not an element of the set $S$, since $1≠4x+10y$ where both $x$ and $y$ are integers.
(This is where I am, stuck I am not sure how to prove $1≠4x+10y$ properly).
To prove $1≠4x+10y$, I have some ideas that I came up with so far.
All integer multiples of $4$ and $10$ will result in an even number and $1$ is odd. I don't this is enough though, because I would then have to somehow prove that multiples of $4$ and $10$ are all even. I also have the idea that the smallest integers are $0,1,-1$, and inputting them into $4x+10y$ will not give $1$.
I am looking for a stronger way to prove that $\gcd(4,10)≠1$ by only using the set $S$. Any suggestions or solutions would really help me out a lot.
Best Answer
Hint: All elements of $S$ are even: $4x+10y=2(2x+5y)=2z$.