Number theory problem

[martinosorio]

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?

 

[lookagain]

I have the following problem:

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

martinosorio,

did you mean "a and b such that GCD(a, b) = 1,...?"

 

[martinosorio]

martinosorio,

did you mean "a and b such that GCD(a, b) = 1,...?"

Sorry about that, i fixed it, i meant "then there exists an integer b such that GCD(b, n)=1"