Maths Olympiad Prep

Library / /383 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

Example 1 Construct the index table for modulo 23 with primitive root 5.

保留源文本的换行和格式,直接输出翻译结果。

(注意:最后一句为中文,可能是注释或说明,翻译时可忽略或根据上下文调整。)

Example 1 Construct the index table for modulo 23 with primitive root 5.

(Keep the original text's line breaks and format, and output the translation directly.)

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

Solution

From Example 1 in §2, we know that 5 is a primitive root modulo 23, and φ(23)=22\varphi(23)=22. First, list Table 1 in the order of indices, as it is easier to compute the absolute least residues of 5j5^{j} modulo 23. Arranging according to the size order of the absolute least reduced residue system, Table 1 becomes Table 2.

Table 1
γ23,5(a)012345678910\hlinea1521043867119δ23(a)122112211221122112211γ23,5(a)1112131415161718192021\hlinea1521043867119δ23(a)211221122112211221122\begin{array}{|c|rrrrrrrrrrrr|} \hline\gamma_{23,5}(a) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hlinea & 1 & 5 & 2 & 10 & 4 & -3 & 8 & -6 & -7 & 11 & 9 \\ \hline\delta_{23}(a) & 1 & 22 & 11 & 22 & 11 & 22 & 11 & 22 & 11 & 22 & 11 \\ \hline \hline\gamma_{23,5}(a) & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ \hlinea & -1 & -5 & -2 & -10 & -4 & 3 & -8 & 6 & 7 & -11 & -9 \\ \hline\delta_{23}(a) & 2 & 11 & 22 & 11 & 22 & 11 & 22 & 11 & 22 & 11 & 22 \\ \hline \end{array}

Table 2
\hlinea1110987654321γ23.5(a)2014211787121551311δ23(a)111122221122112222222\hlinea1234567891011γ23.5(a)021641181961039δ23(a)111111122112211112222\begin{array}{|c|rrrrrrrrrrr|} \hlinea & -11 & -10 & -9 & -8 & -7 & -6 & -5 & -4 & -3 & -2 & -1 \\ \hline\gamma_{23.5}(a) & 20 & 14 & 21 & 17 & 8 & 7 & 12 & 15 & 5 & 13 & 11 \\ \hline\delta_{23}(a) & 11 & 11 & 22 & 22 & 11 & 22 & 11 & 22 & 22 & 22 & 2 \\ \hline \hlinea & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline\gamma_{23.5}(a) & 0 & 2 & 16 & 4 & 1 & 18 & 19 & 6 & 10 & 3 & 9 \\ \hline\delta_{23}(a) & 1 & 11 & 11 & 11 & 22 & 11 & 22 & 11 & 11 & 22 & 22 \\ \hline \end{array}

From the table, we know that the primitive roots modulo 23 (i.e., elements with order 22) are 10, and they are:
9,8,6,4,3,2,5,7,10,11-9,-8,-6,-4,-3,-2,5,7,10,11

Elements with order 11 are 10, and they are:
11,10,7,5,2,3,4,6,8,9-11,-10,-7,-5,2,3,4,6,8,9

The element with order 2 is one: -1. The element with order 1 is one: 1.
Regarding the index sets γa,1,g0(1)(a),γa,1,g0(0)(a)\gamma_{a,-1, g_{0}}^{(-1)}(a), \gamma_{a,-1, g_{0}}^{(0)}(a) for m=2a(α3)m=2^{a}(\alpha \geqslant 3), we only discuss the case g0=5g_{0}=5, and denote them simply as γ(1)(a),γ(0)(a)\gamma^{(-1)}(a), \gamma^{(0)}(a).

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.