Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Prove that if $p$ and $q$ are distinct primes then $\dfrac{pq-1}{(p-1)(q-1)}$ is never an integer. Is it similarly true that if $p,q,r$ are distinct primes then $\dfrac{pqr-1}{(p-1)(q-1)(r-1)}$ is also never an integer?
I think using a modular arithmetic argument here would help. In other words, we must have for the first fraction $pq-1 \equiv 0 \pmod{(p-1)(q-1)}$. Then I am unsure how to proceed next since we can't really use the Chinese Remainder Theorem.
Suppose, for the sake of contradiction, such distinct $p$ and $q$ exist. First of all observe that the statement implies that $p-1|pq-1$. So,
$$p-1|pq-1-q(p-1) \implies p-1|q-1$$
Similarly we get,
$$q-1|p-1$$
These observations imply that $p-1 = q-1$. This implies that $p = q$. Contradiction. They aren't distinct.
I will assume that $p \le q$, not just $p < q$. Also, you don't need the assumption about primality.
I will show that the only solutions are $p=q=2$ and $p=q=3$.
If $p=2$ then $\dfrac{pq-1}{(p-1)(q-1)} =\dfrac{2q-1}{q-1} =\dfrac{2q-2+1}{q-1} =2+\dfrac{1}{q-1} $ which is not an integer unless $q = 2$.
If $p=3$ then
$\begin{array}\\ \dfrac{pq-1}{(p-1)(q-1)} &=\dfrac{3q-1}{2(q-1)}\\ &=\dfrac{3q-3+2}{2q-2}\\ &=\dfrac32+\dfrac{1}{q-1}\\ \end{array} $
which is not an integer if $q \ge 4$. If $q=3$, then $\dfrac{pq-1}{(p-1)(q-1)} =\dfrac{3\cdot 3-1}{2\cdot 2} =2 $ which is an integer.
If $p > 3$ then
$\begin{array}\\ \dfrac{pq-1}{(p-1)(q-1)} &=\dfrac{pq-1}{pq-p-q+1}\\ &=\dfrac{pq-p-q+1+p+q-2}{pq-p-q+1}\\ &=1+\dfrac{p+q-2}{pq-p-q+1}\\ \end{array} $
so we are done if $p+q-2 <pq-p-q+1 $ or $0 <pq-2p-2q+3 =(p-2)(q-2)-1 $ and this is true.
$$\frac{pq-1}{(p-1)(q-1)}-1=\frac1{p-1}+\frac1{q-1}$$cannot be an integer, as the only possible values would be $2$ ($p=q=2$) or $1$ ($p=q=3$).
Similarly,
$$\frac{pqr-1}{(p-1)(q-1)(r-1)}-1\\ =\frac1{p-1}+\frac1{q-1}+\frac1{r-1}+\frac1{(p-1)(q-1)}+\frac1{(q-1)(r-1)}+\frac1{(r-1)(p-1)}$$ cannot be an integer for $p,q,r>4$ as the sum wouldn't exceed $\dfrac{15}{16}$.
The remaining possibilities for $p<q<r$ are $2,q,r$ and $3,q,r$. The maximum value of the sum is achieved for $2,3,5$ and equals $\dfrac{21}8$, hence the only possible integer values are $2$ and $1$.
To be continued.
For the first one, the expression is equal to $1+1/(p-1)+1/(q-1).$ If $p=2$ this leaves that $1/(q-1)$ is an integer, but here $q>2$ so no cases. So if $2<p<q$ the first case is $p=3,q=5$ leading to $1/2+1/4=3/4$ an integer, not so [too small], and for larger $p,q$ the two fractions have an even smaller sum.
Yves Daoust's answer covers the two-prime case as well as the three-prime case except when $p \in \{2,3\}$. Here's a simple way to dispense with the remaining cases efficiently:
Suppose $\frac{pqr-1}{(p-1)(q-1)(r-1)}$ is an integer. Then neither $q$ nor $r$ is congruent to $1$ mod $p$.
This is easy to see because the numerator is not divisible by $p$, so the denominator cannot have any factors of $p$.
The above observation immediately eliminates the case $p=2$. For $p=3$, look at the numerator and denominator mod $3$. The numerator is $2\pmod 3$, and so is the denominator (because $q$ and $r$ must be $2$ mod $3$ by above observation). Thus the quotient, if it is an integer, must be $\equiv 1\pmod3$, and since it's $>1$ it must be $\ge 4$. But the computation in Yves's answer shows that it can't possibly be that large.
[Note that $q$ and $r$ are forced to be $2 \pmod 3$ because they can't be $0 \pmod 3$: this is where we use the fact that $q$ and $r$ are prime, so the argument is consistent with the existence of non-prime solutions $(2,4,8)$ and $(3,5,15)$.]
