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?

  • 3
    just find one counterexample.2012-12-09
  • 1
    You might want to run a search on "pseudoprime".2012-12-09
  • 0
    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”.2012-12-11
  • 1
    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$.2012-12-11

1 Answers 1