Maths Olympiad Prep

Library / /74 of 520

Number theory Difficulty 5.5 AIME, harder Find the answer

Example 2 Solve the congruence equation
x25(mod2)x^{2} \equiv 5(\bmod 2)

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

Solution

First, from
(529)=(295)=(45)=(25)2=1\left(\frac{5}{29}\right)=\left(\frac{29}{5}\right)=\left(\frac{4}{5}\right)=\left(\frac{2}{5}\right)^{2}=1

we know that the given congruence equation must have a solution. Since 295(mod8)29 \equiv 5(\bmod 8), we get the solution from the above proof as
x±(2912)!529+38=±(14!)54±(3628800)(11)(12)(13)(14)(625)±(11)(12)(13)(14)(16)=±384384±18(mod29)\begin{aligned} x & \equiv \pm\left(\frac{29-1}{2}\right)!\cdot 5^{\frac{29+3}{8}} \\ & = \pm(14!) \cdot 5^{4} \\ & \equiv \pm(3628800)(11)(12)(13)(14)(625) \\ & \equiv \pm(11)(12)(13)(14)(16) \\ & = \pm 384384 \equiv \pm 18(\bmod 29) \end{aligned}

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.