Homework Help: Algebraic structure

1. Nov 20, 2005

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

2. Nov 20, 2005

AKG

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

3. Nov 20, 2005

soulflyfgm

yes

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

4. Nov 20, 2005

Hurkyl

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

5. Nov 20, 2005

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?