Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Maths in a minute: Pretend primes

      8 July, 2015
      Suppose you have a prime number p and some other natural number x. Then, no matter what the value of x is, as long as it's a natural number, you will find that xp−x is a multiple of p.

      This result is known as Fermat's little theorem, not to be confused with Fermat's last theorem.

      Let's try the little theorem with a few examples. For p=2 and x=5 we have 52−5=25−5=20=10×2. For p=3 and x=2 we have 23−2=8−2=6=2×3. And for p=7 and x=11 we have 117−11=19,487,171−11=19,487,160=2,783,880×7. You can try it out for other values of p and x yourself.
      Fermat

      Pierre de Fermat.

      Fermat first mentioned a version of this theorem in a letter in 1640. As with his last theorem, he was a little cryptic about the proof:

      "...the proof of which I would send to you, if I were not afraid to be too long."

      But unlike with Fermat's last theorem, a proof was published relatively soon; in 1736 by Leonhard Euler.

      But does Fermat's little theorem work the other way around? If you have a natural number n so that for all other natural numbers x xn−x is a multiple of n, does this imply that n is a prime? If this were true, then we could use Fermat's little theorem to check whether a given number n is prime: pick a bunch of other numbers x at random, and for each of them check whether xn−x is a multiple of n. If you find an x for which this isn't true, then you know for sure that n isn't prime. If you don't find one, then provided you have checked sufficiently many x, you can be pretty sure that n is prime. This method is called Fermat's primality test.
      Alas, it doesn't quite work as well as it could. In 1885 the Czech mathematician Václav Šimerka discovered non-prime numbers that masquerade as primes when it comes to Fermat's little theorem. The number 561 is the smallest of them. It's not prime, but for all other natural numbers x we have that x561−x is a multiple of 561.

      Šimerka also discovered that 1105,1729,2465,2821,6601 and 8911 behave in the same way. Natural numbers that aren't primes but satisfy the relationship stated in Fermat's little theorem are sometimes called pseudoprimes, because they make such a good job of behaving like primes, or Carmichael numbers, after the American Robert Carmichael, who independently found the first one, 561, in 1910.

      You can see from the first seven named above that Carmichael numbers aren't too abundant. There are infinitely many of them, a fact that wasn't proved until 1994, but they are very sparse. In fact, they get sparser as you move up the number line: if you count the Carmichael numbers between 1 and 1021, you'll find that there are only around one in 50 trillion.

      Carmichael numbers do hamper Fermat's primality test somewhat, but not so badly as to make it totally unusable. And there are modified versions of the test that work very well. As cans of worms opened by Fermat go, the one involving Carmichael numbers definitely wasn't the worst.

      • Log in or register to post comments

      Read more about...

      Fermat's Last Theorem
      prime number
      number theory
      Maths in a minute
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms