Найти первообразные корни для модуля 41 Проверит...

Сразу дам ответ, а потом аккуратно разберём теорию и таблицу.

---

1. Что такое первообразный корень по модулю 41

Число $g$ первообразный корень по модулю 41, если меньший положительный показатель $k$, при котором
$g^k \equiv 1 \pmod{41}$, равен $\varphi(41)$.

Такой показатель называется порядком числа $g$ по модулю 41.

Так как 41 — простое, то

$$\varphi(41)=41-1=40.$$

Значит, $g$ — первообразный корень $\Leftrightarrow$ порядок $g$ равен 40.

---

2. Теорема из книги (то, что у вас на страницах 415–416)

Пусть $m$ такое, что $\varphi(m)=c$,
а $q_1,\dots,q_s$ — разные простые делители числа $c$.

Тогда число $g$, взаимно простое с $m$, является первообразным корнем по модулю $m$
тогда и только тогда, когда

$$g^{c/q_i} \not\equiv 1 \pmod{m} \quad \text{для всех } i.$$

Почему?
Порядок $g$ всегда делит $\varphi(m)=c$.
Если порядок меньше $c$, то он делит какое-то число вида $c/q_i$, значит $g^{c/q_i}\equiv 1$. Обратное рассуждение тоже верно.

---

3. Применяем к модулю 41

У нас $\varphi(41)=40$ и

$$40 = 2^3\cdot 5.$$

Разные простые делители числа 40 — это $2$ и $5$.

По теореме:

$g$ — первообразный корень по модулю 41
$\iff$

$$\begin{cases} g^{40}\equiv 1 \pmod{41},\\[2mm] g^{40/2}=g^{20}\not\equiv 1 \pmod{41},\\[2mm] g^{40/5}=g^{8}\not\equiv 1 \pmod{41}. \end{cases}$$

В тетради у вас, скорее всего, опечатка: проверять нужно степени 8 и 20,
а 40-я степень как раз должна быть равна 1 (по малой теореме Ферма).

---

4. Проверяем кандидатов: 2, 3, 4, 5, 6 …

Берём числа, взаимно простые с 41: 2, 3, 4, 5, 6, …

4.1. Число 2

Считаем степени, удобно возводить по шагам:

$$\begin{aligned} 2^5 &= 32 \equiv -9 \pmod{41},\\ 2^{10} &= (-9)^2 =81\equiv -1 \equiv 40 \pmod{41},\\ 2^{20} &= (-1)^2 =1 \pmod{41}. \end{aligned}$$

То есть $2^{20}\equiv 1$, поэтому порядок 2 делит 20, а не 40.
2 — не первообразный корень.

---

4.2. Число 3

$$\begin{aligned} 3^2 &= 9,\\ 3^4 &= 9^2 = 81 \equiv -1 \equiv 40 \pmod{41},\\ 3^8 &= (-1)^2 =1 \pmod{41}. \end{aligned}$$

Здесь $3^8 \equiv 1$, значит порядок 3 делит 8.
3 — не первообразный корень.

---

4.3. Число 4

Заметьте, что $4 = 2^2$. Порядок 4 делит порядок 2, то есть делит 20.

Можно посчитать напрямую:

$$4^{10} = (2^2)^{10} = 2^{20} \equiv 1 \pmod{41},$$

значит порядок 4 $\mid 10 < 40$.
4 — не первообразный корень.

---

4.4. Число 5 (для примера)

$$\begin{aligned} 5^2 &= 25,\\ 5^4 &= 25^2 = 625 \equiv 625-41\cdot 15 = 625-615 =10,\\ 5^8 &= 10^2=100\equiv 100-41\cdot 2=18,\\ 5^{20} &= 5^{8}\cdot 5^{8}\cdot 5^{4} \equiv 18\cdot 18\cdot 10 \equiv 1 \pmod{41}. \end{aligned}$$

(Я тут опускаю промежуточные вычитания 41, но в тетради их можно расписать.)

Получили $5^{20}\equiv 1$, значит порядок 5 делит 20.
5 — не первообразный корень.

---

4.5. Число 6 — наш первый первообразный корень

Теперь проверяем 6.

$$\begin{aligned} 6^2 &= 36,\\ 6^4 &= 36^2 =1296 \equiv 1296-41\cdot 31=1296-1271=25,\\ 6^5 &= 25\cdot 6 =150 \equiv 150-41\cdot 3=27,\\ 6^8 &= 6^4\cdot 6^4 \equiv 25^2 = 625 \equiv 625-41\cdot 15=10. \end{aligned}$$

