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

  • 1
    $\begingroup$ 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$. $\endgroup$ – lulu May 22 at 23:32
  • $\begingroup$ @lulu and why the equivalence to $0$? $\endgroup$ – Secretly May 22 at 23:52
  • 1
    $\begingroup$ Just think about it. If $k^2\,|\,k^n-k$ for $n≥2$ deduce that $k^2\,|\,k$. $\endgroup$ – lulu May 22 at 23:53
  • 1
    $\begingroup$ It has nothing to do with that. I think you need to review the basic properties of congruences. $\endgroup$ – lulu May 23 at 0:02
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.