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$
  • 1
    $\begingroup$ See math.stackexchange.com/questions/173908/… $\endgroup$ – lab bhattacharjee May 26 '16 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 '16 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$ – Marc van Leeuwen May 26 '16 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$ – Batominovski May 26 '16 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 '16 at 15:30
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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ There is always someone on a downvoting spree. This is a good answer. $\endgroup$ – trichoplax May 26 '16 at 12:17
  • $\begingroup$ How can you tell the time of the downvote? :s $\endgroup$ – Luis Masuelli May 26 '16 at 15:34
  • $\begingroup$ @LuisMasuelli Open another answerer's profile. Go to the reputation tab. See the last few reputation changes. With time. $\endgroup$ – TheRandomGuy May 26 '16 at 15:55
  • $\begingroup$ @Dhruv Good point, comment removed. $\endgroup$ – Barry May 26 '16 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.

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice. A lot simpler than mine. $\endgroup$ – marty cohen May 26 '16 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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Any ideas on how to prove the second one is not an integer? $\endgroup$ – Puzzled417 May 26 '16 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 '16 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)$.]

| cite | improve this answer | |
$\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.