1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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