# Little question about gcd and Fermat pseudoprimes.

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?

• $\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}$. – Minus One-Twelfth Apr 13 at 6:43
• @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? – 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)\$$