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 2"

(Created page with "{{MAA Notice}} ==See also== {{USAJMO newbox|year=2017|num-b=1|num-a=3}}")
 
Line 1: Line 1:
 +
==Problem:==
 +
Prove that there are infinitely many distinct pairs <math>(a,b)</math> of relatively prime positive integers <math>a > 1</math> and <math>b > 1</math> such that <math>a^b + b^a</math> is divisible by <math>a + b</math>.
 +
 +
==Solution==
 +
Let <math>a = 2^n - 1</math> and <math>b = 2^n + 1</math>. We see that <math>a</math> and <math>b</math> are relatively prime (they are consecutive positive odd integers).
 +
 +
Lemma: <math>(2^k + 1)^{-1} \equiv 2^k + 1 \pmod{2^{k+1}}</math>.
 +
 +
Since every number has a unique modular inverse, the lemma is equivalent to proving that <math>(2^k+1)^2 \equiv 1 \pmod{2^{k+1}}</math>. Expanding, we have the result.
 +
 +
Substituting for <math>a</math> and <math>b</math>, we have
 +
<cmath>(2^k+1)^{2^k-1} + (2^k-1)^{2^k+1} \equiv 2^k - 1 + 2^k + 1 \equiv 0 \pmod{2^{k+1}},</cmath>
 +
where we use our lemma and the Euler totient theorem: <math>a^\phi{n} \equiv 1 \pmod{n}</math> when <math>a</math> and <math>n</math> are relatively prime.
 +
 
{{MAA Notice}}
 
{{MAA Notice}}
  
 
==See also==
 
==See also==
 
{{USAJMO newbox|year=2017|num-b=1|num-a=3}}
 
{{USAJMO newbox|year=2017|num-b=1|num-a=3}}

Revision as of 18:10, 19 April 2017

Problem:

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

Solution

Let $a = 2^n - 1$ and $b = 2^n + 1$. We see that $a$ and $b$ are relatively prime (they are consecutive positive odd integers).

Lemma: $(2^k + 1)^{-1} \equiv 2^k + 1 \pmod{2^{k+1}}$.

Since every number has a unique modular inverse, the lemma is equivalent to proving that $(2^k+1)^2 \equiv 1 \pmod{2^{k+1}}$. Expanding, we have the result.

Substituting for $a$ and $b$, we have \[(2^k+1)^{2^k-1} + (2^k-1)^{2^k+1} \equiv 2^k - 1 + 2^k + 1 \equiv 0 \pmod{2^{k+1}},\] where we use our lemma and the Euler totient theorem: $a^\phi{n} \equiv 1 \pmod{n}$ when $a$ and $n$ are relatively prime.

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)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2017_USAJMO_Problems/Problem_2&oldid=85288"