7
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Peter
    Jun 29, 2023 at 8:35

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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$ $\endgroup$
    – EvaMGG
    Jan 19, 2021 at 19:09
3
$\begingroup$

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.

enter image description here

$\endgroup$
5
  • $\begingroup$ Wow .. then third sentence of theorem is also can be definition of charmichael number.. right? $\endgroup$
    – wtgrea
    Apr 30, 2016 at 2:09
  • $\begingroup$ 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. $\endgroup$
    – Piquito
    Apr 30, 2016 at 11:03
  • $\begingroup$ I think so too! Thank you for great information! $\endgroup$
    – wtgrea
    Apr 30, 2016 at 11:45
  • $\begingroup$ You are welcome. Don't forget to add the necessary condition "odd not prime" to n. $\endgroup$
    – Piquito
    May 1, 2016 at 10:53
  • $\begingroup$ Ok n must be odd and composite $\endgroup$
    – wtgrea
    May 1, 2016 at 11:41
2
+50
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Peter
    Jun 29, 2023 at 8:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .