Vipul: Created page with "==Statement== Suppose $n$ is a composite natural number that is a Carmichael number, i.e., it is a Fermat pseudoprime to every base relatively prime to..."

2012-01-15T21:14:34Z

Created page with "==Statement== Suppose <math>n</math> is a composite natural number that is a Carmichael number, i.e., it is a Fermat pseudoprime to every base relatively prime to..."

New page

==Statement==

Suppose <math>n</math> is a composite [[natural number]] that is a [[Carmichael number]], i.e., it is a [[Fermat pseudoprime]] to every base relatively prime to it. Equivalently, the [[universal exponent]] <math>\lambda(n)</math> divides <math>n- 1</math>.

Then, <math>n</math> is not a [[semiprime]].

==Facts used==

# [[uses::Carmichael number is square-free]]

==Proof==

We prove the contrapositive: a semiprime cannot be a Carmichael number.

By Fact (1), it suffices to restrict attention to a Carmichael number of the form <math>pq</matH> where <math>p,q</math> are distinct primes.

We have:

<math>\lambda(n) = \operatorname{lcm} \{ p - 1, q - 1\}</math>

In particular, for <math>\lambda(n)</math> to divide <math>n - 1</math>, we must have:

<math>p - 1 \mid n - 1 \qquad \mbox{ and } \qquad q - 1 \mid n - 1</math>

The first condition tells us that:

<math>n \equiv 1 \pmod{p - 1}</math>

Since we already have <math>p \equiv 1 \pmod{p - 1}</math>, and since <math>n = pq</math>, this gives <math>q \equiv 1 \pmod{p - 1}</math>. In particular, this gives <math>q \ge p</math>.

Similarly, the second condition tells us that <math>p \equiv 1 \pmod{q - 1}</math>. In particular, this gives <math>p \ge q</math>.

Combining, we get <math>p = q</math>, contradicting our requirement that <math>n</math> be a product of distinct primes.

Carmichael number is not semiprime - Revision history

Vipul: Created page with "==Statement== Suppose n is a composite natural number that is a Carmichael number, i.e., it is a Fermat pseudoprime to every base relatively prime to..."

Vipul: Created page with "==Statement== Suppose $n$ is a composite natural number that is a Carmichael number, i.e., it is a Fermat pseudoprime to every base relatively prime to..."