Maths Olympiad Prep

Library / /7 of 22

Number theory Difficulty 6.0 AIME, harder Prove it Croatia

Let nn be a positive integer. Prove that there exists a positive integer kk such that
51k17 51^k - 17
is divisible by 2n2^n.

Solution

### Claim.
For every positive integer n3n \ge 3 there exists a positive integer kk such that 512n21=2n(2k+1)51^{2^{n-2}} - 1 = 2^n \cdot (2k + 1).

*Proof.* We prove the claim by mathematical induction on nn.

For n=3n=3 we have 5121=321=851^2 - 1 = 3^2 - 1 = 8 (mod 16), so 512151^2 - 1 is divisible by 232^3 but not by 242^4, therefore the claim holds for n=3n=3. Assume the claim holds for some nn, i.e. 512n21=2n(2k+1)51^{2^{n-2}} - 1 = 2^n \cdot (2k + 1) for some positive integer kk. Then
512n11=(512n21)(512n2+1)=2n(2k+1)(2n(2k+1)+2)=2n+1(2k+1)(2n1(2k+1)+1), \begin{aligned} 51^{2^{n-1}} - 1 &= (51^{2^{n-2}} - 1)(51^{2^{n-2}} + 1) \\ &= 2^n \cdot (2k+1)(2^n \cdot (2k+1) + 2) \\ &= 2^{n+1} \cdot (2k+1)(2^{n-1}(2k+1) + 1), \end{aligned}
and since (2k+1)(2n1(2k+1)+1)(2k+1)(2^{n-1}(2k+1)+1) is odd, the claim holds for n+1n+1. This completes the proof. \square

Regarding the initial statement of the problem, we will inductively define an appropriate knk_n for every nn. Note that for n=1,n=2n=1, n=2 and n=3n=3 we can select k=2k=2, i.e. k1=k2=k3=2k_1 = k_2 = k_3 = 2. Assume the claim holds for some nn, i.e. there exists some positive integer ana_n such that 51kn17=2nan51^{k_n} - 17 = 2^n \cdot a_n. If ana_n is even, we can select kn+1=knk_{n+1} = k_n. If ana_n is odd, we can define kn+1=kn+2n2k_{n+1} = k_n + 2^{n-2}. Then we have
51kn+117=512n2(51kn17)+17(512n21). 51^{k_{n+1}} - 17 = 51^{2^{n-2}} \cdot (51^{k_n} - 17) + 17 \cdot (51^{2^{n-2}} - 1).
By the inductive assumption and the previously proven claim, we can conclude that there exists a positive integer kk such that
51k+n+117=512n22nan+172n(2k+1)=2n(512n2an+17(2k+1)). \begin{aligned} 51^{k+n+1} - 17 &= 51^{2^{n-2}} \cdot 2^n \cdot a_n + 17 \cdot 2^n \cdot (2k+1) \\ &= 2^n \cdot (51^{2^{n-2}} a_n + 17(2k+1)). \end{aligned}
Since ana_n is odd, it follows that 512n2an+17(2k+1)51^{2^{n-2}} a_n + 17(2k+1) is even, therefore 51k+n+11751^{k+n+1} - 17 is indeed divisible by 2n+12^{n+1}.

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.