0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.