# Product of two distinct odd primes is not carmichael

Let $p,q$ be distinct odd primes. Define $N=pq$. Then $N$ is not a carmichael number.

Proof: Suppose $N$ is carmichael. By the Chinese remainder theorem we can find a primitive root $a\in\mathbb{N}$ modulo $p$. Then $a\equiv 1\mod{q}$.

$$a^N=a^{pq}\equiv a\mod{N}\quad \tag{as N is a Carmichael number}$$

Since $p\mid N$ we find that

$$a^{pq}\equiv a\mod{p}$$

By Fermat's little theorem, ($a^p\equiv a\mod{p}$), note that

$$a^{pq}\equiv a^q\equiv a\mod{p}\implies a^{q-1}\equiv1\mod{p}$$

Since $a$ is a primitive root modulo $p$, $p-1\mid q-1$, hence $p-1\le q-1$. By swapping the role of $p$ and $q$ we find that $q-1\le p-1$, thus $p-1=q-1 \implies p=q$, but $p$ and $q$ are distinct so $N$ is not carmichael.$$\tag*{\blacksquare}$$

Question:

Why does $a$ being a primite root modulo $p$ produce the implication:

$$a^{q-1}\equiv 1\mod{p}\implies p-1\mid q-1$$

By definition of primitive root $p-1$ is the smallest exponent $k>0$ with $a^k\equiv 1\mod{p}$. Write $q-1 = n(p-1)+m$ with $0\le m < p-1$. You have to show $m=0$. This follows from $$1\equiv a^{q-1}\equiv a^{n(p-1)+m}\equiv a^{n(p-1)}a^m \equiv (a^{p-1})^n a^m\equiv1^n a^m \equiv a^m \pmod p$$ $m>0$ would contradict the primitive root proportery of $a\,$, thus $m=0\,$ and $q-1\,$ is a multiple of $p-1$.