Integers mod p

  • Thread starter gazzo
  • Start date
175
0
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
 
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]
 

matt grime

Science Advisor
Homework Helper
9,394
3
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.
 
175
0
hehe that's true :) thanks.
 

matt grime

Science Advisor
Homework Helper
9,394
3
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.
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top