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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .