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

• Jan 30th 2010, 04:55 AM
matzerath
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)
• Jan 30th 2010, 05:45 AM
Sudharaka
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.
• Jan 30th 2010, 06:53 AM
Unbeatable0
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)$
• Jan 31st 2010, 03:02 AM
matzerath
Quote:

Originally Posted by Unbeatable0
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)$

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 $\displaystyle \gcd(y+ka,a)=\gcd(y,a)$

Yeah, and thanks to both of you!
• Jan 31st 2010, 05:08 PM
Sudharaka
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.
• Feb 7th 2010, 05:05 AM
matzerath
Quote:

Originally Posted by Sudharaka
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.

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