Итак,

$$6^8 \equiv 10 \not\equiv 1 \pmod{41}.$$

Теперь степень 20:

$$\begin{aligned} 6^{10} &= 6^8\cdot 6^2 \equiv 10\cdot 36 = 360 \equiv 360-41\cdot 8=32,\\ 6^{20} &= (6^{10})^2 \equiv 32^2 =1024 \equiv 1024-41\cdot 25 =1024-1025=-1\equiv 40. \end{aligned}$$

То есть

$$6^{20} \equiv 40 \not\equiv 1 \pmod{41}.$$

И наконец степень 40:

$$6^{40} = (6^{20})^2 \equiv 40^2 =1600 \equiv 1600-41\cdot 39=1600-1599=1.$$

Итак:

• $6^{40}\equiv 1$,
• $6^{20}\not\equiv 1$,
• $6^{8}\not\equiv 1$.

По теореме это значит, что 6 — первообразный корень по модулю 41.

---

5. Таблица степеней 6 по модулю 41 (как в книге)

Построим таблицу значений $6^k \pmod{41}$ для $k=1,\dots,40$:

$k$	$6^k \pmod{41}$	$k$	$6^k \pmod{41}$
1	6	21	35
2	36	22	5
3	11	23	30
4	25	24	16
5	27	25	14
6	39	26	2
7	29	27	12
8	10	28	31
9	19	29	22
10	32	30	9
11	28	31	13
12	4	32	37
13	24	33	17
14	21	34	20
15	3	35	38
16	18	36	23
17	26	37	15
18	33	38	8
19	34	39	7
20	40	40	1

Из таблицы видно:

• в степенях $6^1, 6^2, \dots, 6^{40}$ перебираются все числа от 1 до 40 ровно по одному разу;
• только при $k=40$ мы впервые получаем 1, значит порядок 6 равен 40.

Это и есть «табличное» подтверждение, как у вас на фото.

---

6. Как из одного корня получить все остальные

Общее правило:
если $g$ — первообразный корень по модулю $m$ и $\varphi(m)=c$,
то все первообразные корни имеют вид

$$g^k \pmod{m},\quad \text{где } 1\le k\le c,\ \gcd(k,c)=1.$$

У нас $m=41$, $c=\varphi(41)=40$.
Числа $k$ от 1 до 40, взаимно простые с 40, это

$$k\in\{1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39\}.$$

Подставляем $g=6$ и считаем $6^k \pmod{41}$ для этих $k$. Получаем все первообразные корни по модулю 41:

$$\boxed{ 6,\ 7,\ 11,\ 12,\ 13,\ 15,\ 17,\ 19,\ 22,\ 24,\ 26,\ 28,\ 29,\ 30,\ 34,\ 35 }$$

Их ровно 16 штук — это равно $\varphi(40)$, как и должно быть.

---

7. Краткий алгоритм для любого простого модуля $p$

1. Найти $\varphi(p)=p-1$.
2. Разложить $p-1$ на простые множители: $$p-1 = q_1^{\alpha_1}\dots q_s^{\alpha_s}.$$
3. Брать кандидатов $g=2,3,4,\dots$, взаимно простых с $p$,
   и проверять: $$g^{(p-1)/q_i} \not\equiv 1 \pmod{p} \quad \text{для всех } i.$$ Первый, кто проходит проверку, — первообразный корень.
4. Все остальные получить как $g^k$ при $\gcd(k,p-1)=1$.

---

Если хочешь, в следующем сообщении могу:

• разобрать ещё один пример (другой модуль),
• или подробно расписать, как именно считать степени «вручную», чтобы было удобно делать в тетради без калькулятора.

Ааа, всё, понял, о чём ты 🌟
Ты прав: в таблице по книге в строках стоят числа 2,3,4,5,…, а в столбцах их степени (8-я, 20-я, 40-я и т.п.).
Раньше я делал таблицу по степеням одного числа, теперь сделаем именно так, как у вас в конспекте.

---

1. Логика метода (откуда вообще берутся степени 8 и 20)

Модуль $41$ — простое число, значит

$$\varphi(41)=41-1=40.$$

Число $g$ будет первообразным корнем по модулю 41, если его порядок равен 40, то есть:

\text{наименьшее }k>0,\ \text{что } g^k\equiv1\pmod{41},\ \textравно }40.

