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$
3
  • $\begingroup$ Yes, I know, Fermat $\endgroup$
    – Nethesis
    Commented Aug 3, 2014 at 21:10
  • 2
    $\begingroup$ $\varphi(9)$ is not $8$ but is $6.$ $\endgroup$
    – coffeemath
    Commented Aug 3, 2014 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$ Commented Aug 4, 2014 at 5:33

2 Answers 2

16
$\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$
7
  • 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
    Commented Aug 3, 2014 at 21:17
  • 3
    $\begingroup$ @Nethesis That should be and a and $p$ are coprime. Must be a typo $\endgroup$
    – Mathmo123
    Commented Aug 3, 2014 at 21:19
  • 1
    $\begingroup$ I'm sorry, I don't understand the difference between a and $a$... $\endgroup$
    – Nethesis
    Commented Aug 3, 2014 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
    Commented Aug 3, 2014 at 21:23
  • 3
    $\begingroup$ Ohh, thank you, the book did not phrase it in that way at all, thank you $\endgroup$
    – Nethesis
    Commented Aug 3, 2014 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$
3
  • $\begingroup$ And $9$ is not prime, which is why the theorem fails in this case. $\endgroup$
    – spin
    Commented Aug 3, 2014 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$
    – user123641
    Commented Aug 3, 2014 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
    Commented Aug 3, 2014 at 22:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .