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)

Printable View

- January 30th 2010, 05:55 AMmatzerathx≡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) - January 30th 2010, 06:45 AMSudharaka
Dear matzerath,

Suppose, and

Therefore, and

and

is a common divisor of y and a

Therefore, --------(1)

Similarly, is a common divisor of x and a

Therefore, ---------(2)

From (1) and (2),

Hope this helps. - January 30th 2010, 07:53 AMUnbeatable0
There's a short way to prove this.

Thus, using the fact that for all , it follows that

- January 31st 2010, 04:02 AMmatzerath
- January 31st 2010, 06:08 PMSudharaka
Dear matzerath,

Suppose, and for

Since,

and

Therefore, and

--------(1)

Also since,

and

Therefore, and

---------(2)

By (1) and (2);

Hope this helps. - February 7th 2010, 06:05 AMmatzerath