Maths Olympiad Prep

Library / /87 of 94

Number theory Difficulty 7.1 National Olympiad, round 2 Prove it Hong Kong

Find all nonnegative integers mm and nn that satisfy the equation:
10756(m21)2m+3=(113114n). 107^{56}(m^2 - 1) - 2m + 3 = \binom{113^{114}}{n}.
(If nn and rr are nonnegative integers satisfying rnr \le n, then (nr)=Crn=n!r!(nr)!\binom{n}{r} = C_r^n = \frac{n!}{r!(n-r)!} and (nr)=0\binom{n}{r} = 0 if r>nr > n.)

Solution

The solutions are (m,n)=(1,0),(1,113114)(m, n) = (1, 0), (1, 113^{114}).
When n=0n = 0 or n=113114n = 113^{114}, the equation becomes 10756(m21)2m+3=1107^{56}(m^2 - 1) - 2m + 3 = 1. This implies
(m1)(10756(m+1)2)=0. (m - 1)(107^{56}(m + 1) - 2) = 0.
Clearly, 10756(m+1)2=0107^{56}(m + 1) - 2 = 0 has no solution. Thus, the only solution is m=1m = 1.

When 0<n<1131140 < n < 113^{114}, by Lucas' theorem, 113113 divides (113114n)\binom{113^{114}}{n}. This also holds when n>113114n > 113^{114} since the binomial coefficient is 0. Therefore, we have
10756(m21)2m+30(mod113).(1) 107^{56}(m^2 - 1) - 2m + 3 \equiv 0 \pmod{113}. \qquad (1)
Let gg be a primitive root modulo 113113, and let 107ga(mod113)107 \equiv g^a \pmod{113}. Using the Legendre symbol and the quadratic reciprocity law, we find that
(107113)=(6113)=(1113)(2113)(3113)=(1)(1)(1133)=(23)=1. \left(\frac{107}{113}\right) = \left(\frac{-6}{113}\right) = \left(\frac{-1}{113}\right)\left(\frac{2}{113}\right)\left(\frac{3}{113}\right) = (1)(1)\left(\frac{113}{3}\right) = \left(\frac{2}{3}\right) = -1.
This shows 107107 is a quadratic nonresidue modulo 113113, and so aa is odd. Now, note that
10756g56a1(mod113) 107^{56} \equiv g^{56a} \equiv -1 \pmod{113}
since (g56a)2=g112a=gφ(113)a1(mod113)(g^{56a})^2 = g^{112a} = g^{\varphi(113)a} \equiv 1 \pmod{113} and 112+56a112 + 56a. Therefore, (1) becomes
(m21)2m+30(mod113). -(m^2 - 1) - 2m + 3 \equiv 0 \pmod{113}.

This is the same as (m+1)25(mod113)(m+1)^2 \equiv 5 \pmod{113}. However, we check that
(5113)=(1135)=(35)=1, \left(\frac{5}{113}\right) = \left(\frac{113}{5}\right) = \left(\frac{3}{5}\right) = -1,
which implies 5 is a quadratic nonresidue modulo 113. This is a contradiction. Therefore, there is no solution.

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.