Maths Olympiad Prep

Library / /516 of 520

Number theory Difficulty 7.9 National olympiad, round 2 Prove it

Proposition Under the assumptions of Case III, if a±1(modp)a^{\prime \prime} \neq \pm 1(\bmod p), then there must be a positive integer μλ\mu \leqslant \lambda, which can make
(a)2μ1(modp)\left(a^{\prime \prime}\right)^{2^{\mu}} \equiv-1(\bmod p)

hold. At this time, there must be an odd number t(1t<2μ)t\left(1 \leqslant t<2^{\mu}\right), such that 2iμt2^{i-\mu} \cdot t is the integer hh in Case III.

Solution

Given that aa is a quadratic residue modulo pp, we know
ap12=a22iu=(au)2i+11(modp)a^{\frac{p-1}{2}}=a^{2 \cdot 2^{i} u}=\left(a^{u}\right)^{2^{i+1}} \equiv 1(\bmod p)

From this, we get (au)2i+1\left(a^{u}\right)^{2^{i}} \equiv +1 or 1(modp)-1(\bmod p). If (au)2i1(modp)\left(a^{u}\right)^{2^{i}} \equiv -1(\bmod p), then μ=λ\mu=\lambda. If (au)2i1(modp)\left(a^{u}\right)^{2^{i}} \equiv 1(\bmod p), then we must have (au)2i11\left(a^{u}\right)^{2^{i-1}} \equiv 1 or 1(modp)-1 (\bmod p). This implies μ=λ1\mu=\lambda-1 or (aμ)2i11(modp)\left(a^{\mu}\right)^{2^{i-1}} \equiv 1(\bmod p), which means (au)2i21\left(a^{u}\right)^{2^{i-2}} \equiv -1 or +1(modp)+1(\bmod p). Continuing this process, we eventually get (aμ)21\left(a^{\mu}\right)^{2} \equiv -1 or +1(modp)+1(\bmod p). This leads to μ=1\mu=1 or au±1(modp)a^{u} \equiv \pm 1(\bmod p). However, we assumed au≢±1(modp)a^{u} \not \equiv \pm 1(\bmod p), so there must be an integer
μ=1 or 2 or  or λ,\mu=1 \text { or } 2 \text { or } \cdots \text { or } \lambda,

such that
(au)21(modp)\left(a^{u}\right)^{2^{\prime \prime}} \equiv -1(\bmod p)

Among the numbers 1,2,,2j11, 2, \cdots, 2^{j}-1, there are the following 2μ12^{\mu-1} numbers:
2iμ,2iμ3,2iμ5,,2iμ(2μ1)2^{i-\mu}, 2^{i-\mu} \cdot 3, 2^{i-\mu} \cdot 5, \cdots, 2^{i-\mu}\left(2^{\mu}-1\right)

If tt is odd, we always have
((b2u)2iμt)2μ=(b22μ)t(1)t=1(modp)\left(\left(b^{2 u}\right)^{2^{i-\mu} \cdot t}\right)^{2^{\mu}}=\left(b^{2 \cdot 2^{\prime} \mu}\right) t \equiv (-1)^{t}=-1(\bmod \cdot p)

Thus, (b2u)2iμ,(b2u)2iμ3,(b2u)2iμ5,(b2u)2iμ(2μ1)\left(b^{2 u}\right)^{2^{i-\mu}}, \left(b^{2 u}\right)^{2^{i-\mu} \cdot 3}, \left(b^{2 u}\right)^{2^{i-\mu} \cdot 5}, \left(b^{2 u}\right)^{2^{i-\mu} \cdot\left(2^{\mu}-1\right)} are 2μ12^{\mu-1} solutions to the congruence equation
x2μ1(modp)x^{2^{\mu}} \equiv -1(\bmod p)

This congruence equation has 2μ2^{\mu} solutions, and the other 2μ12^{\mu-1} solutions are the negatives of the aforementioned 2μ12^{\mu-1} solutions. From the previous discussion, we know that aμa^{\mu} is a solution to this congruence equation, so there must be an odd number tt such that
au+(b2u)2jμt or (b2u)2iμt(modp),a^{u} \equiv +\left(b^{2 u}\right)^{2^{j-\mu} \cdot t} \text { or } -\left(b^{2 u}\right)^{2^{i-\mu} \cdot t}(\bmod p),

which means
(b2u)2iμt+au or au(modp),\left(b^{2 u}\right)^{2^{i-\mu}} \cdot t \equiv +a^{u} \text { or } -a^{u}(\bmod p),

Thus, we get h˙=2iμt\dot{h}=2^{i-\mu} \cdot t. Therefore, the proposition is proved.

According to this proposition, when we need to find hh, we first look for a number in the following set
(au)2,(au)22,,(au)2i\left(a^{u}\right)^{2}, \left(a^{u}\right)^{2^{2}}, \cdots, \left(a^{u}\right)^{2^{i}}

that is congruent to 1-1 modulo pp. If
(au)2A1(modp)\left(a^{u}\right)^{2^{A}} \equiv -1(\bmod p)

then we must have
h=2iμth=2^{i-\mu} \cdot t

Next, we look for a number in the set
(b2u)2iμ,(b2u)2iμ3,,(b2u)2iμ(2μ1),\left(b^{2 u}\right)^{2^{i-\mu}}, \left(b^{2 u}\right)^{2^{i-\mu} \cdot 3}, \cdots, \left(b^{2 u}\right)^{2^{i-\mu} \cdot\left(2^{\mu}-1\right)},

or equivalently, in the set
b2iμ+1u,(b2iμ+1u)3,,(b2iμ+1u)2μ1b^{2^{i-\mu+1}} \cdot u, \left(b^{2^{i-\mu+1} \cdot u}\right)^{3}, \cdots, \left(b^{2^{i-\mu+1} \cdot u}\right)^{2^{\mu}-1}

that is congruent to +aμ+a^{\mu} or aμ-a^{\mu} modulo pp. This way, we can find the integer tt, and thus determine hh.

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.