From Wikipedia:

...a Carmichael number is a composite number $n$ which satisfies the modular arithmetic congruence relation:

$1)$ $b^{n-1}\equiv 1{\pmod {n}}$

for all integers $b$ which are relatively prime to $n$...

Equivalently, a Carmichael number is a composite number $n$ for which

$2)$ $b^{n}\equiv b{\pmod {n}}$

for all integers $b$.

It's clear to me that $2) \Rightarrow 1)$ if $\gcd(b,n)=1$, but I can't rule out the possibility of $\gcd(b,n) \neq 1$ (so that $1)$ is emptily satisfied) and $2)$ not holding.

Is it true that if $\gcd(b,n) \neq 1$ then $b^{n}\equiv b{\pmod {n}}$?

Also, regarding Fermat's pseudprimes, many sources define them using the congruence $b^{n}\equiv b{\pmod {n}}$. Other (like Wikipedia) uses the congruence $b^{n-1}\equiv 1{\pmod {n}}$, which seems more restrictive. I know theoretically this is a minor difference, my only doubt is about the available statistics about pseudoprime, to which definition they conform?

  • 3
    $\begingroup$ $\newcommand{\gcd}{\operatorname{gcd}}$Say $b=6$ and $n=4$. Then $$\gcd(b,n)=\gcd(6,4)=2\ne 1.$$ But $$\begin{align}b^n &= 6^4 \\ &= 36\times 36 \\ &\equiv 0\times 0 \\ &\equiv 0\pmod{4},\end{align}$$ and $$b=6\equiv 2\pmod{4}.$$ Hence $b^n\not\equiv b\pmod{n}$. This shows that it is not generally the case that if $\gcd(b,n)\ne 1$, then $b^n\equiv b\pmod{n}$. $\endgroup$ – Minus One-Twelfth Apr 13 at 6:43
  • $\begingroup$ @Minus One-Twelfth Thanks for you good example, but it leaves open the main question. Are the two definition of Carmichael numbers equivalent? n = 4 doesn't satisfy 1) with b = 3. Is it possible for a number n to satisfy 1) and not satisfy 2) because is not coprime to b for a particular choice of b for which 2) doesn't hold? $\endgroup$ – Dany03 Apr 13 at 7:48

Suppose $\ (1)\ $ holds

Let $\ p\ $ be a prime factor of $\ n\ $

  • If $\ p\ $ divides $\ b\ $, then $\ b^n \equiv b\mod p\ $ is obvious
  • If $\ p\ $ does not divide $\ b\ $ , we have $\ b^{n-1}\equiv 1\mod p\ $ implying $\ b^n\equiv b\mod p\ $

Since $\ n\ $ must be squarefree ( a Carmichael number is always squarefree ) , the chinese remainder theorem allows to conclude that with all prime factors of $\ n\ $ , $\ n\ $ itself must divide $\ b^n-b\ $ , showing $\ (2)\ $


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.