Maths Olympiad Prep

Library / /443 of 520

Number theory Difficulty 6.9 National olympiad Prove it

Theorem 4 Let c=φ(2l)=2l1,l1,r1,,rcc=\varphi\left(2^{l}\right)=2^{l-1}, l \geqslant 1, r_{1}, \cdots, r_{c} be the reduced residue system modulo 2l2^{l}. We have
r1rc{1(mod2l),l=1,2,1(mod2l),l3.r_{1} \cdots r_{c} \equiv\left\{\begin{array}{ll} -1\left(\bmod 2^{l}\right), & l=1,2, \\ 1\left(\bmod 2^{l}\right), & l \geqslant 3 . \end{array}\right.

Solution

Proof: When l=1,2l=1,2, the conclusion can be directly verified. Now assume l3l \geqslant 3. Similarly, by property VIII of §1 and the subsequent explanation, for each rir_{i}, there must be a unique rjr_{j} such that
rirj1(mod2l)r_{i} r_{j} \equiv 1\left(\bmod 2^{l}\right)
The necessary and sufficient condition for ri=rjr_{i}=r_{j} is
ri21(mod2l),r_{i}^{2} \equiv 1\left(\bmod 2^{l}\right),

which is equivalent to
(ri1)(ri+1)0(mod2l)\left(r_{i}-1\right)\left(r_{i}+1\right) \equiv 0\left(\bmod 2^{l}\right)

Noting that (ri,2)=1\left(r_{i}, 2\right)=1, the above equation becomes
ri12ri+120(mod2l2)\frac{r_{i}-1}{2} \cdot \frac{r_{i}+1}{2} \equiv 0\left(\bmod 2^{l-2}\right)

Noting that
(ri12,ri+12)=1\left(\frac{r_{i}-1}{2}, \frac{r_{i}+1}{2}\right)=1

it follows that the necessary and sufficient condition for ri=rjr_{i}=r_{j} is
ri120(mod2l2) or ri+120(mod2l2),\frac{r_{i}-1}{2} \equiv 0\left(\bmod 2^{l-2}\right) \quad \text { or } \quad \frac{r_{i}+1}{2} \equiv 0\left(\bmod 2^{l-2}\right),

which is equivalent to
ri1(mod2l1) or ri1(mod2l1).r_{i} \equiv 1\left(\bmod 2^{l-1}\right) \quad \text { or } \quad r_{i} \equiv-1\left(\bmod 2^{l-1}\right).

Therefore, in the reduced residue system modulo 2l2^{l}, ri=rjr_{i}=r_{j} only when
ri1,2l1+1,2l11 or 2l1(mod2l).r_{i} \equiv 1,2^{l-1}+1,2^{l-1}-1 \text { or } 2^{l}-1\left(\bmod 2^{l}\right).

Thus, for each rir_{i} in the reduced residue system modulo 2l2^{l}, except for these four numbers (which are pairwise incongruent modulo 2l2^{l}), there must be rjrir_{j} \neq r_{i}. Therefore, except for these four numbers, the c4c-4 numbers in the reduced residue system can be paired off according to equation (9), meaning the product of these c4c-4 numbers is congruent to 1 modulo 2l2^{l}. This, together with equation (10), proves that equation (8) holds for l3l \geqslant 3.

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.