# Congruences, Fermat's Theorem, Wilson's Theorem - General Questions

• Oct 14th 2012, 06:42 PM
ncshields
Congruences, Fermat's Theorem, Wilson's Theorem - General Questions
Here are several problems that I have been trying to work on but have not gotten very far. Any thoughts?

1) Suppose that p is an odd prime. Show that 1^(p-1) + 2^(p-1) + ... + (p-1)^(p-1) is congruent to -1 (mod p).

2) Verify that sigma(p^n) - p^n = ((p^n) - 1)/(p-1) for n = 1,2,...

3)In assignment 4, we showed that Z_m - {0} = {1,2,...,m-1} is not always a group under multiplication modulo m. Write Z*_m for the set of all elements in Z_m which have a multiplicative inverse in Z_m.
(a) Prove that a in Z*_m if and only if (a; m) = 1. Conclude that Z*_m has exactly phi(m) elements.
(b) Verify that Z*_m is a group under multiplication modulo m. Conclude that a phi(m)= 1 for a in Z*_m.
• Oct 14th 2012, 09:41 PM
MaxJasper
Re: Congruences, Fermat's Theorem, Wilson's Theorem - General Questions
1)
Using Fermat's Little Theorem:

$\displaystyle 1^{p-1}+2^{p-1}+\cdots +(p-1)^{p-1}\equiv 1+1+\cdots +1=p-1\equiv -1 (\text{mod} p)$
• Oct 26th 2012, 03:35 AM
Salahuddin559
Re: Congruences, Fermat's Theorem, Wilson's Theorem - General Questions
Quote:

Originally Posted by ncshields
Here are several problems that I have been trying to work on but have not gotten very far. Any thoughts?

1) Suppose that p is an odd prime. Show that 1^(p-1) + 2^(p-1) + ... + (p-1)^(p-1) is congruent to -1 (mod p).

2) Verify that sigma(p^n) - p^n = ((p^n) - 1)/(p-1) for n = 1,2,...

3)In assignment 4, we showed that Z_m - {0} = {1,2,...,m-1} is not always a group under multiplication modulo m. Write Z*_m for the set of all elements in Z_m which have a multiplicative inverse in Z_m.
(a) Prove that a in Z*_m if and only if (a; m) = 1. Conclude that Z*_m has exactly phi(m) elements.
(b) Verify that Z*_m is a group under multiplication modulo m. Conclude that a phi(m)= 1 for a in Z*_m.

Your problem 2 looks like a general series summation to me, nothing specific to p being a prime. Please clarify Sigma(p^n) notation here. Is it summation on n, from 0 to say N?

Salahuddin
Maths online