Maths Olympiad Prep

Library / /3 of 106

Number theory Difficulty 7.2 National olympiad, round 2 Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve the problem, we need to determine all positive integers that are relatively prime to every term of the sequence defined by:

an=2n+3n+6n1,n1. a_n = 2^n + 3^n + 6^n - 1, \quad n \geq 1.

Step 1: Understanding the sequence properties

To determine an integer relatively prime to all an a_n , we first investigate the properties of the sequence:

an=2n+3n+6n1=2n+3n+(23)n1. a_n = 2^n + 3^n + 6^n - 1 = 2^n + 3^n + (2 \cdot 3)^n - 1.

Step 2: Checking divisibility by small primes

Let's check the sequence for small integer divisibility patterns, beginning with the smallest prime number, p=2 p = 2 :

- For n=1 n = 1 :
a1=21+31+611=2+3+61=10 a_1 = 2^1 + 3^1 + 6^1 - 1 = 2 + 3 + 6 - 1 = 10
a1 a_1 is divisible by 2 2 .

- For n=2 n = 2 :
a2=22+32+621=4+9+361=48 a_2 = 2^2 + 3^2 + 6^2 - 1 = 4 + 9 + 36 - 1 = 48
a2 a_2 is divisible by 2 2 .

- In general, if we use modulo 2 for any n1 n \geq 1 , it is evident that an0(mod2) a_n \equiv 0 \pmod{2} .

Similarly, let's check for divisibility by 3 3 :

- For n=1 n = 1 :
a1=101(mod3) a_1 = 10 \equiv 1 \pmod{3}
a1 a_1 is not divisible by 3 3 .

- For n=2 n = 2 :
a2=480(mod3) a_2 = 48 \equiv 0 \pmod{3}
a2 a_2 is divisible by 3 3 .

- For n=3 n = 3 :
a3=23+33+631=8+27+2161=2501(mod3) a_3 = 2^3 + 3^3 + 6^3 - 1 = 8 + 27 + 216 - 1 = 250 \equiv 1 \pmod{3}
a3 a_3 is not divisible by 3 3 .

Notice that because a20(mod3) a_2 \equiv 0 \pmod{3} , this implies an a_n shares periodic divisibility by 3 3 .

Conclusion

Through examining divisibility by smaller primes such as 2 2 and 3 3 , and recognizing these properties, we deduce that the only positive integer that is relatively prime to every an a_n is:

1 \boxed{1}
This is because 1 1 is relatively prime to every integer. Hence, the complete set of integers relatively prime to all terms in the sequence is \{1\}, given their universal property.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.