2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ $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. $\endgroup$ – dxiv Nov 26 '16 at 6:43
  • 1
    $\begingroup$ 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. $\endgroup$ – Anurag A Nov 26 '16 at 6:43
  • 2
    $\begingroup$ Yes, this is exactly what it means. Your interpretation of it is correct. $\endgroup$ – barak manos Nov 26 '16 at 8:15
  • 1
    $\begingroup$ $a^p\equiv a\pmod{p}$ is just another way of saying $a^p\bmod p=a\bmod p$. $\endgroup$ – barak manos Nov 26 '16 at 8:16
2
$\begingroup$

$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$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.