AoPS - Problem

rafayaashary1

28.09.2016 03:32

coquitao

28.09.2016 04:18

Lookin' at the eq. mod $3$ gives that exactly one of the members of the set $\{p,q,r\}$ is equal to $3$. Supposing that $p=3$, the eq. becomes $$3q+qr+3r=12k+1.$$ Resorting to Simon's Favorite Factoring Trick we can rewrite this eq. as follows: $$(q+3)(r+3) = 2(6k+5).$$Since $2(6k+5)$ is twice an odd number, it follows that $r=2$ or $q=2$. If $r=2$, then $5=12k-5q$ and whence $k=5, q=11$. If $q=2$, then $5=12k-5r$ and whence $k=5, r=11$. It follows that the sols. to the given equation are: $p=2, q=3 , r=11, k=5$ $p=2, q=11, r=3, k=5$ $p= 3, q=11, r=2, k=5$ $p= 3, q=2, r=11, k=5$ $p=11, q=3, r=2, k=5$ $p=11, q= 2, r=3, k=5$.

rafayaashary1

28.09.2016 04:20

It seems that $k$ prime was just a distraction then?

Leicich

28.09.2016 04:24

It depends. I can think of another way of doing it that relies on $p,q,r,k$ being all prime numbers

coquitao

28.09.2016 05:38

rafayaashary1 wrote: It seems that $k$ prime was just a distraction then? If we dropped that condition, we would have infinitely many solutions: for any $u \in \mathbb{N}$ such that $q=12u-1$ is a prime number (a well-known theorem due to Dirichlet allows us to ascertain the existence of infinitely many such $u$), it would suffice to make $p=3, r=2, q=12u-1, k=5u$.

rafayaashary1

28.09.2016 05:46

RIP that makes more sense

Kezer

05.10.2016 00:20

I've a rather bashy solution. If $p,q,r>3$, then as they are primes, they satisfy the congruency $p,q,r \equiv \pm 1 \pmod 6$. As that right-hand side is congruent to $1 \pmod 6$ and the left-hand side has terms congruent to $\pm 1 \pmod 6$, we can conclude that exactly one term is congruent to $-1 \pmod 6$. WLOG $pq \equiv -1 \pmod 6$ and WLOG $p \equiv 1$ and $q \equiv -1$. But that $r \equiv -1$ to ensure the congruency $qr \equiv 1 \pmod 6$. That then gives $rp \equiv -1 \pmod 6$. Contradiction. Let $p = \min(p,q,r)$. Then $p \leq 3$. If $p=3$, then \[ 1 \equiv 12k+1 = 3q+3r+qr \equiv qr-q-r \pmod 4. \]Now $q,r \equiv \pm 1 \pmod 4$ as $q,r \geq p>2$. Testing all possibilities shows that the above congruence cannot be satisfied. If $p=2$, then \[ 2q+2r+qr=12k+1. \]If $q,r \neq 3$, then $q,r \equiv \pm 1 \pmod 3$. By testing we can easily show that there are no solutions again. Therefore, we can WLOG let $q = 3$. We then get \[ 6+5r=12k+1 \iff 5(r+1)=12k. \]As $k$ is prime, we get $k=5$ and $r=11$. So $(p,q,r,k)=(2,3,11,5)$ which is indeed a solution, as $p,q,r,k$ are all primes and plugging them into the equation gives as equality. Permuting the triple $(p,q,r)$ gives us all ordered quadruples.

emiliorosado

05.10.2016 06:26

Suppose all primes in the left hand of the equation are odd. Analize mod $4$ and always find $3\equiv1\ (\mbox{mod }4)$, a contradiction. Thus we can assume $r=2$. Rewrite the resulting equation as $$ (p+2)(q+2)=12k+5 $$thus \[ (p+2)(q+2)\equiv2\ (\mbox{mod }3) \]then one of $p+2$ or $q+2$ is $2$ mod $3$ thus one of $p$ or $q$ is $0$ mod $3$ (so equal to $3$ since both are primes). Thus we can assume $q=3$. Then the original equation becomes \begin{align*} (p+2)\cdot5 & =12k+5 \end{align*}thus $5|k$ so $k=5$. Then $p=11$ and we are done. The values of $p$, $q$, and $r$ can be permuted.

Borbas

05.10.2016 18:34

Here is my solution: We assume WLOG $p \ge q \ge r$. Working $(mod 4)$ we realise that one of $p,q,r$ must be equal to $2$. Which means $r=2$. Then working $(mod 3)$ we realise that one of $p,q$ must be equal to $3$. Which means $q=3$. Finally we easily notice that $5$ divides $k$ which means $k=5$ and $p=11$. Concluding $k=5$ and $(p,q,r)=(11,3,2)$ cyclic.

PennyLane_31

31.10.2023 00:58

