Fermat's little theorem question: why isn't $a^p \equiv 1$?

Question

Fermat's little theorem says that $a^p \equiv a \pmod p$.

I have kind of a stupid question. Since $p \equiv 0\pmod p $, why isn't $a^p \equiv a^0 \equiv 1 \pmod p$ ?

Answer 1

You can't take the modulo of the exponent like that. Think of $a^p$ as $\underbrace{a*a*\dots*a}_{p\text{ times}}$. If it was $p*a$ then what you did would be justified, but not with exponents. A full proof of Fermat's little theorem is off-topic, but this should answer your question!

--

Edit to answer OP's comment on the original post:

When in doubt you can always go back what $a = b \text{ (mod n)}$ means.

$$ \begin{align} a = b \text{ (mod n)} \text{ is equivalent to } a = b + k * n \text{ for some } k \in \mathbb{Z} \end{align} $$

From that it is easy to show that $n * a = 0 \text{ (mod n)}$:

$$ \begin{align} n * a = b + k * n &\implies 0 = b + (k + a) * n\\ &\implies 0 = b \text{ (mod n)} \end{align} $$

But you can't do the same with $a^n$.

Answer 2

While $x\equiv y\pmod p$ implies $a+x\equiv a+y\pmod p$ as well as $a\cdot x\equiv b\cdot y\pmod p$ (and even $x^a\equiv y^a\pmod p$), it does not imply $a^x\equiv a^y\pmod p$.

Answer 3

As an intuitive counter example, Fermat's Little theorem in this form holds for all integers including zero. So $0^p \equiv 1 \mod p$ clearly does not work. If you are familiar with fields, you should realize you're staring at the additive identity, which we exclude from consideration in the multiplicative set.

A different question that should get you thinking about this: for any non-zero integer $a$ and prime $p$ then $a^{p-1} \equiv 1 \mod p$. For any integer $a$ and prime $p$ then $a^p \equiv a \mod p$. Find out how they are equivalent (hint: zero is the problem again).

Answer 4

Modular arithmetic does not work that way. You cannot simply replace every occurence of $ p $ with $ 0 $ when working modulo $ p $.

The idea behind modular arithmetic is to take a set of elements (an ideal) in $ \mathbb{Z} $ and treat them as they are equal to 0. (I am being very loose with the terminology and the notions here, formalizing them requires some abstract algebra.) It turns out that the sets with which you can do this are sets which contain all integers divisible by some number $ n $, and we denote this set by $ n\mathbb{Z} $. Then, we define the set $ \mathbb{Z}/n\mathbb{Z} $ as the set of all "shifted copies" of $ n\mathbb{Z} $ in the integers.

To fully understand what this means, let's consider the case $n = 3 $. Then, $$3\mathbb{Z} = \{ \ldots, -6, -3, 0, 3, 6, \ldots \} $$ and we see that this set has three shifted copies in $ \mathbb{Z} $:

$$3\mathbb{Z} + 0 = \{ \ldots, -6, -3, 0, 3, 6, \ldots \} $$ $$3\mathbb{Z} + 1 = \{ \ldots, -5, -2, 1, 4, 7, \ldots \} $$ $$3\mathbb{Z} + 2 = \{ \ldots, -4, -1, 2, 5, 8, \ldots \} $$

Note that, for example, $3\mathbb{Z} + 3 $ is the same set as $ 3\mathbb{Z}$. So, $ \mathbb{Z}/3\mathbb{Z} = \{ 3\mathbb{Z}, 3\mathbb{Z} + 1, 3\mathbb{Z} + 2 \} $, which we may simply write as $ \{0, 1, 2\} $ if the context is clear. We then define addition and multiplication as follows:

$$ (a + n\mathbb{Z}) + (b + n\mathbb{Z}) = a + b + n\mathbb{Z} $$ $$ (a + n\mathbb{Z})(b + n\mathbb{Z}) = ab + n\mathbb{Z} $$

(One checks that these are well defined.) Now, for example working in $\mathbb{Z}/7\mathbb{Z}$, we have that $$ (2 + 7\mathbb{Z})(5 + 7\mathbb{Z}) = 10 + 7\mathbb{Z} = 3 + 7\mathbb{Z} $$

which is actually the same thing as saying $ 2\cdot 5 \equiv 3 \pmod{7} $.

Now, we are ready to explain why exactly the logic in the OP does not work. The problem is that when we talk about $ x^p $ modulo p, we are really talking about $ (x + p\mathbb{Z})^p = x^p + p\mathbb{Z}$. The base is a member of our structure $ \mathbb{Z}/p\mathbb{Z} $ where we have defined addition and multiplication, but the exponent is only telling us to multiply $ x + p\mathbb{Z} $ with itself $ p $ times. $ p $ is an integer and not a member of $ \mathbb{Z}/p\mathbb{Z} $, and for integers, the equality $ p = 0 $ is clearly not true. So, while $ p + p\mathbb{Z} = p\mathbb{Z} $, we do not have that $ p = 0 $.