Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Algebraic structure

  1. Nov 20, 2005 #1
    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. jcsd
  3. Nov 20, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    What do you know about gcd? Are you familiar with Euclid's algorithm? If not, look it up on Wikipedia.
  4. Nov 20, 2005 #3

    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
  5. Nov 20, 2005 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do you know the algebraic characterization of the GCD? IMHO, it is much more useful than the one involving divisibility.
  6. Nov 20, 2005 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook