Fermat vs Euler

Fermat's little theorem states that for prime p p , we have a p 1 1 ( m o d p ) a^{p-1} \equiv 1\ (\mathrm{mod}\;p) ( p ∤ a ) . (p\not\mid a). Here is a proof:

  1. Consider 1 , 2 , , p 1 1,2,\ldots,p-1 and a , 2 a , , ( p 1 ) a . a,2a,\ldots,(p-1)a.
  2. They are permutations of each other under m o d p . \mathrm{mod}\;p.
  3. 1 2 ( p 1 ) a 2 a ( p 1 ) a ( m o d p ) . 1\cdot 2\cdots (p-1)\equiv a\cdot 2a \cdots (p-1)a \;(\mathrm{mod}\;p).
  4. Cancellation: 1 a p 1 ( m o d p ) . 1\equiv a^{p-1}\;(\mathrm{mod}\;p).

However, when we are talking about a composite number n n , we have a ϕ ( n ) 1 ( m o d n ) a^{\phi(n)} \equiv 1\ (\mathrm{mod}\;n) for coprime integers a a and n n instead, from Euler's theorem .

If I use the above proof flow for the Euler's theorem, in which step do I first make a mistake?

1 2 3 4

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Alex Spagnoletti
Apr 24, 2016

In the 4th point we divide both part by 1 , 2 , . . . ( p 1 ) 1, 2, ... (p-1) and this is ok seen that they are coprime with p. But when we work with n n they are not coprime so I can't divide.

Arjen Vreugdenhil
Apr 26, 2016

If n n is composite, both sides of the equation contain a factor zero (mod p p ). The cancellation law only works if the canceled factor is unequal to zero.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...