Maths Olympiad Prep

Library / /1 of 27

Number theory Difficulty 4.5 AIME Prove it Croatia

Prove that there does not exist a positive integer nn such that 7n17^n - 1 is divisible by 6n16^n - 1.

Solution

Assume that such nn exists.
Note that 55 divides 6n1=(61)(6n1++1)6^n - 1 = (6-1)(6^{n-1} + \dots + 1), so 55 also has to divide 7n17^n - 1.
The powers of 77 when divided by 55 give remainders 2,4,3,1,2, 4, 3, 1, \dots and these remainders repeat periodically. Therefore, 7n17^n - 1 will be divisible by 55 if and only if nn is divisible by 44, i.e. n=4kn = 4k.
By the formula for the difference of kkth powers, we can conclude that 6416^4 - 1 divides 64k16^{4k} - 1. Moreover, 77 divides 641=(621)(62+1)=3537=57376^4 - 1 = (6^2 - 1)(6^2 + 1) = 35 \cdot 37 = 5 \cdot 7 \cdot 37. Therefore, 77 divides 6n16^n - 1, so it also divides 7n17^n - 1, which is a contradiction.

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.