Разложение:

$$40 = 2^3\cdot 5,\quad\text{простые делители }40:\ 2,\ 5.$$

Теорема говорит:

$g$ — первообразный корень по модулю 41
⇔
$g^{40} \equiv 1 \pmod{41}$ и одновременно
$g^{40/2}=g^{20}\not\equiv 1$,
$g^{40/5}=g^{8}\not\equiv 1$.

То есть мы должны проверить две степени:

$$g^8\not\equiv1,\quad g^{20}\not\equiv1 \pmod{41}.$$

А вот $g^{40}\equiv1$ для любого $g$, взаимно простого с 41 (малая теорема Ферма), так что последний столбец таблицы всегда будет равен 1 — его можно считать «контрольным».

Если где-то в задании написано «$g^8$ и $g^{40}$ не сравнимы с 1», это именно опечатка: $g^{40}\not\equiv1$ по модулю 41 быть не может.

---

2. Как строится ТАБЛИЦА «как у вас»

Мы просто перебираем кандидатов $g = 2,3,4,5,6,\dots$
и для каждого считаем два значения:

• $g^8 \pmod{41}$
• $g^{20} \pmod{41}$

Если

• $g^8 \neq 1$,
• $g^{20} \neq 1$,

то $g$ — первообразный корень.

Сделаем так для первых чисел. Я покажу вычисления, как это делать руками.

---

Кандидат $g=2$

Считаем удобно по шагам:

$$\begin{aligned} 2^5 &= 32 \equiv -9 \pmod{41},\\ 2^{10} &= (-9)^2 = 81 \equiv -1 \equiv 40 \pmod{41},\\ 2^{20} &= (2^{10})^2 \equiv (-1)^2 = 1 \pmod{41}. \end{aligned}$$

А $2^8 = 256 \equiv 256-41\cdot6 = 10$.

Итак:

• $2^8 \equiv 10 \neq 1$,
• но $2^{20} \equiv 1$ ⇒ порядок 2 делит 20, а не 40.

Вывод: $2$ — не первообразный корень.

---

Кандидат $g=3$

$$\begin{aligned} 3^2 &= 9,\\ 3^4 &= 9^2 = 81 \equiv -1 \equiv 40 \pmod{41},\\ 3^8 &= (3^4)^2 \equiv (-1)^2 = 1 \pmod{41}. \end{aligned}$$

Здесь уже $3^8\equiv1$, значит порядок 3 делит 8.

Вывод: $3$ — не первообразный корень.

(Для полноты: $3^{20}=(3^4)^5\equiv(-1)^5=-1$, $3^{40}=1$.)

---

Кандидат $g=4$

Можно использовать, что $4=2^2$, а порядок 4 делит порядок 2, но давай чуть посчитаем:

$$\begin{aligned} 4^2 &= 16,\\ 4^4 &= 16^2=256\equiv10,\\ 4^8 &= 10^2 = 100 \equiv 18 \pmod{41},\\ 4^{10} &= 4^8\cdot 4^2 \equiv 18\cdot 16 = 288 \equiv 288-41\cdot7=1,\\ 4^{20} &= (4^{10})^2 \equiv 1. \end{aligned}$$

Вывод: $4$ — не первообразный корень (порядок делит 10).

---

Кандидат $g=5$

$$\begin{aligned} 5^2 &= 25,\\ 5^4 &= 25^2 = 625 \equiv 625-41\cdot15=10,\\ 5^8 &= 10^2 =100\equiv18,\\ 5^{10} &= 5^8\cdot5^2 \equiv 18\cdot25=450\equiv450-41\cdot10=40\equiv-1,\\ 5^{20} &= (5^{10})^2 \equiv (-1)^2 =1. \end{aligned}$$

Вывод: $5$ — не первообразный корень.

---

Кандидат $g=6$

Вот тут начинается самое интересное:

$$\begin{aligned} 6^2 &= 36 \equiv -5 \pmod{41},\\ 6^4 &= (-5)^2 = 25,\\ 6^8 &= 25^2 = 625 \equiv 10 \pmod{41},\\ 6^{10} &= 6^8\cdot6^2 \equiv 10\cdot36 = 360 \equiv 360-41\cdot8=32\equiv -9,\\ 6^{20} &= (6^{10})^2 \equiv (-9)^2 = 81 \equiv -1 \equiv 40 \pmod{41},\\ 6^{40} &= (6^{20})^2 \equiv (-1)^2 = 1 \pmod{41}. \end{aligned}$$

