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 "2017 USAJMO Problems/Problem 1"

m (→‎Solution 2)
m (→‎Solution 2)
Line 10: Line 10:
 
==Solution 2==
 
==Solution 2==
 
Let <math>x</math> be any odd number above 1. We have <math>x^2-1=(x-1)(x+1).</math> Since <math>x-1</math> is even, <math>x^2-1 \equiv 0 \pmod{2x+2}.</math> This means that  <math>x^{x+2}-x^x \equiv 0 \pmod{2x+2},</math> and since x is odd, <math>x^{x+2}+(-x)^x \equiv 0 \pmod{2x+2},</math> or <math>x^{x+2}+x+2^x \equiv 0 \pmod{2x+2}.</math> This means for any odd x, the ordered triple <math>(x,x+2)</math> satisfies the condition. Since there are infinitely many values of <math>x</math> possible, there are infinitely many ordered triples, as desired.  
 
Let <math>x</math> be any odd number above 1. We have <math>x^2-1=(x-1)(x+1).</math> Since <math>x-1</math> is even, <math>x^2-1 \equiv 0 \pmod{2x+2}.</math> This means that  <math>x^{x+2}-x^x \equiv 0 \pmod{2x+2},</math> and since x is odd, <math>x^{x+2}+(-x)^x \equiv 0 \pmod{2x+2},</math> or <math>x^{x+2}+x+2^x \equiv 0 \pmod{2x+2}.</math> This means for any odd x, the ordered triple <math>(x,x+2)</math> satisfies the condition. Since there are infinitely many values of <math>x</math> possible, there are infinitely many ordered triples, as desired.  
−
 
−
(Credits to kingofgeedorah, 2016 MATHCOUNTS Champion)
 
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 18:41, 19 April 2017

Problem

Prove that there are infinitely many distinct pairs $(a,b)$ of relatively prime integers $a>1$ and $b>1$ such that $a^b+b^a$ is divisible by $a+b$.

Solution 1

Let $a = 2n-1$ and $b = 2n+1$. We see that $(2n \pm 1)^2 = 4n^2-4n+1 \equiv 1 \pmod{4n}$. Therefore, we have $(2n+1)^{2n-1} + (2n-1)^{2n+1} \equiv 2n + 1 + 2n - 1 = 4n \equiv 0 \pmod{4n}$, as desired.

(Credits to laegolas)

Solution 2

Let $x$ be any odd number above 1. We have $x^2-1=(x-1)(x+1).$ Since $x-1$ is even, $x^2-1 \equiv 0 \pmod{2x+2}.$ This means that $x^{x+2}-x^x \equiv 0 \pmod{2x+2},$ and since x is odd, $x^{x+2}+(-x)^x \equiv 0 \pmod{2x+2},$ or $x^{x+2}+x+2^x \equiv 0 \pmod{2x+2}.$ This means for any odd x, the ordered triple $(x,x+2)$ satisfies the condition. Since there are infinitely many values of $x$ possible, there are infinitely many ordered triples, as desired.

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2017 USAJMO (Problems • Resources)
First Problem Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_USAJMO_Problems/Problem_1&oldid=85310"