# Thread: Coprimes and modulus problem

1. ## Coprimes and modulus problem

I have the following problem:

Prove: If GCD(a,n)=1, then there exists an integer b such that GCD(b, n)=1, and ab {is congruent to} 1 (mod n)

Yes its my math homework, but ive been staring at it for three hours, and i even talked to my professor about it and just cant seem to get anywhere. Im limited to certain thechniques and theorems, which i think excludes the euclidean algorithm. She suggested i start with the theorem that states that if GCD(a,n)=b, then b=as+nt, with n and t being integers, and b being he smallest number that can be expressed this way, but i just cant seem to get any useful information out of that knowledge.

Can anyone help me in any way? hints? somewhere to start?

2. ## Re: Coprimes and modulus problem

use the fact that gcd(a,n) = 1 means there are integers r,s such that ar + ns = 1. what happens if you take this equation modulo n?

3. ## Re: Coprimes and modulus problem

Originally Posted by Deveno
use the fact that gcd(a,n) = 1 means there are integers r,s such that ar + ns = 1. what happens if you take this equation modulo n?
do you get that
ar mod n = 1 and thus n|ar-1

i can see how this relates to the second conclusion, but i still dont see where im going to get that b from

4. ## Re: Coprimes and modulus problem

what does that tell you about r (mod n)?

5. ## Re: Coprimes and modulus problem

Originally Posted by Deveno
what does that tell you about r (mod n)?
hmmm...
lets see i know n does not divide a, so a mod n = a...
does that mean r equals kn+1? for some integer k?
so n|r-1
so r mod n = 1?

6. ## Re: Coprimes and modulus problem

and thus would mean gcd(r, n) =1?

7. ## Re: Coprimes and modulus problem

no, you're barking up the wrong tree.

if ar + ns = 1, then

ar (mod n) + ns (mod n) = 1 (mod n).

now, what is ns (mod n)?

is it true that ar (mod n) = (a mod n)(r mod n)?

8. ## Re: Coprimes and modulus problem

Originally Posted by Deveno
now, what is ns (mod n)?

is it true that ar (mod n) = (a mod n)(r mod n)?
I thought ns (mod) n = 0, so it cancels out.

and i thought it was true.

so going back ar mod n = 1

(a mod n) + (r mod n) = 1

since n does not divide a, a mod n = a

a + (r mod n) = 1?

...so r mod n = 1 - a?

9. ## Re: Coprimes and modulus problem

why are you adding (a mod n) and (r mod n) rather than multiplying them?