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

Integers mod p

  1. Jul 20, 2005 #1
    Hey, umm... I can't find an answer for this anywhere.

    if we have a group [itex]\mathbb{Z}/p\mathbb{Z}[/itex] (for sufficient p) under multiplication modulo p, is divsion defined

    [tex]\frac{a}{b} = ab^{-1}[/tex]

    ie in [itex]\mathbb{Z}/5\mathbb{Z} = \{1,2,3,4\}[/itex]; would [itex]\frac{3}{2}[/itex] be [itex](3)(2^{-1}) \equiv (3)(3) \equiv 4[/itex]

    Maybe i've completely understood modulo arithmetic
  2. jcsd
  3. Jul 20, 2005 #2
    Seems alright to me.

    By the way, the multiplicative group of integers modulo p is usually denoted by [tex](\mathbb{Z}/p\mathbb{Z})^*[/tex] and is defined as the set of elements of [tex]\mathbb{Z}/p\mathbb{Z}[/tex] which have an inverse under multiplication. [tex]\mathbb{Z}/p\mathbb{Z}[/tex] is a group only under addition. So:

    [tex]\mathbb{Z}/5\mathbb{Z} = \{0,1,2,3,4\} [/tex] and [tex](\mathbb{Z}/5\mathbb{Z})^*=\{1,2,3,4\}[/tex]

    [tex]\mathbb{Z}/9\mathbb{Z} = \{0,1,2,3,4,5,6,7,8\} [/tex] and [tex](\mathbb{Z}/9\mathbb{Z})^*=\{1,2,4,5,7,8\}[/tex]
  4. Jul 20, 2005 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    inverses of all non-zero elements are defined for ALL p when p is a prime. and only for elements coprime to p when p is not a prime (actually this implies they all are invertible if p is a prime).

    i would never say anything like "i completely understand SUBJECT" since there is always someone cleverer than you who understands more about it.
  5. Jul 20, 2005 #4
    hehe that's true :) thanks.
  6. Jul 20, 2005 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    if you'd like to put your knowledge to the test then how abhout this:

    let p be a prime and work mod p.

    show that x^2=1 mod p has exactly two solutions.

    hence show that (p-1)!=-1 mod p

    hint: every element x has a unique y such that xy=1, paur them up. what can you not pair with a distinct inverse? see previous question).

    show that pCr (p choose r) is 0 mod p unless r=1 or p (when it is 1)

    if you know group theory explain why a^{p-1}=1 mod p. if you don't know group theory, use the previous exercise to show it by considering (1+1+..+1)^p {a 1's added together} to show why.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook