Maths Olympiad Prep

Library / /36 of 50

Number theory Difficulty 5.7 AIME, harder Prove it Belarus

Let A=27(714+1)+26711102+2677104+2473106A = 2^7(7^{14} + 1) + 2^6 \cdot 7^{11} \cdot 10^2 + 2^6 \cdot 7^7 \cdot 10^4 + 2^4 \cdot 7^3 \cdot 10^6.
Prove that the number AA ends with 14 zeroes.

Solution

Answer: 14 zeroes.

First solution. Derive the maximum power of 2 as a common factor:
A=27(714+1+252711+235477+235673). A = 2^7 \cdot (7^{14} + 1 + 2 \cdot 5^2 \cdot 7^{11} + 2^3 \cdot 5^4 \cdot 7^7 + 2^3 \cdot 5^6 \cdot 7^3).
Note that 50=72+150 = 7^2 + 1 and represent 50 in this way in all terms:
27A=714+(72+1)711+2(72+1)277+(72+1)373+1. 2^{-7}A = 7^{14} + (7^2 + 1) \cdot 7^{11} + 2 \cdot (7^2 + 1)^2 \cdot 7^7 + (7^2 + 1)^3 \cdot 7^3 + 1.
Expand the right-hand side in powers of 7:
27A=714+713+711+2711+479+277+79+377+375+73+1. 2^{-7}A = 7^{14} + 7^{13} + 7^{11} + 2 \cdot 7^{11} + 4 \cdot 7^9 + 2 \cdot 7^7 + 7^9 + 3 \cdot 7^7 + 3 \cdot 7^5 + 7^3 + 1.
Once again, use equality 72+1=507^2 + 1 = 50, for which derive even degrees of 7 in all terms:
27A=714+7712+7710+14710+2878+1476+778+2176+2174+772+1 2^{-7}A = 7^{14} + 7 \cdot 7^{12} + 7 \cdot 7^{10} + 14 \cdot 7^{10} + 28 \cdot 7^8 + 14 \cdot 7^6 + 7 \cdot 7^8 + 21 \cdot 7^6 + 21 \cdot 7^4 + 7 \cdot 7^2 + 1
and expand the right-hand side in even powers of 7:
27A=714+7712+21710+3578+3576+2174+772+1. 2^{-7}A = 7^{14} + 7 \cdot 7^{12} + 21 \cdot 7^{10} + 35 \cdot 7^8 + 35 \cdot 7^6 + 21 \cdot 7^4 + 7 \cdot 7^2 + 1.
Now it is clear that the right-hand side is the Newton binomial formula for (72+1)7(7^2 + 1)^7, hence the number A=27507=1014A = 2^7 \cdot 50^7 = 10^{14} ends with 14 zeroes.

Second solution For any x1x_1 and x2x_2 set Sk=x1k+x2kS_k = x_1^k + x_2^k, x1+x2=px_1 + x_2 = p and x1x2=qx_1 x_2 = q (note that S0=2S_0 = 2, S1=pS_1 = p). Using the obvious recurrence formula Sk+2=pSk+1qSkS_{k+2} = pS_{k+1} - qS_k, we successively get S2=p22qS_2 = p^2 - 2q, S3=p33pqS_3 = p^3 - 3pq, S4=p44p2q+2q2S_4 = p^4 - 4p^2q + 2q^2, S5=p55p3q+5pq3S_5 = p^5 - 5p^3q + 5pq^3, S6=p66p4+9p2q22q3S_6 = p^6 - 6p^4 + 9p^2q^2 - 2q^3 and, finally,
S7=p77p5q+14p3q27pq3(1) S_7 = p^7 - 7p^5q + 14p^3q^2 - 7pq^3 \quad (1)
Now, take x1=100x_1 = 100, x2=2x_2 = -2 then p=272p = 2 \cdot 7^2, q=2102q = -2 \cdot 10^2 and (1) takes the form 101427=27714+26711102+2677104+247310610^{14} - 2^7 = 2^7 \cdot 7^{14} + 2^6 \cdot 7^{11} \cdot 10^2 + 2^6 \cdot 7^7 \cdot 10^4 + 2^4 \cdot 7^3 \cdot 10^6 which is equivalent to A=1014A = 10^{14}.

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.