We know that $pq+pr+qr= 12k+1$(1), for some $p,q,r,k$ primes. Notice that we have a symmetric expression on LHS, so we can order the primes. Suppose, WLOG, $p\geq q\geq r$. Affirmation 1: In particular, we can only have $p>q>r$. this is easy to prove, but here's the formal proofProof: Suppose, WLOG, $p=q$. So, by (1), we have: $p^2+2pr= 12k+1\implies (p+r)^2= 12k+1+r^2$. Analyzing modulo 3, we got: $(p+r)^2\equiv r^2+1$ (mod 3). As any perfect square $x^2, x\in\mathbb{Z}$, we know $x^2\equiv 0$ or $1$ (mod 3) $\implies (p+r)^2\equiv 0+1$ or $1+1$ (mod 3) $\implies (p+r)^2\equiv 1$ or $2$ (mod 3), but $(p+r)^2$ is perfect square as well, so it can't be 2 modulo 3, so it has to be 1, and $r^2\equiv 0$ (mod 3) $\implies 3\mid r\implies r= 3$. (*) But analyzing (1) again modulo 4, we have: $(p+r)^2\equiv r^2+1$ (mod 4). Similarly, we also have that a perfect square is 0 or 1 modulo 4, so $(p+r)^2\equiv 0+1$ or $1+1$ (mod 4). As we can't have the congruence 2, we must have $(p+r)^2\equiv 1$ (mod 4), and $r^2\equiv 0$ (mod 4), so $r$ must be 2. But by (*) we get $r= 3$. That's impossible! So, we can't have $p=q$ or $p=r$ or $q=r$. And then, we got what we wanted for now. Well, let's see what happens when $p>q>r>3$. As all the primes on LHS of (1) are greater than 3, we can write $p$, $q$ and $r$ as: $p= 6a\pm 1$ $q= 6b\pm 1$ $r= 6c\pm 1$, where $a,b,c\in\mathbb{Z*_{+}}$ We now have 4 cases to consider: spoiler: none of them work, but if you wanna check:Case 1: If all the primes are $\equiv 1$ (mod 6) So, $p= 6a+1, q= 6b+1, r= 6c+1$. Replacing in (1) and analyzing modulo 12, we have: $36ab+6a+6b+1+36ac+6a+6c+1+36bc+6b+6c+1\equiv 1$ (mod 12) $\implies 3\equiv 1$ (mod 12), false! Case 2: If one of the primes is $\equiv -1$ (mod 6) and the rest are $\equiv 1$ (mod 6). (Suppose WLOG $p\equiv -1$ (mod 6)) So, we have, analyzing modulo 12 in (1): $36ab+6a-6b-1+36ac+6a-6c-1+36bc+6b+6c+1\equiv 1$ (mod 12) $\implies -1\equiv 1$ (mod 12), which is false! Case 3: If two of those primes are $\equiv -1$ (mod 6) and one is $\equiv 1$ (mod 6). (Suppose WLOG $p, q\equiv -1$ (mod 6) and $r\equiv 1$ (mod 6)) So, again, analyzing modulo 12 in (1): $36ab-6a-6b+1+36ac+6a-6c-1+36bc+6b-6c-1\equiv 1$ (mod 12) $\implies -1\equiv 1$ (mod 12), which is false too!! Case 4: If all the primes are $\equiv -1$ (mod 6). Analyzing modulo 12 in (1): $36ab-6a-6b+1+36ac-6a-6c+1+36bc-6b-6c+1\equiv 1$ (mod 12) $\implies 3\equiv 1$ (mod 12), which is again false! After all these cases we got one conclusion: definitely, $p,q,r$ can't be all greater than 3. So, one of them (exactly one, because all of them are distinct) is 2 or 3. As we were ordering $p>q>r$, then we have two cases: 1) $r= 2$ If $r=2$, replacing in (1), we got $pq+2p+2q= 12k+1$. Analyzing modulo 3, $pq-p-q\equiv 1$ (mod 3) $\implies pq\equiv 1+p+q$ (mod 3). Here, there are some cases to test $p\equiv 0, \pm 1$ (mod 3). Well, we can see that if $p\equiv \pm 1$ (mod 3) $\implies \pm q\equiv 1\pm 1+q$ (mod 3). So, $q\equiv 2+q\implies 0\equiv 2$ (mod 3) (which is false) or $-q\equiv q\implies q\equiv 0$ (mod 3) $\implies q=3$. Replacing in (1): $3p+2p+6= 12k+1\implies 6+5p= 12k+1\implies 5p= 12k-5\implies 5\mid 12k\implies k= 5$ and $p= 11$ . Finally, we got a quadruple that actually works! $(p,q,r,k)= (11, 3, 2, 5)$ is a solution. Notice that $p\equiv 0$ (mod 3) gives a solution that will already be counted in the permutations of $(11,3,2)$, so we're done for $r=2$. 2) $r=3$ here I just checked if I missed any cases, but I didn't get anything newIf $r=3$, replacing in (1), we got $pq+3p+3q\equiv 12k+1$. Analyzing modulo 4, $pq-p-q\equiv 1$ (mod 4) $\implies pq\equiv 1+p+q$ (mod 4). As $p>r= 3\implies p$ is odd $\implies p\equiv 1$ or $3$ (mod 4). If $p\equiv 1$ (mod 4) $\implies q\equiv 2+q$ (mod 4) $\implies 0\equiv 2$ (mod 4), which is false. And if $p\equiv 3$ (mod 4) $\implies 3q\equiv q$ (mod 4) Also, as $q>r=3\implies q$ is odd $\implies gcd(q,4)= 1$. So, $3\equiv 1$ (mod 4), which is false! Therefore, the solutions are $(p,q,r,k)= (2, 3, 11, 5); (2, 11, 3, 5); (3, 11, 2, 5); (3, 2, 11, 5); (11, 2, 3, 5); (11, 3, 2, 5) $.