Loading ...
Sorry, an error occurred while loading the content.

Extended criterion for Carmichael numbers

Expand Messages
  • Kermit Rose
    It has been proven that an odd number N is a Carmichael number if and only if, for each prime divisor p, (p-1) divides N-1. Let N = q1 q2 q3 ...qj be a
    Message 1 of 1 , Dec 18, 2010
    • 0 Attachment
      It has been proven that an odd number N is a Carmichael number
      if and only if, for each prime divisor p,
      (p-1) divides N-1.

      Let N = q1 q2 q3 ...qj be a Carmichael number.

      (q1 - 1) divides N-1

      (q1 - 1) divides q1 q2 q3 ...qj - 1

      There exist c such that q1 q2 q3...qj - 1 = c(q1-1) = c q1 - c


      c q1 - (q2 q3 ... qj) q1 - c = -1

      Add q2 q3 ... qj to both sides of equation.

      c q1 - (q2 q3 ... qj) q1 - c + (q2 q3 ... qj) = (q2 q3 ... qj) - 1


      Factor left side of equation.

      (c - ( q2 q2 ... qj ) ) (q1 - 1) = (q2 q3 .... qj) - 1


      (q1 - 1) divides (q2 q3 .... qj) - 1

      Since q1 represents any one of the divisors of N,

      we have the extended criterion
      that

      each prime divisor, p, of the Carmichael number N,

      (p-1) divides (N/p) -1

      For the smallest Carmichael number
      561 = 3 * 11 * 17,

      (3-1) divides (561/3 - 1) = 187 - 1 = 186 = 2*93

      (11-1) divides (561/11 - 1) = 51 - 1 = 50 = 5*10

      (17-1) divides (561/17 - 1) = 33 - 1 = 32 = 2*16


      Kermit
    Your message has been successfully submitted and would be delivered to recipients shortly.