13
$\begingroup$

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.

$\endgroup$
12
  • 1
    $\begingroup$ See math.stackexchange.com/questions/173908/… $\endgroup$ May 26, 2016 at 5:19
  • 1
    $\begingroup$ This is never an integer for any number of distinct primes between $2$ and $14$. $\endgroup$
    – Erick Wong
    May 26, 2016 at 5:43
  • 2
    $\begingroup$ @ErickWong: Claiming this for any number of distinct primes between $2$ and $14$ is not particularly interesting (there are $5$ such primes, or $6$ if you meant inclusive). Claiming it for any number between $2$ and $14$ of distinct primes is rather more interesting. $\endgroup$ May 26, 2016 at 11:54
  • 2
    $\begingroup$ For three variables, this is an IMO problem (Year 1992, Problem 1). There are only two solutions $(p,q,r)$ with $1<p<q<r$: $(p,q,r)=(2,4,8)$ and $(p,q,r)=(3,5,15)$. Hence, no prime solutions. See cs.cornell.edu/~asdas/imo/imo/isoln/isoln921.html. $\endgroup$ May 26, 2016 at 14:03
  • 1
    $\begingroup$ @MarcvanLeeuwen: I think what Erick meant to say is that for $2\leq n\leq 14$ and distinct primes $p_1,\ldots,p_n$, the product $(p_1-1)\cdots(p_n-1)$ does not divide $p_1\cdots p_n-1$. $\endgroup$
    – tomasz
    May 26, 2016 at 15:30

5 Answers 5

20
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ There is always someone on a downvoting spree. This is a good answer. $\endgroup$
    – trichoplax
    May 26, 2016 at 12:17
  • $\begingroup$ How can you tell the time of the downvote? :s $\endgroup$ May 26, 2016 at 15:34
  • $\begingroup$ @LuisMasuelli Open another answerer's profile. Go to the reputation tab. See the last few reputation changes. With time. $\endgroup$ May 26, 2016 at 15:55
  • $\begingroup$ @Dhruv Good point, comment removed. $\endgroup$
    – Barry
    May 26, 2016 at 15:58
8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Nice. A lot simpler than mine. $\endgroup$ May 26, 2016 at 18:17
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Any ideas on how to prove the second one is not an integer? $\endgroup$
    – Puzzled417
    May 26, 2016 at 13:45
  • $\begingroup$ @Puzzled No I don't, but are you interested in whether second one can be an integer with $p,q,r$ being any distinct integers greater than $1,$ prime or not? [I thought someone had commented an example with all three primes, but see Yves' answer above, in which this is tried to be shown impossible.] $\endgroup$
    – coffeemath
    May 26, 2016 at 14:51
1
$\begingroup$

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

$\endgroup$

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.