Maths Olympiad Prep

Library / /405 of 520

Number theory Difficulty 5.7 AIME, harder Prove it

Example 2. If H(m,n)=qp(p,qN)H(m, n)=\frac{q}{p}(p, q \in N), and m+nm+n is an odd prime, then (m+n)q(m+n) \mid q.

Solution

Prove that since m+nm+n is an odd prime, nm+1n-m+1 is even. Therefore, H(m,n)H(m, n) has an even number of terms.
 Let 1mn+1(m+1)(n1)+m+n1212+n+12=sr,(r,s)=1,r,sN \begin{array}{l} \text { Let } \frac{1}{m n}+\frac{1}{(m+1)(n-1)}+\cdots \\ \frac{m+n-1}{2} \cdot \frac{1}{2}+\frac{n+1}{2}=\frac{s}{r}, \\ (r, s)=1, r, s \in N \text {. } \\ \end{array}

It is easy to see that the prime factors of rr are all less than or equal to nn, so,
(m+n,r)=1.H(m,n)=qp,qp=(m+n)sr, \begin{array}{l} (m+n, r)=1 . \\ \because H(m, n)=\frac{q}{p}, \\ \therefore \frac{q}{p}=\frac{(m+n) s}{r}, \end{array}

which means
(m+n)sp=rq.(m+n,r)=1,(m+n)q. \begin{array}{l} (m+n) s p=r q . \\ \because(m+n, r)=1, \\ \therefore(m+n) \mid q . \end{array}

The 21st IMO has a problem as follows:
Let p,qp, q be natural numbers, qp=112+1314+\frac{q}{p}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots 11318+11319-\frac{1}{1318}+\frac{1}{1319}. Prove: 1979q1979|q.
It is easy to see that
qp=H(1,1319)2(12+14++11318)=H(1,1319)H(1,659)=H(660,1319). \begin{aligned} \frac{q}{p} & =H(1,1319)-2\left(\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{1318}\right) \\ & =H(1,1319)-H(1,659) \\ & =H(660,1319) . \end{aligned}

Since 660+1319=1979660+1319=1979 is a prime number, by Example 2, we know 1979q1979 \mid q.

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