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

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$$?

• This is just the definition of congruence. Saying $b\equiv c \pmod m$ means $m\,|\,(b-c)$. Of course, if this is true then, if $d\,|\,m$ we must also have $d\,|\,(b-c)$ or $b\equiv c \pmod d$. – lulu May 22 at 23:32
• @lulu and why the equivalence to $0$? – Secretly May 22 at 23:52
• Just think about it. If $k^2\,|\,k^n-k$ for $n≥2$ deduce that $k^2\,|\,k$. – lulu May 22 at 23:53
• It has nothing to do with that. I think you need to review the basic properties of congruences. – lulu May 23 at 0:02
• Please review the basic properties of congruences. Getting other people to do homework (or homework level) problems for you is a terrible way to learn a subject. – lulu May 23 at 0:06

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$$

• how is the former from $n > 1$, what if $n=3$? or it can not be because we are assuming that $k^2 | n$? – Secretly May 23 at 2:19
• if $n<2$ then $k^{n-2}=k^m, m<0$ – Roddy MacPhee May 23 at 2:23
• No this is not what I am asking, I am saying if n is as odd number greater than 2, like 3 for example – Secretly May 23 at 2:30
• if n is greater than 2, then $n-2$ is greater than 0 leading to $k^n$ having $k^2$ as a factor. – Roddy MacPhee May 23 at 2:33
• got it thanks :) – Secretly May 23 at 2:39

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

$$\bbox[5px,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}})$$