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 == | ||
− | {{ | + | 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 such that
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
The given is equivalent to . Notice that only zero or one of
can be even since otherwise, the left-hand side would be divisible by
when the right-hand side is not. Then WLOG let
and
be odd primes. If
is also an odd prime, then taking mod
of both sides results in
, which is obviously not true; thus
. Then
, so taking mod
results in
.
Let and
; by trial and error, the only solutions to the equation are
; this would imply that
. However, notice that due to mod
, one of
must be divisible by
when analyzing the four solutions. Both
and
would require one of
to be divisible by
but not equal to
itself (since
); thus we only consider
.
WLOG consider . Then
, so the initial equation becomes
. This implies that
, so
and
. Thus the solutions to the equation are
.