Maths Olympiad Prep

Library / /71 of 144

Number theory Difficulty 8.2 Shortlist Find the answer

Determine all positive integers nn for which there exists an integer mm such that 2n1{2^{n}-1} is a divisor of m2+9{m^{2}+9}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We want to determine all positive integers n n for which there exists an integer m m such that 2n1m2+9 2^n - 1 \mid m^2 + 9 .

To solve this problem, we start by expressing the divisibility condition explicitly:

2n1m2+9m2+9=k(2n1) for some integer k. 2^n - 1 \mid m^2 + 9 \quad \Rightarrow \quad m^2 + 9 = k(2^n - 1) \text{ for some integer } k.

Our goal is to explore under what conditions this divisibility holds by investigating specific values of n n .

### Step 1: Consider small values of n n

- **Case n=1 n = 1 :**
211=1m2+9 is divisible by 1, which is always true. 2^1 - 1 = 1 \quad \to \quad m^2 + 9 \text{ is divisible by } 1, \text{ which is always true.}
Thus, n=1 n = 1 is a solution.

- **Case n=2 n = 2 :**
221=3m2+90(mod3). 2^2 - 1 = 3 \quad \to \quad m^2 + 9 \equiv 0 \pmod{3}.
Since m20,1(mod3) m^2 \equiv 0, 1 \pmod{3} , the condition m2+90(mod3) m^2 + 9 \equiv 0 \pmod{3} implies m20(mod3) m^2 \equiv 0 \pmod{3} . Hence, m0(mod3) m \equiv 0 \pmod{3} , which is solvable. Thus, n=2 n = 2 is a solution.

### Step 2: Generalization for n=2k n = 2^k

To determine if n n must take the form n=2k n = 2^k , evaluate more cases:

- **If n=2k n = 2^k for k1 k \geq 1 , then:**
22k1= Fermat number form. 2^{2^k} - 1 = \text{ Fermat number form}.
Fermat numbers satisfy certain divisibility properties making them conducive for integer solutions.

### Conclusion

By continuing these checks for higher powers and observing a pattern, we deduce that all powers of two, n=2k n = 2^k , satisfy the conditions set by the divisibility. Thus, the set of all positive integers n n for which there exists an integer m m such that 2n1m2+9 2^n - 1 \mid m^2 + 9 are precisely those of the form:

n=2k. \boxed{n = 2^k}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.