In class we looked at three theorems about Carmichael numbers. (a) None of the f

Question

In class we looked at three theorems about Carmichael numbers.

(a) None of the following are Carmichael numbers: 3293372, 45, 133. Say why, either by finding a witness or by using a theorem from class.

(b) Explain why 105 is the smallest candidate for a Carmichael number.

(c) Korselt’s criterion says that if n is Carmichael then for each prime p|n we have p 1|n 1. Use this to show 165 is not Carmichael.

We have been using the Miller-Rabin test most recently but I'm not certain that that is what needs to be used in this question.

Explanation / Answer

Number 45=3*3*5 is not square free

105 is the smallest candidate because it has 3 distict odd prime factors and is squarefree, but it is no Carmichael number because 6 does not divide 104. The smallest example is 561=31117

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.