Fermat's Little Theorem definition clarification.

Fermat's Little Theorem states that (acc to Gallian book)

$a^p \mod p= a \mod p$.

Does it mean that we get the same remainder when both $a^p$ and $a$ are divided by some prime $p$? I am quite confused about this statement. Through wikipedia, I read $a^p \equiv a \mod p$. Kindly help. I am new to this number system topic.

• $a \bmod p = b \bmod p \;\iff\; a \equiv b \pmod p$. Mind the difference between the notations. See for example Notation for modulo: congruence relation vs operator. – dxiv Nov 26 '16 at 6:43
• The two statements are equivalent. Two numbers are congruent if and only if they belong to the same equivalence class, hence will have the same remainder. – Anurag A Nov 26 '16 at 6:43
• Yes, this is exactly what it means. Your interpretation of it is correct. – barak manos Nov 26 '16 at 8:15
• $a^p\equiv a\pmod{p}$ is just another way of saying $a^p\bmod p=a\bmod p$. – barak manos Nov 26 '16 at 8:16

$a^p\mod p\equiv a \mod p\implies a^p-a\equiv 0 \mod p \implies p\text{divides} (a^p-a)\implies a^p-a=kp\implies a^p=kp+a$

So what is the remainder when $a^p$ is divided by $p$

• Definitely a < p. Why? – dxiv Nov 26 '16 at 6:55
• p could be less than a, as long as p is prime. – Linfeng Li Nov 26 '16 at 7:05
• Could be but not necessarily. – Vidyanshu Mishra Nov 26 '16 at 7:09
• Yes right;I edited it@dxiv – Learnmore Nov 26 '16 at 7:10

As you already know that fermet's little theorem states that $a^p \mod p= a \mod p$. It is equivalent to $p|(a^p)-a$ or simply $(a^p)-a=pk$ for some integer $k$.

Now your question is that:

Does it mean that we get the same remainder when both $a^p$ and a are divided by some prime p??

My answer is Yes.

Consider an example : As 6 divides 30, we can say that 6|35-5, but notice that 6 neither divide $35$ nor $5$,but $6$ divides $35-5$ because $5$ and $35$ give remainder $5$ when they are divided by $6$.

I shall let you conclude from here.