| | |
Prove that if $n$ is a Carmichael number, it must be square-free.
(An integer is said to be square-free if there is no perfect square other than $1$ that divides it.)
Argue indirectly. Suppose there is some perfect square other than $1$ that divides $n$. Without loss of generality, we may assume it is a square of some prime $p$.
Identifying the highest power of $p$ that divides $n$ as $p^k$, we can then say $n = p^k m$ where $k \ge 2$ and $gcd(p,m) = 1$.
Note that $gcd(p^k,m)=1$ tells us that we can find a unique solution$\pmod{p^k m}$ for $a$ in the following system of congruences, via the Chinese Remainder Theorem: $$\begin{align*} a &\equiv 1+p&\pmod{p^k}\\ a &\equiv 1&\pmod{m} \end{align*}$$
It must be the case that $gcd(a,n) = 1$, as otherwise there would be a prime $q$ that would divide both $a$ and $n$. This would be a problem as if $q \mid m$, then $q \not\equiv 1\pmod{m}$, and if $q = p$, then $q \not\equiv 1+p\pmod{p^k}$.
Since $n$ is a Carmichael number and $gcd(a,n) = 1$, we know $$a^{n-1} \equiv 1\pmod{n}$$ Recalling $n$ is a multiple of $p^k$, we can reduce this to $a^{n-1} \equiv 1\pmod{p^k}$, and then recalling the system of congruences above for which $a$ was a solution, we can replace $a$ with $(1+p)$: $$(1+p)^{n-1} \equiv 1\pmod{p^k}$$ Multiplying both sides by $(1+p)$, we have $$(1+p)^n \equiv 1 + p\pmod{p^k}$$ Since $k \ge 2$, we know $p^2 \mid p^k$, allowing us to reduce the modulus even further to $$(1+p)^n \equiv 1 + p\pmod{p^2}$$ However, consider the expansion of $(1+p)^n$ by the binomial theorem. $$\begin{align*} (1+p)^n &= 1 + np + {}_nC_2p^2 + {}_nC_3p^3 + \cdots\\ &= 1 + np + p^2({}_nC_2 + {}_nC_3p + \cdots)\\ &= 1 + np + p^2k\\ &= 1 + p^2k_2 \textrm{ for some } k_2 \in \mathbb{Z}, \textrm{ as } p \mid n\\ &\equiv 1\pmod{p^2} \end{align*}$$ Thus we have argued that both $(1+p) \equiv 1+p\pmod{p^2}$ and $(1+p) \equiv 1\pmod{p^2}$. This is of course impossible. We have the desired contradiction -- thus every Carmichael number $n$ must be square-free.