 |
Пункт 17. Полная и приведенная системы вычетов.
|
|
|
|
В предыдущем пункте было отмечено, что отношение º m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности º m (знатоки скажут - "индекс эквивалентности º m ") в точности равно m.
Определение. Любое число из класса эквивалентности º m будем называть вычетом по модулю m. Совокупность вычетов, взятых по одному из каждого класса эквивалентности º m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m. Вычет r называется абсолютно наименьшим, если ïrï наименьший среди модулей вычетов данного класса.
Пример: Пусть m = 5. Тогда:
0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;
-2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.
Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5.
Лемма 1. 1) Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m.
2) Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m, то значения линейной формы аx+b, где b - любое целое число, тоже пробегают полную систему вычетов по модулю m.
Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Чисел аx+b ровно m штук. Покажем, что они между собой не сравнимы по модулю m. Ну пусть для некоторых различных x 1 и x 2 из полной системы вычетов оказалось, что ax 1 +b º ax 2 +b(mod m). Тогда, по свойствам сравнений из предыдущего пункта, получаем:
|
|
|
ax 1 º ax 2 (mod m)
x 1 º x 2 (mod m)
– противоречие с тем, что x 1 и x 2 различны и взяты из полной системы вычетов.
¨
Поскольку все числа из данного класса эквивалентности º получаются из одного числа данного класса прибавлением числа, кратного m, то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.
Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m.
Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит j (m) штук вычетов, где j (m)– функция Эйлера – число чисел, меньших m и взаимно простых с m. Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.
Пример. Пусть m = 42. Тогда приведенная система вычетов суть:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Лемма 2. 1) Любые j (m) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m.
2) Если (a,m) = 1 и x пробегает приведенную систему вычетов по модулю m, то аx так же пробегает приведенную систему вычетов по модулю m.
Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно j (m) штук. Ясно также, что все они взаимно просты с модулем, ибо (a,m)=1, (x,m)=1 Þ (ax.m)=1. Значит, числа аx образуют приведенную систему вычетов.
¨
Таковы определения и основные свойства полной и приведенной систем вычетов, однако в багаже математических знаний существует еще целый ряд очень интересных и полезных фактов, касающихся систем вычетов. Если умолчать про них в этом пункте, то это, боюсь, будет прямым нарушением Закона Российской Федерации об Информации, злонамеренное утаивание которой является, согласно этому закону, административно и, даже, уголовно наказуемым деянием. Кроме того, без знакомства с дальнейшими важными свойствами систем вычетов пункт 17 получится весьма куцым. Продолжим.
|
|
|
Лемма 3. Пусть m 1 , m 2 ,..., m k – попарно взаимно просты и m 1 m 2 ...m k =M 1 m 1 =M 2 m 2 =...=M k m k , где M j =m 1 ...m j-1 m j+1 ...m k
1) Если x 1 , x 2 ,..., x k пробегают полные системы вычетов по модулям m 1 , m 2 ,..., m k соответственно, то значения линейной формы M 1 x 1 +M 2 x 2 +...+M k x k пробегают полную систему вычетов по модулю m=m 1 m 2 ...m k .
2) Если x 1 , x 2 ,..., x k пробегают приведенные системы вычетов по модулям m 1 , m 2 ,..., m k соответственно, то значения линейной формы M 1 x 1 +M 2 x 2 +...+M k x k пробегают приведенную систему вычетов по модулю m=m 1 m 2 ...m k .
Доказательство.
1) Форма M 1 x 1 +M 2 x 2 +...+M k x k принимает, очевидно, m 1 m 2 ...m k =m значений. Покажем, что эти значения попарно несравнимы. Ну пусть
M 1 x 1 +M 2 x 2 +...+M k x k º M 1 x 1 Ñ +M 2 x 2 Ñ +...+M k x k Ñ (mod m)
Всякое M j , отличное от M s , кратно m s . Убирая слева и справа в последнем сравнении слагаемые, кратные m s , получим:
M s x s º M s x s Ñ (mod m s ) Þ x s º x s Ñ (mod m s )
– противоречие с тем, что x s пробегает полную систему вычетов по модулю m s .
2). Форма M 1 x 1 +M 2 x 2 +...+M k x k принимает, очевидно, j (m 1 ) j (m 2 ) ×... × j (m k ) = j (m 1 m 2 ×... × m k )= j (m) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m 1 m 2 ...m k попарно несравнимы. Последнее легко доказывается рассуждениями, аналогичными рассуждениям, проведенным при доказательстве утверждения 1) этой леммы. Так как (M 1 x 1 +M 2 x 2 +...+M k x k ,m s )=(M s x s ,m s )=1 для каждого 1 £ s £ k, то (M 1 x 1 +M 2 x 2 +...+M k x k ,m s )=1, следовательно множество значений формы M 1 x 1 +M 2 x 2 +...+M k x k образует приведенную систему вычетов по модулю m.
¨
Лемма 4. Пусть x 1 , x 2 ,..., x k ,x пробегают полные, а x 1 , x 2 ,..., x k , x – пробегают приведенные системы вычетов по модулям m 1 , m 2 ,..., m k и m=m 1 m 2 ...m k соответственно, где (m i m j )=1 при i ¹ j. Тогда дроби {x 1 /m 1 +x 2 /m 2 +...+x k /m k } совпадают с дробями {x/m}, а дроби { x 1 /m 1 + x 2 /m 2 +...+ x k /m k } совпадают с дробями { x /m}.
|
|
|
Доказательство. Доказательство обоих утверждений леммы 4 легко получается применением предыдущей леммы 3 после того, как вы приведете каждую сумму {x 1 /m 1 +x 2 /m 2 +...+x k /m k } и { x 1 /m 1 + x 2 /m 2 +...+ x k /m k } к общему знаменателю:
{x 1 /m 1 +x 2 /m 2 +...+x k /m k }={(M 1 x 1 +M 2 x 2 +...+M k x k )/m};
{ x 1 /m 1 + x 2 /m 2 +...+ x k /m k }={(M 1 x 1 +M 2 x 2 +...+M k x k )/m},
где M j =m 1 ...m j-1 m j+1 ...m k .
Если теперь принять во внимание, что дробные части чисел, получающихся при делении на модуль m любых двух чисел, сравнимых по модулю m, одинаковы (они равны r/m, где r – наименьший неотрицательный вычет из данного класса), то утверждения настоящей леммы становятся очевидными.
¨
В оставшейся части этого пункта произойдет самое интересное – мы будем суммировать комплексные корни m -ой степени из единицы, при этом нам откроются поразительные связи между суммами корней, системами вычетов и уже знакомой мультипликативной функцией Мебиуса m (m).
Обозначим через e k k -ый корень m- ой степени из единицы:
- эти формы записи комплексных чисел мы хорошо помним с первого курса. Здесь k=0,1,...,m-1 – пробегает полную систему вычетов по модулю m.
Напомню, что сумма e 0 + e 1 +...+ e m-1 всех корней m -ой степени из единицы равна нулю для любого m. Действительно, пусть e 0 + e 1 +...+ e m-1 =a. Умножим эту сумму на ненулевое число e 1 . Такое умножение геометрически в комплексной плоскости означает поворот правильного m -угольника, в вершинах которого расположены корни e 0 , e 1 ,..., e m-1 , на ненулевой угол 2 p /m. Ясно, что при этом корень e 0 перейдет в корень e 1 , корень e 1 перейдет в корень e 2 , и т.д., а корень e m-1 перейдет в корень e 0 , т.е. сумма e 0 + e 1 +...+ e m-1 не изменится. Имеем e 1 a=a, откуда a=0.
Теорема 1. Пусть m>0 - целое число, a Î Z, x пробегает полную систему вычетов по модулю m. Тогда, если а кратно m, то
в противном случае, при а не кратном m,
.
Доказательство. При а кратном m имеем: a=md и
.
При а не делящемся на m, разделим числитель и знаменатель дроби a/m на d – наибольший общий делитель а и m, получим несократимую дробь a 1 /m 1 . Тогда, по лемме 1, a 1 x будет пробегать полную систему вычетов по модулю m. Имеем:
|
|
|
ибо сумма всех корней степени m 1 из единицы равна нулю.
¨
Напомню, что корень e k m -ой степени из единицы называется первообразным, если его индекс k взаимно прост с m. В этом случае, как доказывалось на первом курсе, последовательные степени e k 1 , e k 2 ,..., e k m-1 корня e k образуют всю совокупность корней m -ой степени из единицы или, другими словами, e k является порождающим элементом циклической группы всех корней m -ой степени из единицы.
Очевидно, что число различных первообразных корней m -ой степени из единицы равно j (m), где j – функция Эйлера, так как индексы у первообразных корней образуют приведенную систему вычетов по модулю m.
Теорема 2. Пусть m>0 – целое число, x пробегает приведенную систему вычетов по модулю m. Тогда (сумма первообразных корней степени m):
где m (m) – функция Мебиуса.
Доказательство. Пусть m=p 1 a 1 p 2 a 2 ...p k a k – каноническое разложение числа m; m 1 =p 1 a 1 , m 2 =p 2 a 2 , m 3 =p 3 a 3 ; x i пробегает приведенную систему вычетов по модулю m i . Имеем:
При a s =1 получается, что только корень e 0 =1 не является первообразным, поэтому сумма всех первообразных корней есть сумма всех корней минус единица:
стало быть, если m свободно от квадратов (т.е. не делится на r 2 , при r >1), то
Если же какой-нибудь показатель a s больше единицы (т.е. m делится на r 2 , при r>1), то сумма всех первообразных корней степени m s есть сумма всех корней степени m s минус сумма всех не первообразных корней, т.е. всех корней некоторой степени, меньшей m s . Именно, если m s =p s m s * , то:
¨
Вот теперь, дорогие читатели, когда я представил на ваше рассмотрение довольно весьма значительное количество сведений про полные и приведенные системы вычетов, никто не сможет обвинить меня в злонамеренном нарушении Закона Российской Федерации об Информации посредством ее утаивания, поэтому я заканчиваю этот пункт с удовлетворением.
Задачки 
| 1. Выпишите на листочке все наименьшие неотрицательные вычеты и все абсолютно наименьшие вычеты
а) по модулю 6,
б) по модулю 8.
Чуть ниже выпишите приведенные системы вычетов по этим модулям. Нарисуйте отдельно на комплексной плоскости корни шестой и корни восьмой степени из единицы, на обоих рисунках обведите кружочком первообразные корни и найдите в каждом случае их сумму.
2. Пусть e – первообразный корень степени 2n из единицы.
Найдите сумму: 1+ e + e 2 +...+ e n-1 .
3. Найдите сумму всех первообразных корней: а) 15-й; б) 24-й; в) 30-й степени из единицы.
4. Найдите сумму всевозможных произведений первообразных корней n -ой степени из единицы, взятых по два.
5. Найдите сумму k -х степеней всех корней n -ой степени из единицы.
6. Пусть m>1, (a, m)=1, b – целое число, х пробегает полную, а x – приведенную систему вычетов по модулю m. Докажите, что:
а) 
б) 
7. Докажите, что:
 ,
где р пробегает все простые делители числа а.
|
|
|
|
|
|
|
