Maths Olympiad Prep

Library / /70 of 136

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Hong Kong

Find the total number of primes p<100p < 100 such that (2+5)p2p+1\lfloor (2 + \sqrt{5})^p \rfloor - 2^{p+1} is divisible by pp. Here x\lfloor x \rfloor denotes the greatest integer less than or equal to xx.

Solution

The answer is 24.
Let pp be an odd prime. Using the binomial theorem, we have
(2+5)p+(25)p=k=0p12(p2k)2p+12k5k=2p+1+k=1p12(p2k)2p+12k5k, (2 + \sqrt{5})^p + (2 - \sqrt{5})^p = \sum_{k=0}^{\frac{p-1}{2}} \binom{p}{2k} 2^{p+1-2k} \cdot 5^k = 2^{p+1} + \sum_{k=1}^{\frac{p-1}{2}} \binom{p}{2k} 2^{p+1-2k} \cdot 5^k,
which is an integer. Since pp is an odd prime, we have (25)p<0(2 - \sqrt{5})^p < 0. From this it follows that (2+5)p=(2+5)p+(25)p|(2 + \sqrt{5})^p| = (2 + \sqrt{5})^p + (2 - \sqrt{5})^p. Thus,
(2+5)p2p+1=k=1p12(p2k)2p+12k5k. |(2 + \sqrt{5})^p| - 2^{p+1} = \sum_{k=1}^{\frac{p-1}{2}} \binom{p}{2k} 2^{p+1-2k} \cdot 5^k.
Since (pr)\binom{p}{r} is divisible by pp for 1rp11 \le r \le p-1, (2+5)p2p+1|(2 + \sqrt{5})^p| - 2^{p+1} is divisible by pp.
It is easy to check that the expression is not divisible by pp when p=2p = 2. Since there are 25 primes less than 100, the answer is 24.

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.