2
$\begingroup$

I would like to show that Fermat's Little Theorem doesn't hold when p is not prime.

I'm assuming this would be a proof by contradiction that Fermat's Theorem only works with prime numbers, but I'm not sure how to go about writing such a proof. Would we need to show that if p isn't prime, then a to any power less than p may share a common factor with p?

$\endgroup$
4
  • 3
    $\begingroup$ just find one counterexample. $\endgroup$
    – user51427
    Dec 9, 2012 at 3:01
  • 1
    $\begingroup$ You might want to run a search on "pseudoprime". $\endgroup$
    – Gerry Myerson
    Dec 9, 2012 at 5:48
  • $\begingroup$ It’s not clear to me just what your quest is. Is it to find a single counterexample, as @sunflower says, or is it to show that for every nonprime, say $P$, Fermat’s Little fails for $P$? If the latter, take @Gerry’s suggestion, or look up “Carmichael numbers”. $\endgroup$
    – Lubin
    Dec 11, 2012 at 1:34
  • 1
    $\begingroup$ Partly depends on how you write Fermat's Theorem. if we use the $x^p\equiv x\pmod{p}$ version, it does hold for some non-primes. Take for example $p=4$. $\endgroup$
    – André Nicolas
    Dec 11, 2012 at 2:07

1 Answer 1

Reset to default
3
$\begingroup$

$a^{p-1} \equiv 1 \bmod p $

let $a = 2$, $p =4$

$2^3 = 8 \bmod 4 =0$

$\endgroup$
3
  • 1
    $\begingroup$ But $a=2$ is also a counterexample for $p=2$. It's a little harder to find a counterexample if you insist on $\gcd(a,p)=1$ in your statement of Fermat. . $\endgroup$
    – Gerry Myerson
    Dec 11, 2012 at 3:09
  • $\begingroup$ @GerryMyerson, he is from my class, I'm pretty sure this counterexample is enough for the grader to give him full point. $\endgroup$
    – xiamx
    Dec 11, 2012 at 3:19
  • $\begingroup$ Fine, but he's missing out on the interesting stuff. (Aside: Jillian is a he?) $\endgroup$
    – Gerry Myerson
    Dec 11, 2012 at 3:20

You must log in to answer this question.

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