Let $p$ and $q$ be distinct odd primes and $a$ be a positive integer with $a<p<q$. I need to prove that if $pq \ | \ \phi(n) $ then $n$ is prime. The proof for the trivial case when $a=2$ is given below.
Proof. Let $n=2pq+1$. Assume $pq \ | \ \phi(n)$. We may write $\phi(n) = cpq$ for some positive integer $c \le 2$. We know that $\phi(n)$ is even for all $n>2$ therefore we must have $c=2$ otherwise $\phi(n) $ is odd. $\phi(n) =2pq=n-1$ which shows that $ n $ is prime. This completes the proof for the trivial case $a=2$.
How do I prove that the proposition holds for an arbitrary positive integer $a$?
from Hot Weekly Questions - Mathematics Stack Exchange
David Jones
Post a Comment