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.


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

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


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.