2016 OIM Problems/Problem 1

Problem

Find all positive prime numbers $p, q, r, k$ such that

$pq + qr + rp = 12k + 1$

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

The given is equivalent to $(p+r)(q+r)=r^2+12k+1$ . Notice that only zero or one of $p,q,r$ can be even since otherwise, the left-hand side would be divisible by $2$ when the right-hand side is not. Then WLOG let $p$ and $q$ be odd primes. If $r$ is also an odd prime, then taking mod $4$ of both sides results in $0\equiv2$ , which is obviously not true; thus $r=2$ . Then $(p+2)(q+2)=12k+5$ , so taking mod $12$ results in $(p+2)(q+2)\equiv5\hspace{2mm}(\text{mod}\hspace{1mm}12)$ .

Let $a=p+2$ and $b=q+2$ ; by trial and error, the only solutions to the equation are $(a,b)=(1,5),(5,1),(7,11),(11,7)$ ; this would imply that $(p,q)=(11,3),(3,11),(5,9),(9,5)$ . However, notice that due to mod $12$ , one of $p,q$ must be divisible by $3$ when analyzing the four solutions. Both $(5,9)$ and $(9,5)$ would require one of $p,q$ to be divisible by $3$ but not equal to $3$ itself (since $3\not\equiv9$ ); thus we only consider $(11,3),(3,11)$ .

WLOG consider $(p,q)\equiv(11,3)$ . Then $q=3$ , so the initial equation becomes $5p=12k-5$ . This implies that $5|k$ , so $k=5$ and $p=11$ . Thus the solutions to the equation are $\boxed{(p,q,r,k)=(11,3,2,5)\text{ and permutations of }p,q,r}$ .

~ eevee9406

Page

Toolbox

Search

2016 OIM Problems/Problem 1

Problem

Solution

See also