Показатели чисел и классов вычетов по данному модулю

§1. Показатели классов и чисел по данному модулю

Определение. Пусть (a,m) = 1, m N. Показателем (порядком) числа а по модулю m называют наименьшее натуральное число n такое, что аⁿ ≡l(modm). Обозначают Р_m(а).

Пример. Найдём показатель числа 3 по модулю 11. 3²≡-2(mod 11), 3³≡5(mod 11), 3⁴≡4(mod 11), 3⁵≡1(mod 11). Следовательно, P₁₁(3)=5

Свойства показателей

1. Если а≡b(modm), то Р_m (а) = Р_m (b)

Доказательство. Так как аⁿ≡bⁿ(modm) для любого n N, то aⁿ≡ l(modm) тогда и только тогда, когда bⁿ ≡ l(mod m).

Из этого свойства следует, что все элементы одного класса по модулю m имеют один и тот же порядок. Можно говорить о порядке класса. Заметил, что условие аⁿ ≡ l(modm) может быть записано в виде(ā)ⁿ= . И в мультипликативной группе G_m классов вычетов, взаимно простых с модулем, n является порядком элемента ā.

2. Если а^s≡l(modm) то s делится на Р_m(а).

Доказательство. Пусть Р_m (а) = n, аⁿ l(modm). Разделим s с остатком на n: s = nq + r, 0 r<n;a^s =(aⁿ)^q a^r ≡a^r≡l(modm). Если r≠0, то получим противоречие с определением порядка числа. Следовательно, r = 0 и s n.

3. φ(m) P_m(a)

Доказательство. Так как (а,m)= 1, то по теореме Эйлера a^φ(m)≡1(modm). По свойству 2 φ(m) P_m(a).

4. Если Р(a) = к, Р(b) =l и k и l взаимно простые числа, то P(ab) = kl.

Доказательство. (аb)^kl =(a^k)^l(b^l)^k≡1(mod m). Пусть P(ab) = s, s kl. (ab)^sk l(mod m),(ab)^sk = (a^k)^sb^sk≡ b^sk (mod m), b^sk≡ l(mod m). Следовательно, sk l (свойство 2). Ho (k,l)= 1, поэтому s l. Аналогично, взяв (ab)^sl, доказываем, что s k. Так как (k,l)=1, то s kl, то есть s kl, поэтому s=kl.

5. Пусть (а,m) = 1. a^s ≡ a^r(modm) тогда и только тогда, когда s ≡ r (mod P(a)).

Доказательство. Пусть, например, r< s. Разделим обе части сравнения на а^r, взаимно простое с m. a^s-r l(modm). (s -r) P(a) (свойство 2), то есть s ≡r(modР(а)). Обратно, если s≡ г (mod Р(а)), то есть s = г + P(a)t, t N, То а^s = а^r () ≡ (mod m).

6. Если Р(а)= n и (n,k) = d, k N, то P(a^k)=n/d.

Доказательство. Если (a^k)^s = l(modm), то ks n. Пусть k =dk₁, n = dn₁. Так как dk₁s dn₁, то к₁s n₁ (свойство делимости 15). Но (k₁,n₁)= 1, следовательно, s n₁, s n₁. А так как (a^k)ⁿ₁=(a^k)^n/d=(aⁿ)^k/d≡1(modm),то s=n₁=n/d.

7. Если P(a)=n и (n,k)=1, k N, тоP(a^k)=n(следует из 6).

8. ЕслиP(a)=n, то числа a,a²,..,aⁿ попарно не сравнимы по модулю m.

Доказательства.aⁱ≡a^j (modm) тогда и только тогда, когда i≡j(modn)(свойство 5). Но среди чисел 1,2,…,n нет сравнимых по модулю n. Примеры. Найдём порядки чисел по модулю 13. Так как φ(m) P_m(a)(свойство 2) и φ(13)=12, то порядки чисел по модулю13 - делители числа 12. (2,13)=1. найдем порядок числа 2. По модулю 13 верны сравнения: 2²≡4, 2³≡8, 2⁴≡3, 2⁶≡-1, 2¹²≡1. Следовательно, P(2)=12. Такой же порядок имеют числа 2^k, где (k,12)=1(свойство 7 порядков), то есть числа 2⁵, 2⁷. 2¹¹. A так как по модулю 13 верно: 2⁵≡ 6, 2⁷≡11, 2¹¹≡ 7, то P(6)=P(11)=P(7)= 12. Если (k,12) = 3, то числа 2^k имеют порядок 12/3=4 (свойство 6 порядков). Это числа 2³ и 2⁹

2³=8, 2⁹≡5(mod13) поэтому P(8)=P(5)=4. Порядок 3=12/4 имеют 2⁴ и 2⁸. Откуда P(3)=P(9) = 3. Порядок 2=12/6 имеет 2⁶ или число 12. Порядок 6 = 12/2 имеют 2² = 4 и 2¹⁰≡10(mod13). Учитывая, что P(l)= 1, найдены порядки представителей всех классов по модулю 13, взаимно простых с модулем.