Problem 4 IMO 2005 (Day 2)

The post below has been deleted. Click to close.

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

Valentin Vornicu

7301 posts

Valentin Vornicu

#1 h Jul 14, 2005, 4:13 PM • 6 Y

Y by Davi-8191, Adventure10, megarnie, itslumi, Mango247, and 1 other user

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.$

This post has been edited 1 time. Last edited by Valentin Vornicu, Oct 2, 2005, 8:32 PM

Z K Y

The post below has been deleted. Click to close.

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

Fedor Petrov

520 posts

Fedor Petrov

#2 h Jul 14, 2005, 4:57 PM • 12 Y

Y by kgo, raknum007, OlympusHero, myh2910, JVAJVA, Adventure10, megarnie, ZhuTao, sabkx, Mango247, and 2 other users

It is not locked? Participants may not read our messages? Thank you for rapidity, Valentin!

For this problem, I think answer is only $1$ and it is clear, since for any prime $p>3$ we have $2^{p-2}+3^{p-2}+6^{p-2}-1$ is divisible by $p$ by Fermat Small Theorem ( $a^{p-2}\equiv 1/a$ , while $1/2+1/3+1/6-1=0$ ). For $n=2$ we have $a_n=48$ and so it is divisible by 6.

Z K Y

The post below has been deleted. Click to close.

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

Fedor Petrov

520 posts

Fedor Petrov

#3 h Jul 14, 2005, 5:16 PM • 2 Y

Y by Adventure10, Mango247

Another very easy problem, two others are not much harder. I predict cutoff for a Gold around 35 points.

Z K Y

The post below has been deleted. Click to close.

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

Adalbert

42 posts

Adalbert

#4 h Jul 14, 2005, 7:11 PM • 2 Y

Y by Adventure10, Mango247

Mine solution is similarly to yours:

if n is prime then by li'l Fermat we have:
a n-1=2^(n-1)+ 3^(n-1) + 6^(n-1) - 1 leaves remainder 2 (mod n), for n>=3. (*)
But for n=3 we have a2=48 which is divisible by 3 and becase of (*) we have contradiction.
Therefore, there is no prime solution so there is no solution at all.

I hope that i didn't made some stupid mistake.

Z K Y

The post below has been deleted. Click to close.

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

idioteque

75 posts

idioteque

#5 h Jul 15, 2005, 1:25 AM • 3 Y

Y by Adventure10, Mango247, PuzzlingCane

Fedor Petrov wrote:

It is not locked? Participants may not read our messages? Thank you for rapidity, Valentin!

For this problem, I think answer is only $1$ and it is clear, since for any prime $p>3$ we have $2^{p-2}+3^{p-2}+6^{p-2}-1$ is divisible by $p$ by Fermat Small Theorem ( $a^{p-2}\equiv 1/a$ , while $1/2+1/3+1/6-1=0$ ). For $n=2$ we have $a_n=48$ and so it is divisible by 6.

Same solutions as yours, except that I wrote it a bit differently because I'm not used to write stuff like $2^{p-2}\equiv\frac{1}{2}$ because it doesn't seem ok (I mean $2^3\equiv\frac{1}{2}$ would mean that 5 divides 15/2 from the definition of congruence).. So I wrote it like this $2^{p-2}=\frac{px+1}{2}, 3^{p-2}=\frac{py+1}{3}, 5^{p-2}=\frac{pz+1}{5}$ and then we get $a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1=\frac{3px+3+2py+2+pz+1}{6}-1=\frac{3px+2py+pz}{6}$ which is obviously divisible by p (for p>=5), and beacuse $a_1=10$ and $a_2=48$ we see that there's no solution in prime numbers..

Z K Y

The post below has been deleted. Click to close.

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

Fedor Petrov

520 posts

Fedor Petrov

#6 h Jul 15, 2005, 4:49 AM • 2 Y

Y by Adventure10, Mango247

No, it looks OK, though may be not usual for one seing it first time. In a ring of residues modulo $n$ those residues coprime to $n$ are invertible, i.e. if $a$ and $n$ are coprime, then there exists $a'$ such that $a\cdot a'\equiv 1$ modulo $n$ . So, if we write $b/a$ , we mean $b\cdot a'$ .

Z K Y

The post below has been deleted. Click to close.

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

thabit

9 posts

thabit

#7 h Jul 15, 2005, 10:50 AM • 2 Y

Y by Adventure10, Mango247

idioteque wrote:

Same solutions as yours, except that I wrote it a bit differently because I'm not used to write stuff like $2^{p-2}\equiv\frac{1}{2}$ because it doesn't seem ok (I mean $2^3\equiv\frac{1}{2}$ would mean that 5 divides 15/2 from the definition of congruence)..

