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 "2024 USAJMO Problems/Problem 3"

(Created page with "=== Problem === Let <math>a(n)</math> be the sequence defined by <math>a(1)=2</math> and <math>a(n+1)=(a(n))^{n+1}-1</math> for each integer <math>n\geq1</math>. Suppose that...")
 
m (→‎Solution 1)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
=== Problem ===
+
__TOC__
 +
 
 +
== Problem ==
 
Let <math>a(n)</math> be the sequence defined by <math>a(1)=2</math> and <math>a(n+1)=(a(n))^{n+1}-1</math> for each integer <math>n\geq1</math>. Suppose that <math>p>2</math> is prime and <math>k</math> is a positive integer. Prove that some term of the sequence <math>a(n)</math> is divisible by <math>p^k</math>.
 
Let <math>a(n)</math> be the sequence defined by <math>a(1)=2</math> and <math>a(n+1)=(a(n))^{n+1}-1</math> for each integer <math>n\geq1</math>. Suppose that <math>p>2</math> is prime and <math>k</math> is a positive integer. Prove that some term of the sequence <math>a(n)</math> is divisible by <math>p^k</math>.
 +
 +
== Solution 1 ==
 +
 +
Lemma <math>1</math>:
 +
 +
Given a prime <math>p</math>, a positive integer <math>k</math>, and an even <math>m</math> such that <math>p^k|a(m)</math>, we must have that <math>p^{k+1}|a(m+2)</math>.
 +
 +
 +
Proof of Lemma <math>1</math>:
 +
 +
<math>a(m+1)\equiv (a(m))^{m+1}-1\equiv -1 \mod p^{k+1}</math>
 +
 +
Then, <math>a(m+2)\equiv (a(m+1))^{m+2}-1\equiv (-1)^{m+2}-1\equiv 0 \mod p^{k+1}</math>
 +
 +
 +
Therefore, by induction, if there exists an even integer <math>m</math> such that <math>p|a(m)</math>, then for all integers <math>k</math>, <math>p^k|a(m+2k-2)</math>, so we are done if there exists an even <math>m</math> such that <math>p|a(m)</math>.
 +
 +
 +
Now, consider the case where there is some prime <math>p>2</math> such that there are no even integers <math>m</math> such that <math>p|a(m)</math>.
 +
 +
Lemma <math>2</math>:
 +
 +
In this case, we must have that <math>p|a(m)</math> if <math>m\equiv -1 \mod p-1</math> for all integers <math>m</math>.
 +
 +
Proof of Lemma <math>2</math>:
 +
 +
Suppose for the sake of contradiction that there exists some <math>m</math> such that <math>m\equiv -1\mod p-1</math> and <math>p</math> does not divide <math>a(m)</math>. Then, we have <math>a(m+1)\equiv (a(m))^{m+1}-1\equiv 1-1\equiv 0\mod p</math>, by Fermat's Little Theorem. Since for all <math>p>2</math>, <math>p-1</math> is even, then <math>m+1</math> would be even. However this results in a contradiction.
 +
 +
Then, we get that if <math>m\equiv -1\mod p-1</math>, then <math>0\equiv a(m)\equiv (a(m-1))^m-1\mod p\implies (a(m-1))^{m+1}\equiv 1\equiv a(m-1)\mod p</math>.
 +
 +
Then, by LTE, <math>v_p(a(m))=v_p((a(m-1))^m-1)=v_p(a(m-1)-1)+v_p(m)>v_p(m)</math>. Since <math>\gcd(p-1,p)=1</math>, then <math>\gcd(p-1,p^k)=1</math> for all positive integers <math>k</math>, so then by Chinese Remainder Theorem there exists integers <math>m</math> such that <math>m\equiv -1\mod p-1</math> and <math>m\equiv 0\mod p^k</math>, so we are done <math>\square</math>
 +
 +
 +
Remark: I think this is a very cool NT problem.
 +
 +
 +
-bronzetruck2016
 +
 +
==See Also==
 +
{{USAJMO newbox|year=2024|num-b=2|num-a=4}}
 +
{{MAA Notice}}

Latest revision as of 20:42, 19 July 2024

Problem

Let $a(n)$ be the sequence defined by $a(1)=2$ and $a(n+1)=(a(n))^{n+1}-1$ for each integer $n\geq1$. Suppose that $p>2$ is prime and $k$ is a positive integer. Prove that some term of the sequence $a(n)$ is divisible by $p^k$.

Solution 1

Lemma $1$:

Given a prime $p$, a positive integer $k$, and an even $m$ such that $p^k|a(m)$, we must have that $p^{k+1}|a(m+2)$.


Proof of Lemma $1$:

$a(m+1)\equiv (a(m))^{m+1}-1\equiv -1 \mod p^{k+1}$

Then, $a(m+2)\equiv (a(m+1))^{m+2}-1\equiv (-1)^{m+2}-1\equiv 0 \mod p^{k+1}$


Therefore, by induction, if there exists an even integer $m$ such that $p|a(m)$, then for all integers $k$, $p^k|a(m+2k-2)$, so we are done if there exists an even $m$ such that $p|a(m)$.


Now, consider the case where there is some prime $p>2$ such that there are no even integers $m$ such that $p|a(m)$.

Lemma $2$:

In this case, we must have that $p|a(m)$ if $m\equiv -1 \mod p-1$ for all integers $m$.

Proof of Lemma $2$:

Suppose for the sake of contradiction that there exists some $m$ such that $m\equiv -1\mod p-1$ and $p$ does not divide $a(m)$. Then, we have $a(m+1)\equiv (a(m))^{m+1}-1\equiv 1-1\equiv 0\mod p$, by Fermat's Little Theorem. Since for all $p>2$, $p-1$ is even, then $m+1$ would be even. However this results in a contradiction.

Then, we get that if $m\equiv -1\mod p-1$, then $0\equiv a(m)\equiv (a(m-1))^m-1\mod p\implies (a(m-1))^{m+1}\equiv 1\equiv a(m-1)\mod p$.

Then, by LTE, $v_p(a(m))=v_p((a(m-1))^m-1)=v_p(a(m-1)-1)+v_p(m)>v_p(m)$. Since $\gcd(p-1,p)=1$, then $\gcd(p-1,p^k)=1$ for all positive integers $k$, so then by Chinese Remainder Theorem there exists integers $m$ such that $m\equiv -1\mod p-1$ and $m\equiv 0\mod p^k$, so we are done $\square$


Remark: I think this is a very cool NT problem.


-bronzetruck2016

See Also

2024 USAJMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_USAJMO_Problems/Problem_3&oldid=223175"