Maths Olympiad Prep

Library / Croatia Mathematical Competitions /1 of 25

Croatia Mathematical Competitions

Number theory Difficulty 4.5 AIME Prove it Croatia

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

Solution

Assume that such nn exists.
Note that 55 divides 6n−1=(6−1)(6n−1+⋯+1)6^n - 1 = (6-1)(6^{n-1} + \dots + 1), so 55 also has to divide 7n−17^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, 7n−17^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 64−16^4 - 1 divides 64k−16^{4k} - 1. Moreover, 77 divides 64−1=(62−1)(62+1)=35⋅37=5⋅7⋅376^4 - 1 = (6^2 - 1)(6^2 + 1) = 35 \cdot 37 = 5 \cdot 7 \cdot 37. Therefore, 77 divides 6n−16^n - 1, so it also divides 7n−17^n - 1, which is a contradiction.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.