Putnam 2001 A5

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

0 users

TOPICS

No tags match your search

M

No tags match your search

M

Putnam 2001 A5

G H J

Reveal topic tags

modular arithmetic

college contests

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6294 posts

#1 h Feb 26, 2012, 10:52 PM • 4 Y

Y by HWenslawski, son7, Adventure10, Mango247

Prove that there are unique positive integers $a$ , $n$ such that $a^{n+1}-(a+1)^n=2001$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1221 posts

tc1729

#2 h Feb 26, 2012, 11:02 PM • 3 Y

Y by HWenslawski, Adventure10, Mango247

Note that $2002 = 2\cdot 7\cdot 11\cdot 13$ . Taking the equation $\mod x$ gives that $0 - 1 \equiv 2001 \pmod{x}$ , so $x$ must be a divisor of $2002$ .

$x$ cannot be a multiple of $3$ , because then we would have $0 - 1 \equiv 0 \pmod{3}$ . Similarly, it cannot be $\equiv 2 \pmod{3}$ . So it must be $\equiv 1 \pmod{3}$ and $n$ must be even.

Taking the equation $\pmod{x+1}$ gives $(-1)\cdot\text{odd} \equiv 2001 \pmod{x+1}$ , so $x + 1$ must divide $2002$ . Hence $x = 1$ or $13$ . $x = 1$ is obviously not a solution, so the only possibility is $x = 13$ and we must find all solutions to $13n+1 - 14n = 2001$ .

There are obviously at most two solutions (since $13n+1 - 14n$ increases to a maximum, then decreases). It is also obvious that $n = 2$ is a solution. But it is not immediately obvious that there is not a second solution.

The trick is to work $\pmod 8$ . We then have $(4 + 1)\cdot\text{odd} - (-2)\cdot\text{even} = 1$ . If the even is greater than $2$ , then $2\cdot\text{even} \equiv 0 \pmod 8$ and we have a contradiction, because expanding $(4 + 1)\cdot\text{odd}$ we get $\text{zero terms} + \text{odd} \cdot 4 + 1 \equiv 5 \pmod 8$ . So the only possibility is $n = 2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1583 posts

#3 h Feb 26, 2012, 11:21 PM • 2 Y

Y by Adventure10, Mango247

Also here.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#4 h Feb 27, 2012, 12:46 AM • 1 Y

Y by Adventure10

Also here, in the Putnam forum. Please to follow that link for some additional arguments.

As I said there, this may be my all-time favorite "year" problem.

I thought that jmerry and I had written up a full set of answers to the 2001 Putnam back in 2001-2002, but from searching, it appears that if I ever had such a thing, I lost it in a file-storage mishap. I did find a fragment of an answer to A5, but everything in that is already posted at the link above.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6 posts

#5 h Apr 5, 2019, 4:28 PM • 1 Y

Y by Adventure10

My solution is slightly different from the Putnam Archive on the `existence' piece of the proof, but quite different on the `uniqueness' piece, so I wanted to share. I didn't come up with anywhere near as direct a proof on uniqueness. Sometimes I'm happy though when I miss the slick line of proof, yet still find something (longer!) that works.

Let $f_{n}\left( a \right) = a^{n + 1} - \left( a + 1 \right)^{n} \Rightarrow f_{n}\left( a \right) \equiv -1(mod\ a).$
$f_{n}\left( a \right) = 2001 \Rightarrow 2001 \equiv -1(mod\ a) \Rightarrow 2002 \equiv 0(mod\ a) \Rightarrow a | 2002$
Claim: $3|f_{n}(a) \Longrightarrow a \equiv 1\left( mod\ 3 \right)\ and\ n \equiv 0(mod\ 2)$
Proof: $gcd(a, a+1) = 1 \Rightarrow 3 \not|\ a\ and\ 3 \not|\ (a+1)\ \Rightarrow a \equiv 1(mod\ 3)$ $a \equiv 1 (mod\ 3) \Rightarrow f_{n}(a) \equiv 1 - 2^{n} \equiv 0 (mod\ 3) \Rightarrow n \equiv 0(mod\ 2)$ As 3| 2001, I can use the claim to show that that $f_{n}\left( a \right) = 2001\ \Rightarrow (a + 1)\ |\ 2002:$
$f_{n}(a) \equiv (-1)^{n + 1} \Rightarrow 2001 \equiv - 1 (mod\ (a+1)) because\ n \equiv 0\ mod\ 2$ $\Rightarrow 2002 \equiv 0\ \left( \text{mod\ }\left( a + 1 \right) \right) \Rightarrow \left( a + 1 \right)\ |\ 2002$
2002=2x7x11x13 has only one set of nontrivial consecutive factors, 13 and 14. Because both a and (a+1) must divide 2002, this
implies that a = 13. From inspection, we get $a = 13,n = 2 \Rightarrow f_{n}\left( a \right) = 2001$

