# Prove a property about Carmichael number

Question: How can I prove the following statement?

There are no natural numbers $$n$$ and $$q$$ such that $$q$$ and $$nq+1$$ are both prime factors of the same Carmichael number.

Context:

A composite odd number $$N$$ is a Carmichael number iff $$N$$ is a squarefree and $$p-1$$ divides $$N-1$$ for every prime $$p$$ dividing $$N$$.

• If such $n$ and $q$ exist, $nq$ divides $N-1$ by definition, so $q$ divides $N-1$. But $q$ also divides $N$. – Hw Chu Sep 9 '19 at 17:52
• Which claim are you trying to prove? The iff statement in your first paragraph or the implication of the iff statement in your second? – lulu Sep 9 '19 at 17:54
• Use the first paragraph to prove the second paragraph @lulu – abeer lshtayeh Sep 9 '19 at 17:58
• This is a logical interpretation Thanks @HwChu – abeer lshtayeh Sep 9 '19 at 18:01
• In that case, I think the comment from @HwChu is the best way to proceed. – lulu Sep 9 '19 at 18:01

Suppoese, $$\ N\$$ is a Carmichael number and $$\ n\$$ a positive integer such that $$\ q\$$ and $$\ r:=nq+1\$$ are both prime factors of $$N$$.
Then, we have $$q\mid N$$ and $$nq=r-1\mid N-1$$ implying $$q\mid N-1$$ which contradicts $$q\mid N$$