Найти порядок числа по модулю

Предмет: Математика
Раздел: Теория чисел (Модульная арифметика, порядок элемента по модулю)

Задание:
В упражнении 115, пункт б, требуется найти порядок числа [a = 18] по модулю [m = 29].

Теория:

Порядок числа [a] по модулю [m] — это наименьшее положительное целое число [k], такое что:

 [a^k \equiv 1 \pmod{m}] 

Порядок существует только если [\gcd(a, m) = 1], то есть [a] и [m] взаимно просты.

Шаг 1: Проверим взаимную простоту чисел 18 и 29

 \gcd(18, 29) = 1 

Значит, порядок существует.

Шаг 2: Найдём порядок числа 18 по модулю 29

Для этого нам нужно найти наименьшее [k], при котором:

 [18^k \equiv 1 \pmod{29}] 

Порядок [k] делит [\varphi(29)], где [\varphi] — функция Эйлера.

Так как 29 — простое число, то:

 \varphi(29) = 28 

Следовательно, возможные значения порядка — делители числа 28:

 k \in \{1, 2, 4, 7, 14, 28\} 

Проверим по порядку:

Проверка:

1. [18^1 \equiv 18 \not\equiv 1 \pmod{29}]
2. [18^2 = 324 \Rightarrow 324 \mod 29 = 324 - 11 \cdot 29 = 324 - 319 = 5 \Rightarrow 18^2 \equiv 5 \pmod{29}]
3. [18^4 = (18^2)^2 = 5^2 = 25 \Rightarrow 18^4 \equiv 25 \pmod{29}]
4. [18^7 = (18^4)(18^2)(18) = 25 \cdot 5 \cdot 18 = 2250]
   Вычислим [2250 \mod 29]:
   2250 \div 29 \approx 77.59 \Rightarrow 29 \cdot 77 = 2233
   2250 - 2233 = 17 \Rightarrow 18^7 \equiv 17 \pmod{29}
5. [18^{14} = (18^7)^2 = 17^2 = 289 \Rightarrow 289 \mod 29 = 289 - 10 \cdot 29 = 289 - 290 = -1 \Rightarrow 18^{14} \equiv -1 \pmod{29}]
6. [18^{28} = (18^{14})^2 = (-1)^2 = 1 \Rightarrow 18^{28} \equiv 1 \pmod{29}]

Ответ:

Наименьшее [k], при котором [18^k \equiv 1 \pmod{29}], — это [28].

Ответ:
[\text{Порядок числа } 18 \text{ по модулю } 29 \text{ равен } 28].