🗊Презентация Приведенная система вычетов

Приведенная система вычетов

Определение Числа одного и того же класса по модулю М имеют с модулем один и тот же общий наибольший делитель.  Особенно важны классы, для которых этот делитель равен единице, т.е. классы, содержащие числа, взаимно простые с модулем. Взяв от каждого такого класса по одному вычету, получим приведенную систему вычетов по модулю М. Приведенную систему вычетов, следовательно, можно составить из чисел полной системы, взаимно простых с модулем. Обыкновенно приведенную систему вычетов выделяют из системы наименьших неотрицательных вычетов: 0,1, . . ., М-1. Так как среди этих чисел число взаимно простых с М есть f(М), то число чисел приведенной системы, равно как и число классов, содержащих числа, взаимно простые с модулем, есть f(М).

Пример Пример.  Приведенная система вычетов по модулю 42 будет    1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Функция Эйлера Функция Эйлера ϕ(a) есть количество чисел из ряда 0, 1, 2,..., a–1, взаимно простых с a.

Лемма Пусть  Тогда: в частности, φ(pα) = pα–pα-1, φ(p) = p–1.

Лемма2  1) Любые ϕ(m) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m. 2) Если d(a, m) = 1 и x пробегает приведенную систему вычетов по модулю m, то аx так же пробегает приведенную систему вычетов по модулю m. Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ϕ(m) штук. Ясно также, что все они взаимно просты с модулем, ибо d(a, m)=1, d(x,m)=1 ⇒d(ax, m)=1. Значит, числа аx образуют приведенную систему вычетов.

Лемма3 Пусть m1 , m2 , ..., mk – попарно взаимно просты и m1 m2 ...mk =M1m1 =M2 m2=...=Mk mk , где Mj =m1 ...mj-1 mj+1 ...mk 1) Если x1 , x2 , ..., xk пробегают полные системы вычетов по модулям m1 , m2 , ..., mk соответственно, то значения линейной формы M1 x1 +M2 x2 + ...+Mkxk пробегают полную систему вычетов по модулю m= m1 m2 ...mk. 2) Если ξ1 , ξ2 , ..., ξk пробегают приведенные системы вычетов по модулям m1 , m2 , ..., mk соответственно, то значения линейной формы M1ξ1 +M2ξ2 + ...+M k ξk пробегают приведенную систему вычетов по модулю m= m1 m2 ...mk.

Лемма4 Пусть x1 , x2 , ..., xk , x пробегают полные, а ξ1 , ξ2 ,..., ξk , ξ – пробегают приведенные системы вычетов по модулям m1, m2,...,mk и m=m1 m2 ...mk соответственно, где (m i m j )=1 при i ≠ j . Тогда дроби {x1 /m1 +x2 /m2 +...+xk /mk} совпадают с дробями {x/m} , а дроби {ξ1 /m1 +ξ2 /m2 +...+ ξk /mk} совпадают с дробями {ξ/m}. Обозначим через εk k -ый корень m- ой степени из единицы:

Теорема1 Пусть m>0 – целое число, a  Z , x пробегает полную систему вычетов по модулю m. Тогда, если а кратно m, то в противном случае, при а не кратном m,

Теорема2 Пусть m>0 – целое число, ξ пробегает приведенную систему вычетов по модулюm. Тогда (сумма первообразных корней степени m):                   где μ(m) – функция Мебиуса.