So if you work with rationals you should interpret "p/q=0 mod m" as "m divides p and is coprime to q".

Z K Y

The post below has been deleted. Click to close.

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

nttu

486 posts

nttu

#8 h Jul 15, 2005, 4:18 PM • 2 Y

Y by Adventure10, Mango247

Strange

! I think this is the easiest Number theory problem in IMO .
The most difficult part : Predict with each prime $p >3$ : $2^{p-2}+3^{p-2}+6^{p-2} -1$ is divisible by $p$ (It's proved easily by Fermat Little Theorem)

I think the 2nd day is easier than the 1st day

Z K Y

The post below has been deleted. Click to close.

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

vnmathboy

33 posts

vnmathboy

#9 h Jul 16, 2005, 10:26 AM • 2 Y

Y by Adventure10, Mango247

For any prime

p>3

x=2^{p-2}, y=3^{p-2}, z=6^{p-2}

Since

2x\equiv 3y\equiv 6z (\equiv 1) (\mod p)

and

\gcd(p,2)=\gcd(p,3)=1

We have

x\equiv 3z, y\equiv 2z (\mod p)

So

x+y+z\equiv 6z\equiv 1 (\mod p)

or

p|a_{p-2}

Z K Y

The post below has been deleted. Click to close.

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

Johann Peter Dirichlet

376 posts

Johann Peter Dirichlet

#10 h Aug 1, 2005, 11:38 AM • 8 Y

Y by Pure_IQ, MeowX2, Kanep, Aarth, ILOVEMYFAMILY, Adventure10, Mango247, Awanglnc

My solution is very similar to yours:

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

Yimin Ge

253 posts

Yimin Ge

#11 h Aug 5, 2005, 9:34 PM • 6 Y

Y by enndb0x, dchenmathcounts, Adventure10, ZhuTao, TheYJZ, and 1 other user

I've got another (more or less) nice solution:

The main idea is to make a recursion of that explicit term for $a_n$ .
It is given that $a_n=2^n+3^n+6^n+(-1)*1^n$ , so the 4 solutions for the characteristic equality $q^4+A*q^3+B*q^2+C*q+D$ are $1, 2, 3, 6$
We still have to calculate the coefficients A, B, C, D which is done easily by Vieta:
$D=1*2*3*6=36$
$C=-(1*2*3+2*3*6+1*3*6+1*2*6)=-72$
$B=1*2+1*3+1*6+2*3+2*6+3*6=47$
$A=-(1+2+3+6)=-12$
We therefore get $a_{n+4}=12a_{n+3}-47a_{n+2}+72a_{n+1}-36a_n$
By calculating the first 4 values for $a_n$ by the explicit term, we get
$a_1=10$
$a_2=48$
$a_3=250$
$a_4=1392$
And now we can calculate (and this time without any concerns about calculating with rational numbers) $a_0=2$ and $a_{-1}=0$ .
As $a_n$ is unique in both directions modulo any prime, 0 will appear again. Therefore 1 is the only solution.

Yimin

Z K Y

The post below has been deleted. Click to close.

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

Pascual2005

1160 posts

Pascual2005

#12 h Aug 5, 2005, 9:46 PM • 1 Y

Y by Adventure10

thatw as also the solution I gave in the contest...

Z K Y

The post below has been deleted. Click to close.

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

Pascual2005

1160 posts

Pascual2005

#13 h Aug 5, 2005, 9:48 PM • 1 Y

Y by Adventure10

Yimin Ge wrote:

As $a_n$ is unique in both directions modulo any prime, 0 will appear again. Therefore 1 is the only solution.

Yimin

modulo any prime not dividing $36$ !!!!!!!!!

Z K Y

The post below has been deleted. Click to close.

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

silouan

3952 posts

silouan

#14 h Aug 6, 2005, 2:20 PM • 2 Y

Y by Adventure10, Mango247

The number $a_n=2^n+3^n+6^n -1$ , $n\geq 1$ is a complex number so we are done

Z K Y

The post below has been deleted. Click to close.

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

silouan

3952 posts

silouan

#15 h Aug 6, 2005, 2:22 PM • 2 Y

Y by Adventure10, Mango247

complex I mean that it is not an odd number

Z K Y

The post below has been deleted. Click to close.

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

dolphinday

1324 posts

dolphinday

#119 h Jan 7, 2024, 6:56 PM

Y by

It's crazy you can do this.
$\newline$

We can prove that for some arbitrary $p$ , there is a $n$ so that
$2^n + 3^n + 6^n - 1 \equiv 0\pmod{p}$ Let $n \equiv -1 \pmod{p-1}$ .
Then
$\frac{1}{2} + \frac{1}{3} + \frac{1}{6} - 1 \equiv 0\pmod{p}$ so $a_n$ is divisible by every prime at some point.
Hence, our answer is $1$ .

Z K Y

The post below has been deleted. Click to close.

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

peace09

5419 posts

peace09

#120 h Jan 10, 2024, 9:35 PM

Y by

aehrignjadfalsdkjfnsdkaslkdjffasdf

Z K Y

The post below has been deleted. Click to close.

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

zaidova

87 posts

zaidova

#121 h Jan 30, 2024, 11:01 AM • 2 Y

Y by monoditetra, Leparolelontane

It is enough to find a prime number p p/an= pow(2,n) + pow(3,n) + pow(6,n) -1

a2= 2² + 3² + 6² - 1= 4+9+36-1=48
p=2, p=3
For p>=5
From Fermat's little theorem;

Pow(2, p-1)== pow(3, p-1) == pow( 6, p-1) (mod p)

6* ( pow( 2, p-2) + pow( 3, p-2) + pow( 6, p-2) -1)==0 (mod p)

So, p / 6* a(p-2) , also (p;6)=1 so, p / a(p-2)

This post has been edited 1 time. Last edited by zaidova, Jan 21, 2025, 10:25 AM

Z K Y

The post below has been deleted. Click to close.

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

Spectator

657 posts

Spectator

#122 h Feb 8, 2024, 11:07 PM • 1 Y

Y by megarnie

If we find all primes such that $p \not \mid a_{i}$ for all $i$ , we can construct every set with them. However, note that
$a_{p-2} \equiv \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1 \equiv 0\pmod{p}$ for all $p\neq 2, 3$ . It's easy to see that $2$ and $3$ divides $a_1$ and $a_2$ respectively. Thus, the only such $n$ is $1$ .

Z K Y

The post below has been deleted. Click to close.

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

de-Kirschbaum

198 posts

de-Kirschbaum

#123 h May 30, 2024, 9:57 PM

Y by

We claim that the sequence $\{a_n\}$ contains all primes.

Consider a prime $p$ . If $p=2$ then we have $3^n \equiv 1 \mod(2)$ which is true for any $n$ . If $p=3$ then we have $2^n \equiv 1 \mod(3)$ which is true for all even $n$ . So from now on we consider only $p$ such that $\gcd(6,p)=1$ .
Thus if $p$ divides some $a_n$ then we have $2^n+3^n+6^n-1 \equiv 0 \mod(p) \implies 2^n+3^n+6^n \equiv 1 \mod(p)$ . Note that since $\gcd(6,p)=1$ , we can multiply both sides by the inverse of $6^n \mod(p)$ to get $( \frac{1}{3} )^n+\big (\frac{1}{2} \big)^n \equiv 0 \mod(p) \implies ( -\frac{2}{3} )^n \equiv 1 \mod(p)$ . Since $p$ is coprime to $2,3$ , there exists an order for $-\frac{2}{3} \mod (p)$ , thus we may take $n$ to be that order and we are done.

This means only 1 is relatively prime to all terms of the sequence.

Z K Y

The post below has been deleted. Click to close.

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

blueberryfaygo_55

340 posts

blueberryfaygo_55

#124 h Jun 7, 2024, 8:26 PM

Y by

We claim that $1$ is the only positive integer relatively prime to all terms of $a_n$ . Since this is obviously true, consider some positive integer $m \geq 1$ . If $m$ is a power of $2$ or $3$ , then we can take $n=2$ to get $a_2 = 2^2 + 3^2 + 6^2 - 1 = 48$ which is not relatively prime to $m$ . Otherwise, consider a prime $p \neq 2,3$ that divides $m$ . Taking $n=p-2$ , we have
$\begin{align*} a_{p-2} &= 2^{p-2} + 3^{p-2} + 6^{p-2} - 1 \\ &= 2^{p-1} \cdot 2^{-1} + 3^{p-1} \cdot 3^{-1} + 6^{p-2} \cdot 6^{-1} - 1 \\ &\equiv 2^{-1} + 3^{-1} + 6^{-1} - 1 \pmod p \, \text{(By Fermat's Little Theorem)} \\ &\equiv 0 \pmod p \end{align*}$ so $\gcd(a_{p-2}, m) \geq p > 1$ , implying that there always exists at least $1$ term of $a_n$ that shares a prime factor with every positive integer greater than $1$ , as claimed. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

S1muelJ

247 posts

S1muelJ

#125 h Jun 7, 2024, 8:37 PM

Y by

Me struggling to understand how you are doing this

Z K Y

The post below has been deleted. Click to close.

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

ezpotd

1263 posts

ezpotd

#126 h Aug 27, 2024, 5:16 PM

Y by

The answer is just $1$ , which clearly works. Manually verify that for $n = 2$ , $3$ is a prime divisor, and for $n = 1$ , $2$ is a prime divisor. For all other primes $p$ , take $n = p - 2$ , then we have $2^{p - 2} + 3^{p - 2} + 6^{p - 2} \equiv \frac 12 + \frac 13 + \frac 16 - 1 = 0 \mod p$ , so no primes are relatively prime to all elements of the sequence, done.

Z K Y

The post below has been deleted. Click to close.

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

megahertz13

3183 posts

megahertz13

#127 h Aug 28, 2024, 8:26 PM

Y by

Z K Y

The post below has been deleted. Click to close.

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

megahertz13

3183 posts

megahertz13

#128 h Nov 4, 2024, 2:36 PM

Y by

The answer is $\boxed{1}$ , which clearly works. We will prove that there are no primes $p$ relatively prime to all $a_n$ . There are two cases.

$p = 2$ , $3$ : Here, we can take $a_2=48$ .

$p\ne 2$ , $3$ : Here, we will prove that $a_{p-2}=2^{p-2}+3^{p-2}+6^{p-2}-1\equiv 0\pmod p.$ Note that $2^{p-2}+3^{p-2}+6^{p-2}-1\pmod p$ $\equiv\frac{2^{p-1}}{2}+\frac{3^{p-1}}{3}+\frac{6^{p-1}}{6}-1\pmod p$ $\equiv \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1 \pmod p$ $\equiv 0\pmod p,$ which completes the problem.

This post has been edited 1 time. Last edited by megahertz13, Nov 4, 2024, 2:36 PM

Z K Y

The post below has been deleted. Click to close.

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

eg4334

637 posts

eg4334

#129 h Nov 29, 2024, 9:35 PM

Y by

The answer is just $n=1$ which obviously works. It clearly suffices to show that $\forall p, \exists n \in \{ 1, 2, \dots \}, p|a_n$ . The conclusion for $p=2$ is true for all $n$ and for $p=3$ it is true for all even $n$ . For other $p$ , consider $n=p-2$ . So, $a_{p-2} = \frac12 + \frac13 + \frac16 - 1 \equiv 0 \pmod{p}$ , so we are done.

This post has been edited 1 time. Last edited by eg4334, Nov 29, 2024, 9:35 PM

Z K Y

The post below has been deleted. Click to close.

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

Eka01

204 posts

Eka01

#130 h Dec 3, 2024, 2:59 PM

Y by

Consider a prime $p>3$ and $n=p-2$ . We have that $2^n +3^n +6^n -1 \equiv 0.5+0.333...+0.16... -1 \equiv 0$ modulo $p$ so all primes greater than $3$ divide atleast one term of this sequence so we are done. $2$ obviously divides all terms and $3$ divides all those with $n$ even.

This post has been edited 1 time. Last edited by Eka01, Dec 3, 2024, 3:00 PM

Z K Y

The post below has been deleted. Click to close.

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

Maximilian113

575 posts

Maximilian113

#131 h Dec 14, 2024, 4:17 AM

Y by

Note that we can take $a_2=48$ so multiples of $2, 3$ don't work. Now, suppose that $p>3$ is a prime. Then by FLT $a_{p-2} \equiv \frac12+\frac13+\frac16-1 \equiv 0 \pmod p.$ Therefore $1$ is the only solution.

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

616 posts

cursed_tangent1434

#132 h Feb 10, 2025, 5:22 AM

Y by

Really easy problem. It's really nice to look at the solutions from 2005 to the present and see how the solutions have evolved with time.

Clearly $a_2=48$ so multiples of $2$ and $3$ do not satisfy the desired condition. Further, for all primes $p>3$ , by Fermat's Little Theorem we have,
$2^{p-2}+3^{p-2}+6^{p-2}-1\equiv \frac{1}{2}+\frac{1}{3}+\frac{1}{6}-1 \equiv 0 \pmod{p}$ Thus, $p\mid a_{p-2}$ for all primes $p>3$ . Thus, any integer with a prime factor greater than $3$ also violates the condition, implying that the only solution is $n=1$ .

Remark. It might be interesting to look at the following similar question.

Harder Problem wrote:

Determine all positive integers which have some multiple in the infinite sequence $a_n=2^n+3^n+6^n -1,\ n\geq 1.$

A similar argument as above shows that all $n$ for which $\gcd(n,6)=1$ satisfy this condition, but the cases where $\gcd(n,6)>1$ are messier. In particular any positive integer of the form $15k,20k,21k,28k$ does not satisfy this condition.