Maths Olympiad Prep

Library / /11 of 20

Number theory Difficulty 6.2 National olympiad Prove it China

Let A={2,22,,2n,}A = \{2, 2^2, \dots, 2^n, \dots\}. Prove:

(1) For any aAa \in A, bNb \in \mathbb{N}^*, if b<2a1b < 2a - 1, then b(b+1)b(b+1) will not be a multiple of 2a2a.

(2) For any aAˉ(=NA)a \in \bar{A} (= \mathbb{N}^* - A) satisfying a1a \neq 1, there exists bNb \in \mathbb{N}^* satisfying b<2a1b < 2a - 1, such that b(b+1)b(b+1) is a multiple of 2a2a.

Solution

(1) For any aAa \in A, a=2ka = 2^k (kNk \in \mathbb{N}^*). Then 2a=2k+12a = 2^{k+1}. Let bb be any positive integer strictly less than 2a12a - 1. Then (b+1)2a1(b+1) \le 2a - 1.

Between bb and b+1b+1, one is an odd number that contains no prime factor 22, and the other is an even number that contains at most the kkth power of 22. Therefore, b(b+1)b(b+1) is definitely not a multiple of 2a2a.

(2) For aAˉa \in \bar{A} and a1a \ne 1, suppose a=2kma = 2^k m where kk is a non-negative integer and mm is an odd number greater than 11. Then 2a=2k+1m2a = 2^{k+1} m. We will present three different proofs in the following.

Proof 1. Let b=mxb = mx, b+1=2k+1yb+1 = 2^{k+1} y. Eliminating bb, we have 2k+1ymx=12^{k+1}y - mx = 1. Since (2k+1,m)=1(2^{k+1}, m) = 1, the equation has integral solutions that can be expressed as
{x=x0+2k+1t,y=y0+mt(where tZ, and (x0,y0) is a special solution of the equation.) \begin{cases} x = x_0 + 2^{k+1} t, \\ y = y_0 + m t \end{cases} \quad (\text{where } t \in \mathbb{Z}, \text{ and } (x_0, y_0) \text{ is a special solution of the equation}.)
Denote the smallest solution among them as (x,y)(x^*, y^*). Then x<2k+1x^* < 2^{k+1}.
Therefore, b=mx<2a1b = m x^* < 2a - 1 and b(b+1)b(b+1) is a multiple of 2a2a.

Proof 2. Since (2k+1,m)=1(2^{k+1}, m) = 1, by the Chinese Remainder Theorem, the congruence equation
{x0(mod2k+1),xm1(modm) \begin{cases} x \equiv 0 \pmod{2^{k+1}}, \\ x \equiv m-1 \pmod{m} \end{cases}
has a solution x=bx = b with b(0,2k+1m)b \in (0, 2^{k+1} m). It is easy to see that b<2a1b < 2a-1 and b(b+1)b(b+1) is a multiple of 2a2a.

Proof 3. Since (2k+1,m)=1(2^{k+1}, m) = 1, then there exists rNr \in \mathbb{N}^*, rm1r \le m - 1, such that 2r1(modm)2^r \equiv 1 \pmod{m}.
Take tNt \in \mathbb{N}^* such that tr>k+1tr > k + 1. Then 2tr1(modm)2^{tr} \equiv 1 \pmod{m}. It is easy to see that there exists
b=(2tr1)q2k+1m>0(qN), b = (2^{tr} - 1) - q \cdot 2^{k+1} m > 0 \quad (q \in \mathbb{N}),
such that 0<b<2a10 < b < 2a - 1. Then we have mbm \mid b, 2k+1b+12^{k+1} \mid b + 1.
Therefore, b(b+1)b(b + 1) is a multiple of 2a2a.

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.