Difference between revisions of "2017 USAJMO Problems/Problem 1"
Aopsuser101 (talk | contribs) (→Solution 3) |
|||
Line 17: | Line 17: | ||
{{MAA Notice}} | {{MAA Notice}} | ||
+ | |||
+ | ==Solution 4== | ||
+ | Let <math>a = 2x + 1</math> and <math>b = 2x-1</math>, where <math>x</math> leaves a remainder of <math>1</math> when divided by <math>4</math>.We seek to show that <math>(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4x</math> because that will show that there are infinitely many distinct pairs <math>(a,b)</math> of relatively prime 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>. | ||
+ | |||
+ | Claim 1: <math>(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4</math>. | ||
+ | We have that the remainder when <math>2x+1</math> is divided by <math>4</math> is <math>3</math> and the remainder when <math>2x-1</math> is divided by <math>4</math> is always <math>1</math>. Therefore, the remainder when <math>(2x+1)^{2x-1} + (2x-1)^{2x+1}</math> is divided by <math>4</math> is always going to be <math>(-1)^{2x-1} + 1^{2x+1} = 0</math>. | ||
+ | |||
+ | Claim 2: <math>(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod x</math> | ||
+ | We know that <math>(2x+1) \mod x \equiv 1</math> and <math>(2x-1) \mod x \equiv 3</math>, so the remainder when <math>(2x+1)^{2x-1} + (2x-1)^{2x+1}</math> is divided by <math>4</math> is always going to be <math>(-1)^{2x-1} + 1^{2x+1} = 0</math>. | ||
+ | |||
+ | Claim 3: <math>(2x+1)^{2x-1} + (2x-1)^{2x+1} \equiv 0 \mod 4x</math> | ||
+ | Trivial given claim <math>1,2</math>. <math>\boxed{}</math> | ||
==See also== | ==See also== | ||
{{USAJMO newbox|year=2017|beforetext=|before=First Problem|num-a=2}} | {{USAJMO newbox|year=2017|beforetext=|before=First Problem|num-a=2}} |
Revision as of 15:16, 19 February 2020
Problem
Prove that there are infinitely many distinct pairs of relatively prime integers and such that is divisible by .
Solution 1
Let and . We see that . Therefore, we have , as desired.
(Credits to mathmaster2012)
Solution 2
Let be odd where . We have so This means that and since x is odd, or as desired.
Solution 3
Because problems such as this usually are related to expressions along the lines of , it's tempting to try these. After a few cases, we see that is convenient due to the repeated occurrence of when squared and added. We rewrite the given expressions as: After repeatedly factoring the initial equation,we can get: Expanding each of the squares, we can compute each product independently then sum them: Now we place the values back into the expression: Plugging any positive integer value for into yields a valid solution, because there is an infinite number of positive integers, there is an infinite number of distinct pairs .
-fatant
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
Solution 4
Let and , where leaves a remainder of when divided by .We seek to show that because that will show that there are infinitely many distinct pairs of relatively prime integers and such that is divisible by .
Claim 1: . We have that the remainder when is divided by is and the remainder when is divided by is always . Therefore, the remainder when is divided by is always going to be .
Claim 2: We know that and , so the remainder when is divided by is always going to be .
Claim 3: Trivial given claim .
See also
2017 USAJMO (Problems • Resources) | ||
First Problem | Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |