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?
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?