Maths Olympiad Prep

Library / /8 of 11

Number theory Difficulty 6.2 National Olympiad Prove it Spain

For all positive integer nn we consider the number an=46n+1943a_n = 4^{6^n} + 1943. Prove that ana_n is divisible by 20132013 for all n1n \ge 1, and find all values of nn for which an207a_n - 207 is the cube of a positive integer.

Solution

To prove the first part, we begin observing that 2013=31161=33612013 = 3 \cdot 11 \cdot 61 = 33 \cdot 61. Since 95=81819=(61+20)(61+20)99^5 = 81 \cdot 81 \cdot 9 = (61+20)(61+20) \cdot 9 and 20209=3600=6159+120 \cdot 20 \cdot 9 = 3600 = 61 \cdot 59 + 1, then we have 951(mod61)9^5 \equiv 1 \pmod{61}. Since 46=4096=6167+99(mod61)4^6 = 4096 = 61 \cdot 67 + 9 \equiv 9 \pmod{61} and 6n1=(5+1)n1=5m+16^{n-1} = (5+1)^{n-1} = 5m + 1, mNm \in \mathbb{N}, then for all n1n \ge 1, holds
46n=(46)6n1=(46)5m+195m9(mod61)9(mod61) 4^{6^n} = (4^6)^{6^{n-1}} = (4^6)^{5m+1} \equiv 9^{5m} \cdot 9 \pmod{61} \equiv 9 \pmod{61}
So, an=46n+19431952(mod61)0(mod61)a_n = 4^{6^n} + 1943 \equiv 1952 \pmod{61} \equiv 0 \pmod{61} and 61an61|a_n, for all n1n \ge 1.

On the other hand, an=46n4+1947=4(46n11)+3359a_n = 4^{6^n} - 4 + 1947 = 4(4^{6^n-1} - 1) + 33 \cdot 59. Since 6n10(mod5)6^n - 1 \equiv 0 \pmod{5}, then 6n1=5p,pN6^n - 1 = 5p, p \in \mathbb{N}. Then, we have
46n11=45p1=(45)p1=1024p1=(10241)(1024p1++1)=1023q=3331q \begin{aligned} 4^{6^n-1} - 1 &= 4^{5p} - 1 = (4^5)^p - 1 = 1024^p - 1 \\ &= (1024 - 1)(1024^{p-1} + \dots + 1) = 1023 \cdot q = 33 \cdot 31 \cdot q \end{aligned}

and 33an33|a_n the jointly with the preceding yields 2013=3361an2013 = 33 \cdot 61|a_n for all n1n \ge 1.

To solve the second part of the statement, we observe that an207=46n+1736a_n - 207 = 4^{6^n} + 1736 is an even integer, say 2x2x with xNx \in \mathbb{N}. From 46n+1736=(2x)34^{6^n} + 1736 = (2x)^3 follows 226n3+217=x32^{2 \cdot 6^{n-3}} + 217 = x^3 or 23(46n11)+217=x32^{3(4 \cdot 6^{n-1}-1)} + 217 = x^3. Putting 246n11=y2^{4 \cdot 6^{n-1}-1} = y in the last equation yields
x3y3=217(xy)(x2+xy+y2)=217=731 x^3 - y^3 = 217 \Leftrightarrow (x - y)(x^2 + xy + y^2) = 217 = 7 \cdot 31
Since xy<x2+xy+y2x - y < x^2 + xy + y^2, then we have two possibilities
{xy=1,x2+xy+y2=217.or{xy=7,x2+xy+y2=31. \begin{cases} x - y = 1, \\ x^2 + xy + y^2 = 217. \end{cases} \quad \text{or} \quad \begin{cases} x - y = 7, \\ x^2 + xy + y^2 = 31. \end{cases}
The solutions of the first system are (9,8)(9, 8), (8,9)(-8, -9) and the solutions of the second one (6,1)(6, -1) and (1,6)(1, -6). Finally, since y=246n11y = 2^{4 \cdot 6^{n-1}-1} is a positive integer, then y=246n11=8=23y = 2^{4 \cdot 6^{n-1}-1} = 8 = 2^3 from which follows n=1n = 1, and we are done. \square

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.