GCD=1 with Congruence

• Feb 20th 2007, 07:56 PM
GCD=1 with Congruence
Let a,b,c,n be integers with n>1. If gcd(a,n)=1, ab congruences ac (mod n).

Prove b congruence c (mod n).

My proof so far:

Now I have ai + nj = 1 and ab = ac+ne for integers i,j,e.

Then I need something like b = c + nv for an integer v.

How do I go for that?

Thanks.

KK
• Feb 21st 2007, 07:41 AM
ThePerfectHacker
Quote:

Let a,b,c,n be integers with n>1. If gcd(a,n)=1, ab congruences ac (mod n).

Prove b congruence c (mod n).

My proof so far:

Now I have ai + nj = 1 and ab = ac+ne for integers i,j,e.

Then I need something like b = c + nv for an integer v.

How do I go for that?

Thanks.

KK

I am sure you learn this in class.

Theorem
Let the integers be positive then,
ac=bc (mod n)
Then
a = b (mod n/d) where d=gcd(n,c)

Thus, in the special case of relative primeness we have d=1.
Simple.
• Feb 21st 2007, 07:49 AM
N0, I have not learn this theorem in class yet.

Is there a proof somewhere in the web?

KK
• Feb 21st 2007, 11:32 AM
ThePerfectHacker
Quote:

N0, I have not learn this theorem in class yet.

Is there a proof somewhere in the web?

KK

Use Euclid's Lemma (assuming you proved it in class).

Theorem Given positive integers, if a|(bc) and gcd(a,b)=1 then a|c.

Proof I leave it as an excerise for you to prove, if you did not.

Corollary If ac=bc (mod n) and gcd(c,n)=1 then a=b (mod n). Given positive integers.

Proof By definition n|(ac-bc) then n|c(a-b) but gcd(c,n)=1 thus we have n|(a-b) by Euclid's Lemma. Thus, by definition a=b (mod n).