Maths Olympiad Prep

Library / /99 of 136

, 1997

Number theory Difficulty 8.2 Shortlist Prove it Hong Kong

Let nn be a positive integer with the following property: 2n12^n - 1 divides a number of the form m2+81m^2 + 81, where mm is a positive integer. Find all possible nn.

Solution

nn can be any nonnegative integral power of 22.

If nn has an odd divisor d3d \ge 3, then 2d12n1m2+812^d - 1 \mid 2^n - 1 \mid m^2 + 81. Since 2d13(mod4)2^d - 1 \equiv 3 \pmod{4} and 32d13 \nmid 2^d - 1, there exists an odd prime p>3p > 3 such that p3(mod4)p \equiv 3 \pmod{4} and p2d1p \mid 2^d - 1. This implies pm2+81p \mid m^2 + 81. However, this means m292(modp)m^2 \equiv -9^2 \pmod{p}, and hence (91m)21(modp)(9^{-1}m)^2 \equiv -1 \pmod{p}. This is impossible as p3(mod4)p \equiv 3 \pmod{4}. Therefore, nn has no odd divisor greater than 11. Thus, n=2kn = 2^k for some nonnegative integer kk.

It remains to find an mm such that 22k1m2+812^{2^k} - 1 \mid m^2 + 81. Firstly, note that
22k1=(2+1)(22+1)(22k1+1). 2^{2^k} - 1 = (2 + 1)(2^2 + 1)\cdots(2^{2^{k-1}} + 1).
The factors on the right are pairwise relatively prime. Indeed, if r<sr < s, then 22r+122s12^{2^r} + 1 \mid 2^{2^s} - 1, and (22s1,22s+1)=(22s1,2)=1(2^{2^s} - 1, 2^{2^s} + 1) = (2^{2^s} - 1, 2) = 1, so that (22r+1,22s+1)=1(2^{2^r} + 1, 2^{2^s} + 1) = 1. Now, by the Chinese remainder theorem, there exists mZ+m \in \mathbb{Z}^+ such that 3m3 \mid m and
m922j1(mod22j+1) m \equiv 9 \cdot 2^{2^{j-1}} \pmod{2^{2^j} + 1}
for j=1,2,,k1j = 1, 2, \dots, k - 1. For this mm, we have 3m2+813 \mid m^2 + 81 and
m2+8181(22j+1)0(mod22j+1). m^2 + 81 \equiv 81(2^{2^j} + 1) \equiv 0 \pmod{2^{2^j} + 1}.
Hence, 22k1m2+812^{2^k} - 1 \mid m^2 + 81 as desired.

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.