This satisfies the existence part of the proof. To show uniqueness, I demonstrate that there is no value of n other than n = 2 that can yield $f_{n}\left( 13 \right) = 2001$ .

Proof is by contradiction. Let us assume that there is another such n:

${13^{3} - {14}^{2} = 13^{n + 1} - 14^{n} \Rightarrow 14^{2}\left( 14^{n - 2} - 1 \right) = {13}^{3}\left( {13}^{n - 2} - 1 \right)}$ ${\Rightarrow 13^{3}\ |\ (14^{n - 2} - 1) \Rightarrow \ 13^{2}\ |\ (14^{n - 3} + \ldots + 14 + 1)}$ Expressing 14 as (13 + 1), the above associated binomial expansion yields terms of the form $a_{i}13^{i}.$ We only need to consider the terms with exponent 1 or zero, as all other terms will mod out, yielding the following:
${14^{n - 3} + \ldots + 14 + 1 \equiv 1 \cdot \left( n - 2 \right) + 13\sum_{i = 1}^{n - 3}i\ \left( \text{mod\ }13^{2} \right)}$ ${\equiv \left( n - 2 \right) + \frac{13\left( n - 2 \right)\left( n - 3 \right)}{2}\ \left( \text{mod\ }13^{2} \right) \equiv \frac{n - 2}{2}\left( 13n - 37 \right) \equiv 0\ \left( \text{mod\ }13^{2} \right)}$ ${\Rightarrow 13^{2}\ |\ \left( n - 2 \right)\ \Rightarrow n > 13^{2}}$
From here, we show that $f_{n}\left( 13 \right) < 0\ if\ n > 13^{2}.$ This contradicts $f_{n}\left( 13 \right) = 2001$ , completing the proof.

${\left( 1 + \frac{1}{13} \right)^{n} > 1 + \frac{n}{13} > \frac{n}{13} > 13\ \ because\ n > 13^{2}}$ ${\left( \frac{14}{13} \right)^{n} > 13 \Rightarrow 14^{n} > 13^{n + 1} \Rightarrow {(13}^{n + 1} - 14^{n}) < 0 \Rightarrow f_{n}\left( 13 \right) < 0}$

This post has been edited 2 times. Last edited by sanjaym, Apr 5, 2019, 4:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

656 posts

#6 h Feb 17, 2022, 1:45 PM • 1 Y

Y by Ba_dalinaaa

The answer is $(a,n) = (13,2)$ , which works as $13^3 = 2197$ and $14^2 = 196$ .
Note $3$ must not divide $a,a+1$ . This forces $a \equiv 1 \pmod{3}$ Taking modulo $3$ forces
$n \text{ is even}$ Now taking modulo $a,a+1$ we get
$a,a+1 \mid 2001 + 1 = 2002 = 2 \cdot 7 \cdot 11 \cdot 13$ As $2002 \ge \text{lcm}(a,a+1) = a(a+1)$ , hence $a \le 44$ . Now the only divisors of $2002$ which are $\le 44$ are
$2,7,11,13,14,22,26$ Among these, $a+1 \mid 2002$ is satisfies by $a=13$ only. Now we want
$\begin{align*} 13^{n+1} - 14^n = 2001 \qquad \qquad (1) \\ \iff 13 = \frac{2001}{13^n} + \left( \frac{14}{13} \right)^n \qquad \qquad (2) \end{align*}$ Recall $n$ even. We already verified $n=2$ is a solution. FTSOC $n \ge 4$ . Taking modulo $13^3$ in $(1)$ gives
$13^3 \mid 14^n - 14^2 \implies 13^3 \mid 14^{n-2} - 1$ By LTE, this forces $13^2 \mid n-2$ , implying $n \ge 165$ . But then RHS of $(2)$ becomes very large, contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2113 posts

407420

#7 h Feb 17, 2022, 5:01 PM

Y by

Observe that $2002\equiv 0\pmod a$ . Now $a\equiv 0,2\pmod 3$ gives a contradiction, so $a\equiv 1\pmod 3$ , if $n$ is odd then $\mod 3$ again gives a contradiction, hence $n$ is even. Using this we get $a\equiv 0,2,3\pmod 4$ gives a contradiction, hence $a\equiv 1\pmod 4$ . From $2002\equiv 0\pmod a$ and $a\equiv 1\pmod 4$ we get $a$ can only be divisible by $7,11,13$ . Now $a\equiv 1\pmod 3$ implies that $11\nmid a$ , therefore $a\equiv 1\pmod 4$ implies that $7\nmid a$ . Hence either $a=1$ or $a=13$ , but $a=1$ doesn't work, therefore $a=13$ . If $n>2$ , then $\mod 16$ gives a contradiction, hence $n=2$ . Also, $(a,n)=(13,2)$ works.

