Maths Olympiad Prep

Library / /6 of 48

Number theory Difficulty 5.1 AIME, harder Prove it Greece

Prove that the number A=72n−48n−1A = 7^{2n} - 48n - 1 is a multiple of 99, for all positive integers nn.

Solution

We distinguish three cases mod 33.

* If n=3kn = 3k, then A=76k−48(3k)−1=493k−9⋅16k−1A = 7^{6k} - 48(3k) - 1 = 49^{3k} - 9 \cdot 16k - 1. Since 49≡4(mod9)49 \equiv 4 \pmod{9}, it follows that 493≡43(mod9)≡1(mod9)49^3 \equiv 4^3 \pmod{9} \equiv 1 \pmod{9} and hence 9∣493k−1⇒9∣A9 \mid 49^{3k} - 1 \Rightarrow 9 \mid A.

* If n=3k+1n = 3k+1, then
A=76k+2−48(3k+1)−1=72⋅76k−9⋅16k−49=49(76k−1)−9⋅16kA = 7^{6k+2} - 48(3k+1) - 1 = 7^2 \cdot 7^{6k} - 9 \cdot 16k - 49 = 49(7^{6k} - 1) - 9 \cdot 16k.
Since 9∣76k−19 \mid 7^{6k} - 1, it follows again that 9∣A9 \mid A.

* If n=3k+2n = 3k + 2, then A=76k+4−48(3k+2)−1=74⋅76k−9⋅16k−97A = 7^{6k+4} - 48(3k + 2) - 1 = 7^4 \cdot 7^{6k} - 9 \cdot 16k - 97. We have that 76k≡1(mod9)⇒74⋅76k≡74(mod9)≡492(mod9)≡42(mod9)≡7(mod9)7^{6k} \equiv 1 \pmod{9} \Rightarrow 7^4 \cdot 7^{6k} \equiv 7^4 \pmod{9} \equiv 49^2 \pmod{9} \equiv 4^2 \pmod{9} \equiv 7 \pmod{9} and also 97≡7(mod9)97 \equiv 7 \pmod{9}.
Hence 9∣74⋅76k−979 \mid 7^4 \cdot 7^{6k} - 97, that is 9∣A9 \mid A.

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 and solution reproduced as published; topic and difficulty added by this site.