Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 $(a, b)$ of positive integers such that $2a + 1$ and $2b - 1$ are relative primes and $a + b$ divides $4ab + 1$.

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

Solution

We are given that $a+b$ divides $4ab+1$; thus $a+b$ must also divide $4ab+2(a+b)+1=(2a+1)(2b+1)$. But notice that since $\gcd(2a+1,2b-1)=1$, by the Euclidean Algorithm, we must also have \[\gcd(2a+1,2b-1)=\gcd((2a+1,(2a+1)+(2b-1))=\gcd(2a+1,2(a+b))=1\] Clearly $2\nmid 2a+1$; thus $\gcd(a+b,2a+1)=1$. Therefore, from earlier, we know that $(a+b)|(2a+1)(2b+1)$; what we just found implies that \[(a+b)|(2b+1)\] This fact is equivalent to \[\frac{2b+1}{a+b}\in\mathbb{Z}\] But \[\frac{2b+1}{a+b}=1+\frac{b-a+1}{a+b}\] which implies that \[\frac{b-a+1}{a+b}\in\mathbb{Z}\] Let the expression above equal some integer $k$. Rearranging gives us the equation \[a(k+1)+b(k-1)=1\] If $k\ge1$, then \[a(k+1)+b(k-1)\ge2a\ge2>1\] a contradiction. Similarly, if $k\le-1$, then \[a(k+1)+b(k-1)\le -2b\le -2<1\] also a contradiction, which implies that $k=0$. Substituting into the above yields $a-b=1$.

Finally, we check that these solutions work. If $a-b=1$, then $a+b=2b+(a-b)=2b+1$, and \[4ab+1=4(b+1)b+1=4b^2+4b+1=(2b+1)^2\] thus the condition is clearly true, so our solution set is $\boxed{(t+1,t)}$ for all positive integers $t$.

~ eevee9406

See also

OIM Problems and Solutions

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_OIM_Problems/Problem_4&oldid=246403"