This post has been edited 1 time. Last edited by 407420, Feb 17, 2022, 5:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Infinity_Integral

306 posts

Infinity_Integral

#8 h Oct 19, 2022, 9:42 AM

Y by

Taking mod $a$ ,
$-1 \equiv 2001 ( \mod a )$ Thus $a$ is a factor of $2002$ .

Note that $2002 = 2 \cdot 7 \cdot 11 \cdot 13$ .
When $n=1$ , $a \notin \mathbb{Z^+}$ , no soln.

$a^{n+1} - (a+1)^n \geq a^3 - a^2 - 2a - 1 > 2001 \forall a>13$ Thus $a \leq 13$ .

Therefore $a=1,2,7,11,13$ only.
Testing through all these cases, we find the only soln occurs at $(13,2)$ ,
Otherwise $a \notin \mathbb{Z^+} \forall a \neq 13$ .

Thus we conclude the unique soln to be $(13,2)$ .
$\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Happymathematics

81 posts

Happymathematics

#9 h Oct 19, 2022, 10:09 AM • 1 Y

Y by Mango247

I think that we can prove easy, that th function $f(x)=x^{n+1}-(x+1)^n$ it is increasing, so the LHS it is increasing, the RHS constant, so we have maximum obe solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Infinity_Integral

306 posts

Infinity_Integral

#10 h Oct 19, 2022, 10:16 AM • 2 Y

Y by Mango247, Mango247

Happymathematics wrote:

I think that we can prove easy, that th function $f(x)=x^{n+1}-(x+1)^n$ it is increasing, so the LHS it is increasing, the RHS constant, so we have maximum obe solution.

no cos the function is in 2 variables so your argument actually gives infinitely many points but we need to prove only 1 is a lattice point. think of graphing a curve.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#11 h Oct 20, 2022, 7:54 AM

Y by

First, $a\mid 2002$ . And $a\equiv 0,2\pmod 3$ fails, so $a\equiv 1\pmod 3$ . Now $n$ is even, so $a+1\mid 2002$ . Among factors of $2002$ , only $a=13$ works. Taking modulo $8$ forces $n=2$ . Clearly $(a,n)=(13,2)$ works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#12 h Nov 4, 2022, 3:37 PM

Y by

By taking modulo $a$ we get that $a \mid 2002$ , and by taking modulo $a+1$ we get that $a+1 \mid 2022$ if $n$ is even and $a+1 \mid 2020$ otherwise. We can check that this either gives $a=13$ or $a=7$ .
For the case of $a=13$ , note that $n=2$ works. No solutions exist to $13^x \equiv 2001 \pmod{343\cdot 8}$ , so we cannot have solutions for $n \geq 3$ (if you want, I guess you can use the binomial formula to prove this part).
For the case of $a=7$ , no solutions exist by $\bmod{5}$ .
Thus the only solution is $(a,n)=(13,2)$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lifeismathematics

1188 posts

lifeismathematics

#13 h Mar 28, 2024, 9:41 AM

Y by

cool problem , we expand binomially to observe that $a|2001$ , now taking $\pmod 3$ it also forces that $3\nmid a , 3\nmid a+1$ , so only posisble values of $a$ can be $13,7,91$ . Now we observe that taking ${\pmod a}$ we must have $n$ to be even. Now taking mod $a+1$ on the given equation we have $2002 \equiv 0 \pmod{a+1}$ and hence we have $a|2002 , a+1|2002 \implies a=13$ , now:

$13^{n+1}-14^{n}=2001$ , we must have $13^{n+1}>14^{n} \implies n<34$ , upon checking we can check only $n=2$ works.

This post has been edited 4 times. Last edited by lifeismathematics, Mar 28, 2024, 9:42 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

214 posts

#14 h Apr 6, 2025, 10:36 PM

Y by

Sketch:
check $a^{n+1}-(a+1)^n \equiv$ -1 (mod $a)$ and $a^{n+1}-(a+1)^n \equiv$ -1 (mod $a+1)$

conclude that $a,a+1\mid 2002$
check divisors of $\textbf{2002}$ . we find that the only 2 divisors that are consecutive are $13,14$

it will only have one solution, and $n$ must be $\geq 1$ , therefore (13,2) is the only answer $\blacksquare$
:starwars:

:starwars:

ps: these are the divisors of 2002

This post has been edited 7 times. Last edited by Levieee, Apr 21, 2025, 7:05 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a