Maths Olympiad Prep

Library / /264 of 520

Number theory Difficulty 6.1 National olympiad Find the answer

Example 5 Try to solve the congruence equation
x234(mod257)x^{2} \equiv 34(\bmod 257)

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

Solution

Since 257 is a prime number, we have
(34257)=(2257)(17257)=(17257)=(25717)=(217)=1\begin{aligned} \left(\frac{34}{257}\right) & =\left(\frac{2}{257}\right)\left(\frac{17}{257}\right)=\left(\frac{17}{257}\right) \\ & =\left(\frac{257}{17}\right)=\left(\frac{2}{17}\right)=1 \end{aligned}

Therefore, the original congruence equation must have a solution.
Since 257=4×26+1257=4 \times 2^{6}+1, we have n=26,λ=6,μ=1n=2^{6}, \lambda=6, \mu=1, u+12=1\frac{u+1}{2}=1, so au=34a^{u}=34. We also have
342=1156128(mod257)34221282=1638419364(mod257)3423(64)2=409624116(mod257)3424(16)2=2561(mod257)\begin{array}{c} 34^{2}=1156 \equiv 128(\bmod 257) \\ 34^{2^{2}} \equiv 128^{2}=16384 \equiv 193 \equiv-64(\bmod 257) \\ 34^{2^{3}} \equiv(-64)^{2}=4096 \equiv 241 \equiv-16(\bmod 257) \\ 34^{2^{4}} \equiv(-16)^{2}=256 \equiv-1 \quad(\bmod 257) \end{array}

Thus,
μ=4,λμ=64=2,\mu=4, \lambda-\mu=6-4=2,

Hence,
h=22t=4t,t is odd h=2^{2} \cdot t=4 t, \quad t \text { is odd }

And we have \square
1t241=151 \leqslant t \leqslant 2^{4}-1=15

Since 257=12×21+5257=12 \times 21+5, 3 is a quadratic non-residue modulo 257, so we have
(b2u)h=(32)4t=(38)t\left(b^{2 u}\right)^{h}=\left(3^{2}\right)^{4 t}=\left(3^{8}\right)^{t}

However, we have
38=94=812=6561136121(mod257)(38)3(121)3=(14641)(121)(8)(121)96819760(mod257)(38)5(8)(60)=48034(mod257)\begin{array}{c} 3^{8}=9^{4}=81^{2}=6561 \equiv 136 \equiv-121(\bmod 257) \\ \left(3^{8}\right)^{3} \equiv(-121)^{3}=(14641)(-121) \equiv(-8)(-121) \\ \equiv 968 \equiv 197 \equiv-60(\bmod 257) \\ \left(3^{8}\right)^{5} \equiv(-8)(-60)=480 \equiv-34(\bmod 257) \end{array}

Therefore, we must have t=5t=5, so h=4t=4×5=20h=4 t=4 \times 5=20,
nh=2620=44,n-h=2^{6}-20=44,

Since
(38)534(mod257)\left(3^{8}\right)^{5} \equiv-34(\bmod 257)

We have
34434×34081×(34)275418473(mod257)\begin{aligned} 3^{44} & \equiv 3^{4} \times 3^{40} \equiv 81 \times(-34) \equiv-2754 \\ & \equiv-184 \equiv 73(\bmod 257) \end{aligned}

And
34×73=248216988(mod257)34 \times 73=2482 \equiv 169 \equiv-88(\bmod 257)

Thus, by (10), the solution to the original equation is
x±88(mod257)x \equiv \pm 88(\bmod 257)

For the case of pαp^{\alpha} modulo, where p>2,α>1p>2, \alpha>1.
We already know how to determine whether
x2a(modp),(a,p)=1x^{2} \equiv a(\bmod p),(a, p)=1

has a solution, and if it does, how to find it. In this section, we will discuss, if pp is an odd prime, α\alpha is an integer greater than 1, the congruence equation
x2a(modpα),(α,p)=1x^{2} \equiv a\left(\bmod p^{\alpha}\right),(\alpha, p)=1

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.