11
$\begingroup$

4 and 9 are relatively prime, but $4^8$ = 65536, which is not $1 \mod 9$. I can't figure out why because I've been told that $a^{p-1}$ is equivalent to $1 \mod p$ if $p$ and $a$ are relatively prime...so...what am I missing?

$\endgroup$
  • $\begingroup$ Yes, I know, Fermat $\endgroup$ – Nethesis Aug 3 '14 at 21:10
  • 2
    $\begingroup$ $\varphi(9)$ is not $8$ but is $6.$ $\endgroup$ – coffeemath Aug 3 '14 at 21:14
  • 1
    $\begingroup$ You do need $\gcd(a, p) = 1$ but you also need for $p$ to be either prime OR a pseudoprime to base $a$. As it happens, 4 is a pseudoprime to base 9: verify that $9^3 \equiv 1 \mod 4$. $\endgroup$ – Robert Soupe Aug 4 '14 at 5:33
15
$\begingroup$

You can't apply Fermat's theorem: $$a^{p-1} \equiv 1 \pmod p$$

because $9$ is not a prime. However,you can use Euler's theorem:

$$a^{\phi(m)} \equiv 1 \pmod m$$

$$a=4$$

$$m=9$$

$$(a,m)=1$$

$$\phi(9)=\phi(3^2)=3^2 \left (1-\frac{1}{3} \right )=9 \frac{2}{3}=6$$

Therefore:

$$4^6 \equiv 1 \pmod 9$$

$\endgroup$
  • 2
    $\begingroup$ Ok then, I guess the textbook is wrong, it says it applies if p is prime or a and p are coprime $\endgroup$ – Nethesis Aug 3 '14 at 21:17
  • 3
    $\begingroup$ @Nethesis That should be and a and $p$ are coprime. Must be a typo $\endgroup$ – Mathmo123 Aug 3 '14 at 21:19
  • 1
    $\begingroup$ I'm sorry, I don't understand the difference between a and $a$... $\endgroup$ – Nethesis Aug 3 '14 at 21:20
  • 4
    $\begingroup$ @Nethesis You can only apply the Ferma'ts theorem if $p$ is a prime AND $(a,p)=1$. $\endgroup$ – evinda Aug 3 '14 at 21:23
  • 3
    $\begingroup$ Ohh, thank you, the book did not phrase it in that way at all, thank you $\endgroup$ – Nethesis Aug 3 '14 at 21:24
7
$\begingroup$

Fermat's Little Theorem is true only if $p$ is prime - the statement is $$a^p \equiv a \mod p$$ for $p$ prime. When $(a,p) = 1$, this is equivalent to the usual formulation of the theorem (we can divide by $a$): $$a^{p-1} \equiv 1 \mod p$$ if $p$ is prime and $(a,p) = 1$. In this case, $9$ is not prime, so the theorem will fail.


There is however a generalisation that works for all integers, usually called the Fermat-Euler Theorem: we define $\phi(n)$ to be the number of integers less than $n$ that are coprime to $n$. Then if $(a,n)=1$, $$a^{\phi(n)} \equiv 1 \mod n$$

We have $\phi(9) = 6$ and indeed, $4^6 \equiv 1 \mod 9$.

$\endgroup$
  • $\begingroup$ And $9$ is not prime, which is why the theorem fails in this case. $\endgroup$ – spin Aug 3 '14 at 21:15
  • $\begingroup$ Fermat's Theorem holds in any finite field-even ones of non-prime order. So in any finite field of order $q$, we have $a^q=a$. This does not mean that $a^q\equiv a\mod q$ for each prime power $q$. This is because multiplication in $\Bbb F_q$ is different from multiplication in $\Bbb Z/q\Bbb Z$. $\endgroup$ – Robert Wolfe Aug 3 '14 at 22:20
  • 1
    $\begingroup$ I've never heard that general theorem called Fermat's theorem - I had always thought of Fermat as specifically referring to $\mathbb Z / p\mathbb Z$. Although both follow simply from Lagrange's theorem for finite groups $\endgroup$ – Mathmo123 Aug 3 '14 at 22:24

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.