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

**matzerath** · January 30th 2010, 04:55 AM

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)

**Sudharaka** · January 30th 2010, 05:45 AM

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.

**Unbeatable0** · January 30th 2010, 06:53 AM

There's a short way to prove this.
$x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\<img src=$ 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)$

**matzerath** · January 31st 2010, 03:02 AM

Originally Posted by Unbeatable0

There's a short way to prove this.
$x\equiv y \pmod{a} \Leftrightarrow x=y+ka\:\<img src=$ 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!

**Sudharaka** · January 31st 2010, 05:08 PM

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.

**matzerath** · February 7th 2010, 05:05 AM

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!

Thread: x≡y (mod a) => (x,a)=(y,a)

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

a ≡ b ?

Give a proof of ⊢ A ≡ B ≡ (A ∧ B) ∨ (¬A ∧ ¬B)

a^p≡1 (mod p^n) iff a≡1 (mod p^(n-1)), n≥2

lcm of k,k+1,k+2 where k≡3(mod 4)

x^n ≡ 3 (mod 4) only if x ≡ n ≡ 1 (mod 2)

Search Tags