Carmichael proof of at least 3 prime factors I'm having some trouble while trying to prove the well known fact that a Carmichael number has at least 3 prime factors.
Basically, how I see it, I have 2 options:


*

*building a number b that will satisfy $b^{n-1}\not\equiv 1(n)$ thus creating a fermat witness

*trying to contradict the condition of: $p|n \iff\ p-1|n-1$
Maybe I'm missing something very simple but I can't seem to get this done.
Addition: we are talking about the case where $n=pq$, the case $n=p$ is trivial.
 A: Assume that $n=pq$, with $p<q$ two distinct primes, is a Carmichael number. Then we have
$$
q\equiv1\pmod{q-1}\implies n=pq\equiv p\mod{q-1}\implies n-1\equiv p-1\pmod{q-1}.
$$
Here $0<p-1<q-1$, so $n-1$ is not divisible by $q-1$. A contradiction.
The same argument can be extended to prove that any prime factor of a Carmichael number $n$ is less than $\sqrt n$. Namely, as above we get for all primes $p\mid n$
$$
n-1\equiv p\frac{n}{p}-1\equiv \frac{n}{p}-1\pmod{p-1}.
$$
Therefore $n/p-1$ must be a (positive) multiple of $p-1$. Thus
$$
\frac{n}{p}-1\ge p-1\implies\frac{n}{p}\ge p\implies n\ge p^2.
$$
A: (Personally, I find the following proof very unsatisfying, because it provides me no insight: it seems to all boil down to rather tedious numerical nitty-gritty.  Unfortunately, this seems to be par for the course in number theory, at least in my limited experience.)
Suppose $n = pq$, where $p$ and $q$ are prime, $p < q$, and $(q - 1)|(n - 1)$.  We show that these conditions lead to a contradiction.
The last condition is equivalent to saying that there exists an integer $k$ such that
$$
n -  1 = pq - 1 = k(q - 1)\, \tag{1}
$$
Since $q > p > 1$, it follows that $n = pq > q$, and therefore $n - 1 > q - 1$.
This, together with $(1)$, implies that $k > 1$.
Now, rearranging the second equality in $(1)$ we get
$$
k = q(k - p) + 1 \,.
$$
Since we already established that $k > 1$, the last equality implies that
$$k - p \geq 1\,.\tag{2}$$
Now, once more rearranging the second equality in $(1)$, to
$$
0 = k(q - 1) - pq + 1\,
$$
and adding $p$ to both sides, we arrive at a contradiction:
$$
p = k(q - 1) - pq + p + 1 = (k - p)(q - 1) + 1 > (k-p)(p-1) + 1 \geq (p-1) + 1 = p \,.
$$
Note that the last inequality above follows from $(2)$.