Смотрим условия:

• $6^8 \equiv 10 \neq 1$,
• $6^{20} \equiv 40 \neq 1$,
• $6^{40}\equiv1$.

Все как надо ⇒ 6 — первообразный корень по модулю 41.

---

3. Таблица в том виде, как ты описываешь

Соберём данные для первых кандидатов в табличку:

$$\varphi(41)=40,\quad \text{делители }40:2,5.$$

$g$	$g^8 \pmod{41}$	$g^{20} \pmod{41}$	$g^{40} \pmod{41}$	вывод
2	10	1	1	не первообразный
3	1	40	1	не первообразный (уже 8-я степень =1)
4	18	1	1	не первообразный
5	18	1	1	не первообразный
6	10	40	1	✅ первообразный корень

Дальше можно, если надо, продолжать таблицу для 7, 8, 9, … — но это уже не обязательно: первый найденный корень — 6.

---

4. Как найти ВСЕ первообразные корни модуля 41

Как только у нас есть один корень $g=6$, дальше просто.

Если $\varphi(41)=40$, то все первообразные корни имеют вид

$$6^k \pmod{41},\quad 1\le k\le 40,\ \gcd(k,40)=1.$$

Числа $k$ от 1 до 40, взаимно простые с 40:

$$k\in\{1,3,7,9,11,13,17,19,21,23,27,29,31,33,37,39\}.$$

Подставляя эти показатели и считая $6^k\pmod{41}$, получаем все первообразные корни:

$$\boxed{ 6,\ 7,\ 11,\ 12,\ 13,\ 15,\ 17,\ 19,\ 22,\ 24,\ 26,\ 28,\ 29,\ 30,\ 34,\ 35 }$$

(это совпадает с табличками из интернета/конспекта.)

---

Если хочешь, могу:

• дописать полную табличку $g, g^8, g^{20}$ для всех $g=2,\dots,40$,
• или разобрать ещё один пример с другим модулем, чтобы ты совсем уверенно чувствовал эту тему.

Супер, давай просто дорисуем всю таблицу до $g=40$.

Напоминаю правило:
$g$ — первообразный корень по модулю 41, если
$g^8\not\equiv1\pmod{41}$ и $g^{20}\not\equiv1\pmod{41}$
(а $g^{40}\equiv1\pmod{41}$ по малой теореме Ферма).

---

Таблица для всех $g=2,\dots,40$

$g$	$g^8 \pmod{41}$	$g^{20} \pmod{41}$	$g^{40} \pmod{41}$	вывод
2	10	1	1	не первообразный
3	1	40	1	не первообразный
4	18	1	1	не первообразный
5	18	1	1	не первообразный
6	10	40	1	первообразный
7	37	40	1	первообразный
8	16	1	1	не первообразный
9	1	1	1	не первообразный
10	16	1	1	не первообразный
11	16	40	1	первообразный
12	18	40	1	первообразный
13	10	40	1	первообразный
14	1	40	1	не первообразный
15	18	40	1	первообразный
16	37	1	1	не первообразный
17	16	40	1	первообразный
18	10	1	1	не первообразный
19	37	40	1	первообразный
20	37	1	1	не первообразный
21	37	1	1	не первообразный
22	37	40	1	первообразный
23	10	1	1	не первообразный
24	16	40	1	первообразный
25	37	1	1	не первообразный
26	18	40	1	первообразный
27	1	40	1	не первообразный
28	10	40	1	первообразный
29	18	40	1	первообразный
30	16	40	1	первообразный
31	16	1	1	не первообразный
32	1	1	1	не первообразный
33	16	1	1	не первообразный
34	37	40	1	первообразный
35	10	40	1	первообразный
36	18	1	1	не первообразный
37	18	1	1	не первообразный
38	1	40	1	не первообразный
39	10	1	1	не первообразный
40	1	1	1	не первообразный

---

Отсюда видно, что первообразные корни по модулю 41 (все, у кого в таблице оба значения ≠ 1) — это:

$$6,\ 7,\ 11,\ 12,\ 13,\ 15,\ 17,\ 19,\ 22,\ 24,\ 26,\ 28,\ 29,\ 30,\ 34,\ 35.$$

Если хочешь, могу по шагам расписать вычисления именно для какого-нибудь одного числа из таблицы (например, как руками получить $7^8$ и $7^{20}$ по модулю $41$).