Difference between revisions of "2016 OIM Problems/Problem 1"

(Created page with "== Problem == Find all positive prime numbers <math>p, q, r, k</math> such that <cmath>pq + qr + rp = 12k + 1</cmath> ~translated into English by Tomas Diaz. ~orders@tomasdi...")
 
 
Line 7: Line 7:
  
 
== Solution ==
 
== Solution ==
{{solution}}
+
The given is equivalent to <math>(p+r)(q+r)=r^2+12k+1</math>. Notice that only zero or one of <math>p,q,r</math> can be even since otherwise, the left-hand side would be divisible by <math>2</math> when the right-hand side is not. Then WLOG let <math>p</math> and <math>q</math> be odd primes. If <math>r</math> is also an odd prime, then taking mod <math>4</math> of both sides results in <math>0\equiv2</math>, which is obviously not true; thus <math>r=2</math>. Then <math>(p+2)(q+2)=12k+5</math>, so taking mod <math>12</math> results in <math>(p+2)(q+2)\equiv5\hspace{2mm}(\text{mod}\hspace{1mm}12)</math>.
 +
 
 +
Let <math>a=p+2</math> and <math>b=q+2</math>; by trial and error, the only solutions to the equation are <math>(a,b)=(1,5),(5,1),(7,11),(11,7)</math>; this would imply that <math>(p,q)=(11,3),(3,11),(5,9),(9,5)</math>. However, notice that due to mod <math>12</math>, one of <math>p,q</math> must be divisible by <math>3</math> when analyzing the four solutions. Both <math>(5,9)</math> and <math>(9,5)</math> would require one of <math>p,q</math> to be divisible by <math>3</math> but not equal to <math>3</math> itself (since <math>3\not\equiv9</math>); thus we only consider <math>(11,3),(3,11)</math>.
 +
 
 +
WLOG consider <math>(p,q)\equiv(11,3)</math>. Then <math>q=3</math>, so the initial equation becomes <math>5p=12k-5</math>. This implies that <math>5|k</math>, so <math>k=5</math> and <math>p=11</math>. Thus the solutions to the equation are <math>\boxed{(p,q,r,k)=(11,3,2,5)\text{ and permutations of }p,q,r}</math>.
 +
 
 +
~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406]
  
 
== See also ==
 
== See also ==
 
[[OIM Problems and Solutions]]
 
[[OIM Problems and Solutions]]

Latest revision as of 11:40, 20 March 2025

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

See also

OIM Problems and Solutions