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