Proving Invertible Elements in Algebraic Structure of Zn

[soulflyfgm]

For Zn = { 0, 1 ,...,n-1}, the algebraic structure (Zn, +, . ) is a "ring", i.e., it has nearly all of the usual properties of addition and multiplication that we use unconsciously most of the time(where the opertaions are defined by performing them in Z and then recording the remainder on division by n). In Z, of course, the only invertible elements with respect to multiplication (a for which there is some b such that ab = 1), are +-1. PRove that the invertible elements with respect to multiplication in Zn are exactly those elements a such that a and n are relatively priime; that is , gcd{a,n}=1

can some one give me a hint on wat to do in this problem? i woud really apriciate it!

 

[AKG]

What do you know about gcd? Are you familiar with Euclid's algorithm? If not, look it up on Wikipedia.

 

[soulflyfgm]

yes

yes i know wat it is and i also know how to solve it.. but i don't see how am i suppost to use the euc alg to solve this problem.
any hint?
thank u

 

[Hurkyl]

Do you know the algebraic characterization of the GCD? IMHO, it is much more useful than the one involving divisibility.

 

[matt grime]

the euclidean algorithm states that if a and n are coprime there are integers x and y such that "SOMETHING THAT GIVES AWAY THE ANSWER"

if you do know the Euclidean algorithm then the answer is obvious, surely?