Maths Olympiad Prep

Library / /468 of 520

Number theory Difficulty 7.1 National olympiad, round 2 Prove it

Property VI Let α3,1d2α2\alpha \geqslant 3,1 \leqslant d \mid 2^{\alpha-2}, and let ψ(d)\psi(d) denote the number of elements of order dd in a reduced residue system modulo 2α2^{\alpha}. We have
ψ(d)={1,d=13,d=22φ(d),2<d2α2\psi(d)=\left\{\begin{array}{ll} 1, & d=1 \\ 3, & d=2 \\ 2 \varphi(d), & 2<d \mid 2^{\alpha-2} \end{array}\right.

Solution

We take the reduced residue system modulo 22^{\circ} given by formula (4) (g0=5)\left(g_{0}=5\right). From formula (17), we know that the sufficient and necessary condition for δ2a(a)=1\delta_{2^{a}}(a)=1 is γ(0)(a)=γ(1)(a)=0\gamma^{(0)}(a)=\gamma^{(-1)}(a)=0, i.e., a1(mod2a)a \equiv 1\left(\bmod 2^{a}\right). Therefore, formula (19) holds. From formula (17), we know that the sufficient and necessary condition for δ2a(a)=2\delta_{2^{a}}(a)=2 is either
γ(0)(a)=0,γ(1)(a)=1γ(0)(a)=2a3,γ(1)(a)=0,1\begin{array}{cc} \gamma^{(0)}(a)=0, & \gamma^{(-1)}(a)=1 \\ \gamma^{(0)}(a)=2^{a-3}, & \gamma^{(-1)}(a)=0,1 \end{array}

Thus, there are three such elements in a reduced residue system, so formula (19) also holds. When d>2,d2a2d>2, d \mid 2^{a-2}, we can set d=2j,1<j2a2d=2^{j}, 1<j \leqslant 2^{a-2}. From formula (17), we know that the sufficient and necessary condition for δ2a(a)=d=2j\delta_{2^{a}}(a)=d=2^{j} is
(γ(0)(a),2a2)=2a2j,0<γ(0)(a)<2a2.\left(\gamma^{(0)}(a), 2^{a-2}\right)=2^{a-2-j}, \quad 0<\gamma^{(0)}(a)<2^{a-2} .

Let γ(0)(a)=2a2jt\gamma^{(0)}(a)=2^{a-2-j} \cdot t, the above equation becomes
(t,2j)=1,0<t<2j\left(t, 2^{j}\right)=1, \quad 0<t<2^{j}

There are φ(2j)=φ(d)\varphi\left(2^{j}\right)=\varphi(d) such tt values, and since γ(1)(a)\gamma^{(-1)}(a) can take 0 or 1, there are exactly 2φ(d)2 \varphi(d) elements with index d(2<d2a2)d\left(2<d \mid 2^{a-2}\right) in a reduced residue system.

Similar to the index table for a modulus mm with a primitive root, we can list the index group table for modulus 2a(α3)2^{a}(\alpha \geqslant 3), where the index δ(a)=δ2e(a)\delta(a)=\delta_{2^{e}}(a) is derived from formula (17).

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.