Looking at the following one would think it is simple, and mabye it is, BUT to me it is impossible and has been so for two days.
So, show that if x≡y (mod a) then (x,a)=(y,a)
Dear matzerath,
Suppose, $\displaystyle d_1=(x,a)$ and $\displaystyle d_2=(y,a)$
$\displaystyle x\equiv{y(mod a)}\Rightarrow{a}\mid{x-y}$
Therefore, $\displaystyle d_1\mid{a}$ and $\displaystyle a\mid{x-y}\Rightarrow{d_1\mid{x-y}}$
$\displaystyle d_1\mid{x-y}$ and $\displaystyle d_1\mid{x}\Rightarrow{d_1\mid{y}}$
$\displaystyle d_1$ is a common divisor of y and a
Therefore, $\displaystyle d_1\leq{d_2}$--------(1)
Similarly, $\displaystyle d_2$ is a common divisor of x and a
Therefore, $\displaystyle d_2\leq{d_1}$---------(2)
From (1) and (2),
$\displaystyle d_1=d_2\Rightarrow{(x,a)=(y,b)}$
Hope this helps.
There's a short way to prove this.
$\displaystyle x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\k\in \mathbb{Z})$
Thus, using the fact that $\displaystyle \gcd(m,n)=\gcd(m+rn,n)$ for all $\displaystyle r\in \mathbb{Z}$, it follows that
$\displaystyle \gcd(x,a)=\gcd(y+ka,a)=\gcd(y,a)$
Dear matzerath,
Suppose, $\displaystyle (y+ka,a) = d_1$ and $\displaystyle (y,a) = d_2$ for $\displaystyle k\in{Z}$
Since, $\displaystyle (y+ka,a) = d_1$
$\displaystyle d_1\mid{y+ka}$ and $\displaystyle d_1\mid{a}$
Therefore, $\displaystyle d_1\mid{y}$ and $\displaystyle d_1\mid{a}$
$\displaystyle d_1\leq{d_2}$--------(1)
Also since, $\displaystyle d_2=(y,a)$
$\displaystyle d_2\mid{y}$ and $\displaystyle d_2\mid{a}$
Therefore, $\displaystyle d_2\mid{y+ka}$ and $\displaystyle d_2\mid{a}$
$\displaystyle d_2\leq{d_1}$---------(2)
By (1) and (2); $\displaystyle d_1=d_2\Rightarrow{(y+ka,a)=(y,a)}$
Hope this helps.