Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

On Carmichael Numbers

  1. Oct 9, 2009 #1
    Hi everyone :-)

    at http://mathworld.wolfram.com/CarmichaelNumber.html it says that a Carmichael number is one which satisfies Fermat's little theorem:

    [tex]a^{n-1} \equiv 1 mod (n)[/tex]

    for every choice of a which is co-prime to n, with 1 < a < n.

    Why is the domain 1 < a < n specified?

    A maths book that I'm reading says "Can it happen that n is a pseudoprime to all possible bases a? The answer is yes and such numbers are called Carmichael numbers."

    Does this mean that the set (1,n) exhausts all possible bases a?

    Thanks :-)

  2. jcsd
  3. Oct 9, 2009 #2
    Yes, because [tex](a +bn)^{n-1} = a^{n-1} \mod n[/tex].
    Therefore you do not have to check the coprime numbers greater than n. Can you see why that is so?
    Last edited: Oct 9, 2009
  4. Oct 9, 2009 #3
    I see how that works.. and I expanded for n=3 to get a taste.

    Thanks, ramsey!
  5. Oct 11, 2009 #4
    Thomas 430: Does this mean that the set (1,n) exhausts all possible bases a?

    We are only considering coprime numbers, so that n==0 Mod n is not considered.

    By coprime there are only [tex]\Phi (n) [/tex] (Euler totient function) such possibilities. For example for n=15 there are only [tex]\Phi(3)*\Phi 5 = 8 [/tex] such numbers that form the multiplicative group.
  6. Oct 15, 2009 #5
    Thanks Robert, that makes good sense.
  7. Oct 15, 2009 #6
    Good! Glad to hear.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook