# Carmichael number square free

Show that if $n$ is a Carmichael number, then $n$ is a square-free.

I did this: Let $n= (p^t)(m)$ where $t >1$. Then by modular property, $$b^p= b \mod n , \,\, b^m= b \mod n$$ Above two equations are also true in$\mod p$, $\mod p^t$. But in$\mod m$, just $b^n=b \mod m$.

And I tried to use CRT But I couldn't. I think that I've chosen wrong way

• By the way : A Carmichael number must also be odd and have at least $3$ prime factors. Korselt (as mentioned below) noticed the nice criterion : If $n$ is odd , squarefree and composite , $n$ is a Carmichel number iff $p-1\mid n-1$ holds for every prime $p$ dividing $n$. Jun 29, 2023 at 8:35

We start as in your post, letting $n=p^tm$ where $t\ge 2$ and $m$ is not divisible by $p$.

By the Chinese Remainder Theorem, the system of congruences $x\equiv 1+p\pmod{p^t}$, $x\equiv 1\pmod{m}$ has a solution $a$. Note that $\gcd(a,n)=1$.

Since $n$ is Carmichael, we have $a^{n-1}\equiv 1\pmod{n}$. In particular, $a^{n-1}\equiv 1\pmod{p^t}$, and therefore $a^{n}\equiv a\pmod{p^2}$.

So $(1+p)^{n}\equiv 1+p\pmod{p^2}$. Expand $(1+p)^{n}$ modulo $p^2$ using the binomial theorem. We get that $(1+p)^{n}\equiv 1\pmod{p^2}$, since the first two terms of the expansion are $1$ and $np$, and the rest of the terms are divisible by $p^2$.

Thus $1\equiv 1+p\pmod{p^2}$. This is impossible.

• It is not clear the use of chinese remainder theorem in the rest of the proof. Also no clear why you select $1+p$ on the fourth parragraph. After all, $gcd(1+p,n) \neq 1$ Jan 19, 2021 at 19:09

You ask about a part of the theorem of Korselt of which I adjoint a copy. Unfortunately I don't remember the source of the publication however I give you a curious detail: Korselt has made his discovery before these numbers were called Carmichael and could not find any. It was Carmichael who discovered the first, 561,several years after this theorem.

• Wow .. then third sentence of theorem is also can be definition of charmichael number.. right? Apr 30, 2016 at 2:09
• That is correct! I never have forgotten the "curious detail". Have you liked it? It seems to me Korselt was a true mathematical genius. I don't know if Carmichael used a computer to find 561. Apr 30, 2016 at 11:03
• I think so too! Thank you for great information! Apr 30, 2016 at 11:45
• You are welcome. Don't forget to add the necessary condition "odd not prime" to n. May 1, 2016 at 10:53
• Ok n must be odd and composite May 1, 2016 at 11:41

In my honest opinion, the given proofs are too long. Here's my approach:

Suppose $$p^2\mid n$$, where $$p$$ is a prime. Because $$n$$ is a Carmichael number, we know that $$p^n\equiv p\pmod{n}$$. Since $$p^2\mid n$$, we deduce $$p^n\equiv p\pmod{p^2}$$. But, given that $$n\geq 2$$, this last congruence becomes $$p\equiv 0\pmod{p^2}$$, a contradiction.

• Nice proof (+1) , but the usual definition of a Carmichael number is that $a^{n-1}\equiv 1\mod n$ holds for all $a$ coprime to $n$. The complicated or longer proofs have the reason that they only use this property and not the stronger property $a^n\equiv a\mod n$ for every $a$. Jun 29, 2023 at 8:31