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
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).