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?