Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Yes, I know, Fermat –  Nethesis Aug 3 at 21:10
2  
$\varphi(9)$ is not $8$ but is $6.$ –  coffeemath Aug 3 at 21:14
1  
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$. –  Robert Soupe Aug 4 at 5:33

2 Answers 2

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

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

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

share|improve this answer
    
And $9$ is not prime, which is why the theorem fails in this case. –  spin Aug 3 at 21:15
    
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$. –  Bryan Aug 3 at 22:20
1  
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 –  Mathmo123 Aug 3 at 22:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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