Let $a,b,c\in\mathbb Z^+$. If $a\equiv b\pmod c$ then $\gcd(a,c)=\gcd(b,c)$. Use this to show that there are no $ x, y $ such that $ x + y = 100 $ and $ (x, y) = 3 $.
Since $a\equiv b\pmod c$, then $a=b+ck$ with $k\in\mathbb Z$. Let $d=\gcd(a,c)$, then exists $x,y\in\Bbb Z^+$ such that $$\begin{align*} d&=ax+cy\\ &=(b+ck)x+cy\\ &=bx+ckx+cy\\ &=bx+c(kx+y)\\ &=bx+cz. \end{align*}$$ This shows that $ d = \gcd(b, c) $. Is my proofcorrect? And how do I use this for the particular result. Thanks a lot.
A slight rephrase:
Let $d$ be any common divisor of $a$ and $c$, then consider $b = a-ck$ with $k\in\mathbb Z$, $d$ is a divisor of the right hand side, so $d\mid b$.
i.e. All common divisors of $a$ and $c$ are also divisors of $b$, and hence are common divisors of $b$ and $c$.
Similarly, by considering $a=b+ck$, all common divisors of $b$ and $c$ are also common divisors of $a$ and $c$.
So the set of common divisors of $a$ and $c$ is the same as the set of common divisors of $b$ and $c$. The greatest elements of the two sets are also the same.