fermat’s little theorem and euler’s generalization of fermats theorem

1. supose p is prime and that α has order 3 modulo p. what is the order of α+1? (you need to solve this for all pais (α,p) that satisfy the conditions of the problem.

2. Suppose p is a prime and that 2 and 3 are both primitive roots(modp). Prove that 4 and 6 are both not primitive roots(modp). (you must prove this for every p such that 2 and 3 are the primitive roots(mod p)- and there are probably infinitely many such p). Is it possible that 5 is also a primitive root(mod p).

3. find with proof, all n such that Φ(n) divides 25 n

## Expert Answer

**Fermat’s Little Theorem.**- Let
*p*be a prime which does not divide the integer*a*, then*a*^{p-1}= 1 (mod*p*).

It is so easy to calculate *a*^{p-1} that most elementary primality tests are built using a version of Fermat’s Little Theorem rather than Wilson’s Theorem.

As usual Fermat did not provide a proof (this time saying “I would send you the demonstration, if I did not fear its being too long” [Burton80, p79]). Euler first published a proof in 1736, but Leibniz left virtually the same proof in an unpublished manuscript from sometime before 1683.

**Proof.**- Start by listing the first
*p*-1 positive multiples of*a*:*a*, 2*a*, 3*a*, … (*p*-1)*a*Suppose that

*ra*and*sa*are the same modulo*p*, then we have*r*=*s*(mod*p*), so the*p*-1 multiples of*a*above are distinct and nonzero; that is, they must be congruent to 1, 2, 3, …,*p*-1 in some order. Multiply all these congruences together and we find*a*^{.}2*a*^{.}3*a*^{.}…^{.}(*p*-1)*a*= 1^{.}2^{.}3^{.}…^{.}(*p*-1) (mod*p*)or better,

*a*^{(p-1)}(*p*-1)! = (*p*-1)! (mod*p*). Divide both side by (*p*-1)! to complete the proof.