Первісні корені та індекси. Загальні теореми

Первісні корені та індекси

1.  Загальні теореми

a.  При (a,m)=1 існує додатнє γ з умовою α^γ≡1(modm), наприклад (теорема Ейлера), γ=φ(m). Найменше з них зветься: показник, якомуaналежить по модулю m.

b.  Якщо a по модулю m належить показнику δ, то числа 1=a⁰,a¹, …, a^δ-1 по модулю m непорівнянні.

Дійсно, з a^l≡ a^k(modm), 0≤k<l<δ, слідує a^l-k≡1(mod m); 0<1-k<δ, що протирічить означенню δ.

c.  Якщо a по модулю m належить показнику δ, то a^γ≡a^γ’(mod m)тоді і тільки тоді, коли γ≡γ’(mod δ); зокрема (при γ’=0), a^γ≡1(mod m) тоді і тільки тоді, коли γ ділиться на δ.

Дійсно, нехай r і r₁ найменші додатні лишки чисел γ і γ' по модулю δ; тоді деяких q та q₁маємо γ=δq+r, γ'=δq₁+r₁. Звідси та з a^δ≡1(modm) слідує

a^γ=(a^δ)^qa^r≡a^r(mod m)

a ^γ=(a^δ)^q≡(mod m)

Отже, a^γ≡a^γ’(mod m) тоді і тільки тоді, коли a^r≡(mod m), тобто (b), коли r=r₁.

d.  Нехай a по модулю m належить показнику δ. Тоді з с (γ'=0) та з a^φ(m)≡1(mod m) слідує, що φ(m) ділиться на δ. Таким чином, показники, яким числам належать по модулю m, є дільниками φ(m). Найбільших з цих дільників є сама φ(m). Числа, які належать показнику φ(m) (якщо такі існують), називаються первісними коренями по модулю m.

2.  Первісні корені по модулям p^αта 2p^α

a.  Нехай p – просте непарне число та α≥1. Доведемо існування первісних коренів по модулям p^α та 2p^α.

b.  Якщо x(mod m) належить показнику ab, то x^a належить показнику b.

Дійсно, нехай x^a належить показнику δ. Тоді (x^a)^δ≡1(mod m), звідки x^aδ ≡ 1(mod m); отже (1,c), a δ ділиться на ab, тобто δ ділиться на b. З іншої сторони, x^ab ≡ 1(mod m), звідси (x^a)^b≡ 1(mod m); отже (1,c), b ділиться на δ. Значить δ=b.

c.  Якщо x по модулю mналежить показнику a, а y – показнику b, причому (a,b)=1, то xy належить показнику ab.

Дійсно, нехай xy належить показнику δ. Тоді (xy)^δ≡1(modm). Звідси x^bδy^bδ≡1(modm)(c, 1)x^bδ≡1(modm). Отже, (c, 1)bδділиться на a. І так як (b,a)=1, то δ ділиться на a. Так само знаходимо, що δ ділиться і на ab. З іншої сторони, з (xy)^ab≡1(modm)маємо (c, 1), що abділиться на δ. Отже δ=ab.

d.  Існують первісні корені по модулю p.

Дійсно, нехай

δ₁, δ₂, …, δ_r                        (1)

-всі різні показники, котрим по модулю p належать числа 1, 2, …, (p-1). Нехай τ – найменше спільне кратне цих показників та

- його канонічний розклад. Кожен множник  цього розкладу ділить хоча б одне число δ_j ряда (1), котре може бути представлено у вигляді: . Нехай ξ_j – однеізчисел ряду 1, 2, …, (p-1), які належать показнику δ_j. Згідно з b число належить показнику , згідно з c добуток g=ξ₁ξ_2…ξ_kналежить показнику . Отже (d, 1) τ – дільник p-1.

Але оскільки числа (1) ділять τ, всі 1, 2, …, (p-1) є розв’язками (c, 1) конгруенції x^τ≡1(mod p); отже будемо мати p-1≤τ. Звідси, τ=p-1, та g–первісний корінь.

e.  Нехай g – первісний корінь по модулю p. Можемо вказати t з умовою, яка визначена рівністю (g+pt)^p-1=1+pu, не ділиться на p. Відповідні g+pt буде первісним коренем по модулю p^α при будь яких α>1.

Дійсно, маємо

g^p-1=1+pT₀                            (2)

(g+pt)^p-1=1+p(T₀-g^p-2t+pT)=1+pu

де, одночасно з t, u пробігає повну систему лишків по модулю p. Тому можна вказати t з умовою, що u не ділиться на p. При такому t з (2) виводимо

(g+pt)^p(p-1)=(1+pu)^p=1+p²u₂

………………………………………………………….                         (3)

де всі u₂, u₃, …, u_α також не діляться на p. Нехай g+pt належить показнику δ по модулю p^α. Тоді маємо (g+pt)^δ≡1(modp^α), звідси знаходимо g ^δ≡1(modp). Тому (1,c) δ ділиться на p-1 та, будучи (1,d) дільником числа φ(p^α)=p^α-1(p-1), повинно мати вигляд δ=p^r-1(p-1), де r – одне з чисел 1, …, α. Так як рівності (2) та (3) показують, що конгруенція

вірно при r=α та невірно при r<α, то (d, 1)δ=p^α-1(p-1)=φ(p^α) та g+pt – первісний корінь по p^α.

f.  Нехай α≥1 та g – первісний корінь по модулю p^α. Непарне g₀ зчисел g та g+p^α ,буде первісним коренем по модулю 2p^α.

Дійсно, φ(p^α) та φ(2p^α) рівні між собою (маємо φ(2p^α)=φ(2)φ(p^α)=φ(p^α)); їх спільне значення позначають буквою c. Далі легко впевнитися що конгруенції  та  можуть виконуватися лише одночасно (  ділиться на 2). А так як g₀ – первісний корінь по модулю p^α і перша конгруенція вірна при r=c і невірна при r<c, тим самим і друга конгруенція вірна при r=c і невірна при r<c та g₀–первісний корінь по модулю 2p^α.

3.  Пошук первісних коренів по модулям p^αта 2p^α

a.  Первісні корені по модулям p^αта 2p^α, де p–просте непарне число і α≥1, можна знайти, користуючись наступною загальною теоремою:

Нехай c=φ(m) та q₁, q₂, …, q_k – різні прості дільники числа c. Для того, щоб число g взаємно просте з m, було первісним коренем по модулю m, необхідно та достатньо, щоб це g не задовольняло ні одну з конгруенцій.