A discrepancy in understanding the proof that any Carmichael number is square free.

Question

The proof as given in " David M. Burton " is as follows:

Suppose that $a^n \equiv a \pmod n$ for every integer a, but $k^2\mid n$ for some $k > 1.$ If we let $a = k,$ then $k^{n} \equiv k \pmod n.$ Because $k^2\mid n$, this last congruence holds modulo $k^2$; that is $ k \equiv k^{n} \equiv 0 \pmod {k^2}$, whence $k^2\mid k$, which is impossible. Thus, $n$ must be square-free.

But I do not understand this statement :

"this last congruence holds modulo $k^2$; that is $ k \equiv k^{n} \equiv 0\pmod {k^2}$"

Could anyone explain it for me please? why this last congruence holds modulo $k^2$ ? and why this leads to that $ k^{n} \equiv 0$?

Answer 1

Here's my steps.

• $a^n\equiv a\bmod n\implies nx+a=a^n$
• $k^2\mid n \implies n=k^2c$
• $a=k\implies k^2cx+k=k^n\implies k^n-k^2cx=k^2(k^{n-2}+cx)=k\implies k^2\mid k$

Hopefully you can get it in polynomial form. All I used was: conversion of modular congruence to a linear polynomial, divisor pairing, substitution, and factoring out ( reverse of distribution). The portion you quote breaks down to: $$k^n\equiv 0\bmod k^2$$ and, $$k\equiv k^n\bmod k^2$$ The latter of which follows from $k^2$ being a divisor of n, the former from $n>1$

Answer 2

It's a special case of: congruences persist mod factors of the modulus, i.e.

$$ \bbox[6px,border:1px solid red]{a\equiv \bar a\!\!\pmod{\!bm}\ \Rightarrow\ a\equiv \bar a\!\!\pmod{\! m}}\qquad\!$$

via defining divisibility persists: $\, m\mid bm\mid a-\bar a\,\Rightarrow\, m\mid a-\bar a\,$ by transitivity of "divides".

So in the OP the congruence $\,k\equiv k^{\large n}\pmod{\!n}\,$ remains true $\!\bmod k^2\,$ by $\,k^2\mid n$.

Thus $\bmod k^2:\,\ k\equiv k^{\large n}\equiv 0\,$ by $\,k^{\large 2}\mid k^{\large n}\,$ by $\,n\ge 2$

Remark $ $ You can find a full proof here of this criterion for Carmichael numbers, where I present this part concisely as follows:

If $\rm\,n\,$ isn't squarefree then $\rm\,1\neq \color{#0a0}{a^{\large 2}}\!\mid n\mid \color{#0a0}{a^{\large e}}\!-\!a\, \Rightarrow\: a^{\large 2}\mid a\:\Rightarrow\!\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: \color{#0a0}{a^2\mid a^{\large e}})$