Difference between revisions of "2006 OIM Problems/Problem 4"
(Created page with "== Problem == Find all pairs <math>(a, b)</math> of positive integers such that <math>2a + 1</math> and <math>2b - 1</math> are relative primes and <math>a + b</math> divides...") |
(solution) |
||
Line 5: | Line 5: | ||
== Solution == | == Solution == | ||
− | {{solution} | + | We are given that <math>a+b</math> divides <math>4ab+1</math>; thus <math>a+b</math> must also divide <math>4ab+2(a+b)+1=(2a+1)(2b+1)</math>. But notice that since <math>\gcd(2a+1,2b-1)=1</math>, by the [[Euclidean Algorithm]], we must also have |
+ | <cmath>\gcd(2a+1,2b-1)=\gcd((2a+1,(2a+1)+(2b-1))=\gcd(2a+1,2(a+b))=1</cmath> | ||
+ | Clearly <math>2\nmid 2a+1</math>; thus <math>\gcd(a+b,2a+1)=1</math>. Therefore, from earlier, we know that <math>(a+b)|(2a+1)(2b+1)</math>; what we just found implies that | ||
+ | <cmath>(a+b)|(2b+1)</cmath> | ||
+ | This fact is equivalent to | ||
+ | <cmath>\frac{2b+1}{a+b}\in\mathbb{Z}</cmath> | ||
+ | But | ||
+ | <cmath>\frac{2b+1}{a+b}=1+\frac{b-a+1}{a+b}</cmath> | ||
+ | which implies that | ||
+ | <cmath>\frac{b-a+1}{a+b}\in\mathbb{Z}</cmath> | ||
+ | Let the expression above equal some integer <math>k</math>. Rearranging gives us the equation | ||
+ | <cmath>a(k+1)+b(k-1)=1</cmath> | ||
+ | If <math>k\ge1</math>, then | ||
+ | <cmath>a(k+1)+b(k-1)\ge2a\ge2>1</cmath> | ||
+ | a contradiction. Similarly, if <math>k\le-1</math>, then | ||
+ | <cmath>a(k+1)+b(k-1)\le -2b\le -2<1</cmath> | ||
+ | also a contradiction, which implies that <math>k=0</math>. Substituting into the above yields <math>a-b=1</math>. | ||
+ | |||
+ | Finally, we check that these solutions work. If <math>a-b=1</math>, then <math>a+b=2b+(a-b)=2b+1</math>, and | ||
+ | <cmath>4ab+1=4(b+1)b+1=4b^2+4b+1=(2b+1)^2</cmath> | ||
+ | thus the condition is clearly true, so our solution set is <math>\boxed{(t+1,t)}</math> for all positive integers <math>t</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 21:58, 9 April 2025
Problem
Find all pairs of positive integers such that
and
are relative primes and
divides
.
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
We are given that divides
; thus
must also divide
. But notice that since
, by the Euclidean Algorithm, we must also have
Clearly
; thus
. Therefore, from earlier, we know that
; what we just found implies that
This fact is equivalent to
But
which implies that
Let the expression above equal some integer
. Rearranging gives us the equation
If
, then
a contradiction. Similarly, if
, then
also a contradiction, which implies that
. Substituting into the above yields
.
Finally, we check that these solutions work. If , then
, and
thus the condition is clearly true, so our solution set is
for all positive integers
.