Find all natural numbers $m$ having exactly three prime divisors $p,q,r$, such that $$p-1\mid m; \quad qr-1 \mid m; \quad q-1 \nmid m; \quad r-1 \nmid m; \quad 3 \nmid q+r.$$
Problem
Source: Macedonia National Olympiad 2015
Tags: number theory
06.04.2015 12:04
There is no positive integer $m$ with the following properties: $(1) \;\; m$ has exactly three prime divisors $p$, $q$, $r$ $(2) \;\; p - 1 \mid m$ $(3) \;\; qr - 1 \mid m$ $(4) \;\; q - 1 \nmid m$ $(5) \;\; r - 1 \nmid m$ $(6) \;\; 3 \nmid q + r$ Proof: Clearly $q \neq 2$ and $r \neq 2$ by (4) and (5) respectively. Hence $q$ and $r$ are both odd, which means $qr - 1$ is even. Thus $m$ is even by (3), yielding $p=2$. Consequently $q \neq 3$ and $r \neq 3$ by (4) and (5) respectively, which according to (6) implies $q \equiv r \equiv 1,2 \pmod{3}$. Therefore $3 \mid qr - 1$, yielding $3 \mid m$ by (3), contradicting (1) since $p=2$ and $q,r>3$. This contradiction completes the proof.
30.04.2015 14:07
Let $m=p^\alpha q^\beta r^\gamma$. Since $qr-1 \mid m=p^\alpha q^\beta r^\gamma$ and $\gcd(qr-1,q^\beta r^\gamma)=1$ then $qr-1 \mid p^\alpha$ and thus there is $0 \leq x \leq \alpha$ for which $qr-1=p^x$. Since $q-1 \nmid m$ and $r-1 \nmid m$ then $q$ and $r$ are both $>2$ thus they are odd and $qr-1$ is even so $x>0$ and $p=2$. If $x$ is odd then $qr=2^x+1=0 \mod 3$ thus $q=3$ or $r=3$ but in this case $q-1=2 \mid 2^\alpha q^\beta r^\gamma= m $ or $r-1=2 \mid 2^\alpha q^\beta r^\gamma =m $ which it is a contradiction. If $x$ is even then $qr=2^x+1=1 \mod 3$ thus $3 \mid qr-1 \mid m=2^\alpha q^\beta r^\gamma$ thus $3 \mid qr$ which it is a contradiction. Hence there is no solution for this problem.