# Math Help - x≡y (mod a) => (x,a)=(y,a)

1. ## x≡y (mod a) => (x,a)=(y,a)

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)

2. Dear matzerath,

Suppose, $d_1=(x,a)$ and $d_2=(y,a)$

$x\equiv{y(mod a)}\Rightarrow{a}\mid{x-y}$

Therefore, $d_1\mid{a}$ and $a\mid{x-y}\Rightarrow{d_1\mid{x-y}}$

$d_1\mid{x-y}$ and $d_1\mid{x}\Rightarrow{d_1\mid{y}}$

$d_1$ is a common divisor of y and a

Therefore, $d_1\leq{d_2}$--------(1)

Similarly, $d_2$ is a common divisor of x and a

Therefore, $d_2\leq{d_1}$---------(2)

From (1) and (2),

$d_1=d_2\Rightarrow{(x,a)=(y,b)}$

Hope this helps.

3. There's a short way to prove this.
$x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\k\in \mathbb{Z})" alt="x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\k\in \mathbb{Z})" />
Thus, using the fact that $\gcd(m,n)=\gcd(m+rn,n)$ for all $r\in \mathbb{Z}$, it follows that

$\gcd(x,a)=\gcd(y+ka,a)=\gcd(y,a)$

4. Originally Posted by Unbeatable0
There's a short way to prove this.
$x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\k\in \mathbb{Z})" alt="x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\k\in \mathbb{Z})" />
Thus, using the fact that $\gcd(m,n)=\gcd(m+rn,n)$ for all $r\in \mathbb{Z}$, it follows that

$\gcd(x,a)=\gcd(y+ka,a)=\gcd(y,a)$

how would one prove the last thing? I've seen it before but I've never seen the proof...

and by the last thing I mean $\gcd(y+ka,a)=\gcd(y,a)$

Yeah, and thanks to both of you!

5. Dear matzerath,

Suppose, $(y+ka,a) = d_1$ and $(y,a) = d_2$ for $k\in{Z}$

Since, $(y+ka,a) = d_1$

$d_1\mid{y+ka}$ and $d_1\mid{a}$

Therefore, $d_1\mid{y}$ and $d_1\mid{a}$

$d_1\leq{d_2}$--------(1)

Also since, $d_2=(y,a)$

$d_2\mid{y}$ and $d_2\mid{a}$

Therefore, $d_2\mid{y+ka}$ and $d_2\mid{a}$

$d_2\leq{d_1}$---------(2)

By (1) and (2); $d_1=d_2\Rightarrow{(y+ka,a)=(y,a)}$

Hope this helps.

6. Originally Posted by Sudharaka
Dear matzerath,

Suppose, $(y+ka,a) = d_1$ and $(y,a) = d_2$ for $k\in{Z}$

Since, $(y+ka,a) = d_1$

$d_1\mid{y+ka}$ and $d_1\mid{a}$

Therefore, $d_1\mid{y}$ and $d_1\mid{a}$

$d_1\leq{d_2}$--------(1)

Also since, $d_2=(y,a)$

$d_2\mid{y}$ and $d_2\mid{a}$

Therefore, $d_2\mid{y+ka}$ and $d_2\mid{a}$

$d_2\leq{d_1}$---------(2)

By (1) and (2); $d_1=d_2\Rightarrow{(y+ka,a)=(y,a)}$

Hope this helps.

next time I'll think befor asking a question... but thank you!

>, mod, x≡y