Maths Olympiad Prep

Library / /258 of 520

Number theory Difficulty 6.1 National olympiad Find the answer

Example 6 Solve the congruence equation x22(mod74)x^{2} \equiv 2\left(\bmod 7^{4}\right).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The complete residue system of 747^{4} can be represented as
x=x0+x17+x272+x3733xj3,0j3\begin{array}{c} x=x_{0}+x_{1} \cdot 7+x_{2} \cdot 7^{2}+x_{3} \cdot 7^{3} \\ -3 \leqslant x_{j} \leqslant 3, \quad 0 \leqslant j \leqslant 3 \end{array}

We solve the congruence equations sequentially
(x0+x17++xj7j)22(mod7j+1),0j3\left(x_{0}+x_{1} \cdot 7+\cdots+x_{j} \cdot 7^{j}\right)^{2} \equiv 2\left(\bmod 7^{j+1}\right), \quad 0 \leqslant j \leqslant 3

to find x0,x1,x2,x3x_{0}, x_{1}, x_{2}, x_{3}. When j=0j=0, solve
x022(mod7)x_{0}^{2} \equiv 2(\bmod 7)

we get x0=±3x_{0}= \pm 3. When j=1j=1, solve
(±3+x17)22(mod72)\left( \pm 3+x_{1} \cdot 7\right)^{2} \equiv 2\left(\bmod 7^{2}\right)

we have
9±67x12(mod72)±6x11(mod7)\begin{array}{l} 9 \pm 6 \cdot 7 x_{1} \equiv 2\left(\bmod 7^{2}\right) \\ \pm 6 x_{1} \equiv-1(\bmod 7) \end{array}

we get x1=±1x_{1}= \pm 1. When j=2j=2, solve
(±3±17+x272)22(mod73)\left( \pm 3 \pm 1 \cdot 7+x_{2} \cdot 7^{2}\right)^{2} \equiv 2\left(\bmod 7^{3}\right)

we have
(±3±17)2+2(±3)72x22(mod73)±6x22(mod7)\begin{array}{c} ( \pm 3 \pm 1 \cdot 7)^{2}+2 \cdot( \pm 3) \cdot 7^{2} x_{2} \equiv 2\left(\bmod 7^{3}\right) \\ \pm 6 x_{2} \equiv-2(\bmod 7) \end{array}

we get x2=±2x_{2}= \pm 2. When j=3j=3, solve
(±3±17±272+x373)22(mod74)\left( \pm 3 \pm 1 \cdot 7 \pm 2 \cdot 7^{2}+x_{3} \cdot 7^{3}\right)^{2} \equiv 2\left(\bmod 7^{4}\right)

we have
(±3±17±272)2±673x32(mod74)100+4072±673x32(mod74)±67x3240(mod72)±6x36(mod7)\begin{array}{c} \left( \pm 3 \pm 1 \cdot 7 \pm 2 \cdot 7^{2}\right)^{2} \pm 6 \cdot 7^{3} x_{3} \equiv 2\left(\bmod 7^{4}\right) \\ 100+40 \cdot 7^{2} \pm 6 \cdot 7^{3} x_{3} \equiv 2\left(\bmod 7^{4}\right) \\ \pm 6 \cdot 7 x_{3} \equiv-2-40\left(\bmod 7^{2}\right) \\ \pm 6 x_{3} \equiv-6(\bmod 7) \end{array}

we get x3=1x_{3}=\mp 1. Thus, the congruence equation has two solutions:
x13+17+27273235(mod74)x2317272+73235(mod74)\begin{array}{l} x_{1} \equiv 3+1 \cdot 7+2 \cdot 7^{2}-7^{3} \equiv-235\left(\bmod 7^{4}\right) \\ x_{2} \equiv-3-1 \cdot 7-2 \cdot 7^{2}+7^{3} \equiv 235\left(\bmod 7^{4}\right) \end{array}

The solution method in Example 6 is to use the kk-ary representation of integers to solve congruence equations modulo klk^{l}, where kk does not necessarily have to be a prime number.

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.