2 Carmichael number is positive composite integer n such tha

2. Carmichael number is positive composite integer n such that a^n = a (mod n)

2. Recall that a Carmichael number is a positive composite integer n such that A^n is equal by definition to a (mod n) for all integers a. i) Show that a^1729 is equal by definition to a (mod m) for m = 7, 13, and 19. Explain why this implies that 1729 is a Carmichael number. ii) Prove that any Carmichael number must he a product of distinct odd primes.

2. Recall that a Carmichael number is a positive composite integer n such that for all integers a. i) Show that a^1729 a (mod m) for m = 7, 13, and 19. Explain why this implies that 1729 is a Carmichael number. ii) Prove that any Carmichael number must he a product of distinct odd primes.

Solution

Consider the number 1729

1729 = 7x247 = 7x13x19

1729 is divisible by 7

a¹⁷²⁹ = (a⁷)^{13 )19}

^{Hence we have a^1729 = a mod 7, a mod 13, a mod 19.}

^{------------------------------------------}

^{Because a^1729 = amod 7, a mod 13 and a mod 19}

^{a is a Carmichael number.}

^{----------------------------------------------------------------------}

^{ii) if a number N is product of odd primes p,q,r say obviously}

a^N=a^pqr

Hence N is a Carmichael number

If N =pqr when one p is not prime say

then p = lm hence a^N=a^lmqr

then N becomes a Carmichael for l,m,q,r and not p, q, r

Suppose p is even then p is composite as 2l, hence the same proof follows.