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

Homework Help: Carmichael Numbers

  1. Apr 30, 2006 #1
    Ive been trying to prove that the number 6601 is a Carmichael number. Ive gone some way to prove it but I don't like it. The first thing I did was look up the prime factors of 6601. And they are

    [tex]6601 = 7 \times 23 \times 41[/tex]

    And then I noticed that for each prime factor [itex]p_i = \{7,23,41\}[/itex] we have

    [tex]p_i - 1 = n \quad \mbox{and } n | (6601 - 1)[/tex]

    So that 7 - 1 = 6 and 6 divides 6600, 22 divides 6600, and 40 divides 6600.

    Now, Fermat's Little Theorem says that if a is an integer and q is coprime to a, then q divides [itex]a^{q-1} - 1[/itex]. And from this we can say that

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

    So since 7-1 divides 6601-1 we can say that

    [tex]a^{6600} \equiv 1(\mod 7)[/tex]
    [tex]a^{6600} \equiv 1(\mod 23)[/tex]
    [tex]a^{6600} \equiv 1(\mod 41)[/tex]

    because 7, 23, and 41 all divide q-1. and a and q are coprime. Multiplying these together we get

    [tex]a^{6600} \equiv 1(\mod 6601) \quad \forall a\in\mathbb{Z}[/tex]

    But is this enough to prove that 6601 is a Carmichael Number?
     
  2. jcsd
  3. Apr 30, 2006 #2
    duh! By the definition of a Carmichael number it is enough surely!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook