The Student Room Group
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>

Need help with a mod problem

Show that 1/1 + 1/2 + 1/3 + 1/4 +1/5 +1/6 ... 1/p-1 = 1 + 2 + 3 + 4 + 5 + 6 + ... + p-1 (modp)

Help please!!

When i asked my friend he said "it's obvious" because each non zero integer (modp) is equivalent to the reciprocal of one and only one non-zero integer (modp), but I don't get why that is the case.
(edited 9 years ago)
Original post by CancerousProblem
Show that 1/1 + 1/2 + 1/3 + 1/4 +1/5 +1/6 ... 1/p-1 = 1 + 2 + 3 + 4 + 5 + 6 + ... + p-1 (modp)

Help please!!

When i asked my friend he said "it's obvious" because each non zero integer (modp) is equivalent to the reciprocal of one and only one non-zero integer (modp), but I don't get why that is the case.


Pick a prime e.g. 7 then find 1−1,2−1,...,(p−1)−1(1^{-1},2^{-1},...,(p-1)^{-1} (mod pp) what can you see about the inverses? Can you apply this more generally?

Or pick a non-prime e.g. 6 what is 3−1mod63^{-1} mod 6? Why does this happen?
Original post by tombayes
Pick a prime e.g. 7 then find 1−1,2−1,...,(p−1)−1(1^{-1},2^{-1},...,(p-1)^{-1} (mod pp) what can you see about the inverses? Can you apply this more generally?

Or pick a non-prime e.g. 6 what is 3−1mod63^{-1} mod 6? Why does this happen?


I can see the inverses are a rearrangement of 1, 2 ,3 4... (p-1) but I can't see any reason this should be the case for any prime p.

Also I have no idea what you mean by 3^-1 mod6, is that even valid? That makes no sense...
thanks for helping, but I still don't get it
Original post by CancerousProblem

Also I have no idea what you mean by 3^-1 mod6, is that even valid? That makes no sense...


Exactly that is why is it important for p to be prime.

For the prime case: can you see how the numbers are being rearranged?
no... i don't see why the numbers would be just rearrangements, even though every prime i've checked that appears to be the case. How do I show it applies to all primes?
bump
Original post by CancerousProblem
bump


Another hint: use the fact that n−1n^{-1}mod p prime is unique (i.e. no two inverses are the same) for n<p;n∈Nn<p; n \in \mathbb{N}
Original post by tombayes
(i.e. no two inverses are the same)

that's exactly what my friend told me but i have no idea why its true. I can see why if its true it will imply my original question, but i have no idea why it's true. Can you explain why it's true to me? This problem has been disturbing me all day. I wanted to do some C4 past papers today but I came across this in a book and it's been bugging me for 2 hours now before i gave up.
Original post by CancerousProblem
that's exactly what my friend told me but i have no idea why its true. I can see why if its true it will imply my original question, but i have no idea why it's true. Can you explain why it's true to me? This problem has been disturbing me all day. I wanted to do some C4 past papers today but I came across this in a book and it's been bugging me for 2 hours now before i gave up.


Pick a p prime and
Suppose there exists a positive integer n,(n≠0)n, (n\ne0) with a non-unique inverse mod p i.e. there exists two integers x,y<px,y < p such that xn=1xn=1 & yn=1 yn=1 modp p. Then xn−yn=0xn-yn=0 mod p p this implies x−y=0x-y=0 or n=0n=0 however we already said that nn was a positive integer so n≠0n\ne 0 therefore x−y=0  ⟹  x=yx-y=0 \implies x=y i.e. inverses are unique.

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you