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 "2005 IMO Problems/Problem 4"

(→‎Solution)
(→‎Solution)
(7 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
==Problem==
 +
 
Determine all positive integers relatively prime to all the terms of the infinite sequence <cmath> a_n=2^n+3^n+6^n -1,\ n\geq 1. </cmath>
 
Determine all positive integers relatively prime to all the terms of the infinite sequence <cmath> a_n=2^n+3^n+6^n -1,\ n\geq 1. </cmath>
  
 
==Solution==
 
==Solution==
  
−
For all primes <math>p</math> greater than <math>3</math>, by Fermat's last theorem, <math>n^{p-1} = 1</math> mod <math>p</math> if <math>n</math> and <math>p</math> are relatively prime. This means that <math>n^{p-3} = \frac{1}{n^2}</math> mod <math>p</math>. Plugging <math>n = p-3</math> back into the equation, we see that the value mod <math>p</math> is simply <math>\frac{2}{9} + \frac{3}{4} + \frac{1}{36} - 1 = 0</math>. Thus, the expression is divisible by <math>p</math>. Because the expression is clearly never divisible by <math>2</math> or <math>3</math>, our answer is all numbers of the form <math>2^a3^b</math>.
+
Let <math>k</math> be a positive integer that satisfies the given condition.
 +
 
 +
For all primes <math>p>3</math>, by [[Fermat's Little Theorem]], <math>n^{p-1} \equiv 1\pmod p</math> if <math>n</math> and <math>p</math> are relatively prime. This means that <math>n^{p-3} \equiv \frac{1}{n^2} \pmod p</math>. Plugging <math>n = p-3</math> back into the equation, we see that the value<math>\mod p</math> is simply <math>\frac{2}{9} + \frac{3}{4} + \frac{1}{36} - 1 = 0</math>. Thus, the expression is divisible by all primes <math>p>3.</math> Since <math>a_2 = 48 = 2^4 \cdot 3,</math> we can conclude that <math>k</math> cannot have any prime divisors. Therefore, our answer is only <math>1.</math>
 +
 
 +
==See Also==
 +
 
 +
{{IMO box|year=2005|num-b=3|num-a=5}}

Revision as of 22:14, 25 November 2023

Problem

Determine all positive integers relatively prime to all the terms of the infinite sequence \[a_n=2^n+3^n+6^n -1,\ n\geq 1.\]

Solution

Let $k$ be a positive integer that satisfies the given condition.

For all primes $p>3$, by Fermat's Little Theorem, $n^{p-1} \equiv 1\pmod p$ if $n$ and $p$ are relatively prime. This means that $n^{p-3} \equiv \frac{1}{n^2} \pmod p$. Plugging $n = p-3$ back into the equation, we see that the value$\mod p$ is simply $\frac{2}{9} + \frac{3}{4} + \frac{1}{36} - 1 = 0$. Thus, the expression is divisible by all primes $p>3.$ Since $a_2 = 48 = 2^4 \cdot 3,$ we can conclude that $k$ cannot have any prime divisors. Therefore, our answer is only $1.$

See Also

2005 IMO (Problems) • Resources
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 5
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_IMO_Problems/Problem_4&oldid=205852"