1. carmichael numbers

question

Suppose that p, 2p-1, 3p-2 are all primes, with p>3 . Prove that p(2p-1)(3p-2) is a Carmichael number. Find the smallest Carmichael number of this form.

Thank you very much.

2. Originally Posted by Jenny20
question

Suppose that p, 2p-1, 3p-2 are all primes, with p>3 . Prove that p(2p-1)(3p-2) is a Carmichael number. Find the smallest Carmichael number of this form.

Thank you very much.
First I need to explain what a Carmichael number is.

Any prime satisfiers this (Fermat's little theorem):
$a^{p}\equiv a (\mbox{mod } p)$
For any integer $a$.

However, the converse fails.
For example,
$2^{341}\equiv 2 (\mbox{mod }341)$.
This is an example of a pseudoprime (to base two) for which the converse fails.

A pseudoprime to all base is call a Carmichaeal number.
----
Since $p,2p-1,3p-2$ are all primes we have.
Let $\gcd(a,p)=\gcd(a,2p-1)=\gcd(a,3p-2)=1$.
Then, Fermat's Elegant theorem (different version than above)
$a^{p-1} \equiv 1 (\mbox{mod }p)$
$a^{2p-2}\equiv 1 (\mbox{mod }2p-1)$
$a^{3p-3}\equiv 1 (\mbox{mod }3p-2)$
Thus,
$(a^{p-1})^{6p^2-(p-1)}\equiv 1(\mbox{mod }p)$
$(a^{2p-2})^{3p^2-(p-1)/2}\equiv 1(\mbox{mod }2p-1)$
$(a^{3p-3})^{2p^2-(p-1)/3}\equiv 1(\mbox{mod }3p-2)$

Important Note $(p-1)/2$ is an integer because primes are odd (usually) and we require for $(p-1)/3$ to be an integer we need that $p\equiv 1(\mbox{mod }3)$.

Now, because of relative primeness in the moduli we have,
$a^{6p^3-7p^2+2p-1}\equiv 1(\mbox{mod }p(2p-1)(3p-2)=6p^3-7p^2+2p)$
Thus,
$a^{6p^3-7p^2+2p}\equiv a(\mbox{mod }6p^3-7p^2+2p)$.

Thus, if $p\equiv 1(\mbox{mod }3)$.
And, $p,2p-1,3p-2$ are primes.
Then,
$p(2p-1)(3p-2)$ is a Carmichael number.
---
I am supprised, where did you get this theorem from? First time I hear of it. It is really interesting.

3. Rewrite

Suppose that p, 2p-1, 3p-2 are all primes, with p>3 . Prove that p(2p-1)(3p-2) is a Carmichael number.
Substitute $p=6k+1$, so $p(2p-1)(3p-2)=(6k+1)(12k+1)(18k+1)$. QED.

Carmichael Number -- from Wolfram MathWorld