Maths Olympiad Prep

Library / /2 of 3

Number theory Difficulty 8.0 National olympiad, round 2 Prove it North Macedonia

Нека mm и nn се позитивни цели броеви такви што m>nm>n. Дефинираме xk=m+kn+kx_k = \frac{m+k}{n+k} за k=1,2,...,n+1k=1,2,...,n+1. Докажи дека ако x1,x2,...,xn+1x_1,x_2,...,x_{n+1} се цели броеви, тогаш x1x2...xn+11x_1x_2...x_{n+1}-1 е делив со барем еден прост непарен број.

Solution

Нека препоставиме дека x1,x2,...,xn+1x_1,x_2,...,x_{n+1} се цели броеви. Ги дефинираме целите броеви
ak=xk1=m+kn+k1=mnn+k>0, a_k = x_k - 1 = \frac{m+k}{n+k} - 1 = \frac{m-n}{n+k} > 0,
за k=1,2,...,n+1k=1,2,...,n+1.
Нека P=x1x2...xn+11P = x_1x_2...x_{n+1}-1. Потребно е да докажеме дека PP е делив со барем еден непарен прост број, или дека PP не е степен на бројот 2. За таа цел, ќе ги испитаме степените на 2 кои ги делат броевите aka_k.
Нека 2d2^d е најголем степен на 2 кој го дели mnm-n, а нека 2c2^c е најголем степен на 2 кој не го надминува 2n+12n+1. Тогаш 2n+12c+112n+1 \le 2^{c+1}-1, па n+12cn+1 \le 2^c. Значи, добиваме дека 2c2^c е еден од броевите n+1,n+2,...,2n+1n+1, n+2, ..., 2n+1, и дека единствен степен на 2 е 2c2^c кој се наоѓа меѓу тие броеви. Нека ll природен број таков што n+l=2cn+l=2^c. Бидејќи mnn+l\frac{m-n}{n+l} е цел број, добиваме дека dcd \ge c. Според тоа 2dc+1al=mnn+l2^{d-c+1} \nmid a_l = \frac{m-n}{n+l}, додека 2dc+1ak2^{d-c+1}|a_k за секој k{1,2,3,...,n+1}{l}k \in \{1,2,3,...,n+1\} \setminus \{l\}.
Ке пресметаме конгруенција по модуло 2dc+12^{d-c+1}, при што добиваме
P=(a1+1)(a2+1)...(an+1+1)1(al+1)1n1=al≢0(mod2dc+1). P = (a_1+1)(a_2+1)...(a_{n+1}+1) - 1 \equiv (a_l+1) \cdot 1^n - 1 = a_l \not\equiv 0 \pmod{2^{d-c+1}}.
Според тоа 2dc+1P2^{d-c+1} \nmid P.
Од друга страна, за секој k{1,2,...,n+1}{l}k \in \{1,2,...,n+1\} \setminus \{l\} имаме 2dc+1ak2^{d-c+1}|a_k. Според тоа P>ak2dc+1P > a_k \ge 2^{d-c+1}, за некое kk од каде следува дека PP не е степен на бројот 2.

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.