Теория остатков

Определение. Любое число из класса эквивалентности m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицатель

ными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет называется абсолютно наименьшим, если наименьший среди модулей вычетов данного класса.

Пример : Пусть 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 содержит ( m ) штук вычетов, где ( m )– функция Эйлера – число чисел, меньших m и взаимно простых с m . Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.

Пример. Пусть m = 42. Тогда приведенная система вычетов суть:

1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Лемма 2. 1) Любые ( m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .

2) Если ( a,m ) = 1 и x пробегает приведенную систему вычетов по модулю m , то аx так же пробегает приведенную систему вычетов по модулю m .

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

Лемма 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) Если 1 , 2 , ., k пробегают приведенные системы вычетов по модулям m 1 , m 2 , ., m k соответственно, то значения линейной формы M 1 1 +M 2 2 + .+M k 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 1 +M 2 2 + .+M k k принимает, очевидно, ( m 1 ) ( m 2 )  . ( m k ) = ( m 1 m 2  . m k )= ( m ) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m 1 m 2 .m k попарно несравнимы. Последнее легко доказывается рассуждениями, аналогичными рассуждениям, проведенным при доказательстве утверждения 1) этой леммы. Так как ( M 1 1 +M 2 2 + .+M k k ,m s )=(M s s ,m s )=1 для каждого 1 s k , то ( M 1 1 +M 2 2 + .+M k k ,m s )=1 , следовательно множество значений формы M 1 1 +M 2 2 + .+M k k образует приведенную систему вычетов по модулю m .



Лемма 4. Пусть x 1 , x 2 , ., x k ,x пробегают полные, а 1 , 2 , ., k , – пробегают приведенные системы вычетов по модулям 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} , а дроби { 1 /m 1 + 2 /m 2 + .+ k /m k } совпадают с дробями { /m} .

Доказательство. Доказательство обоих утверждений леммы 4 легко получается применением предыдущей леммы 3 после того, как вы приведете каждую сумму {x 1 /m 1 +x 2 /m 2 + .+x k /m k } и { 1 /m 1 + 2 /m 2 + .+ 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} ;

{ 1 /m 1 + 2 /m 2 + .+ k /m k }={(M 1 1 +M 2 2 + .+M k k )/m} ,

где M j =m 1 .m j-1 m j+1 .m k .

Если теперь принять во внимание, что дробные части чисел, получающихся при делении на модуль m любых двух чисел, сравнимых по модулю m , одинаковы (они равны r/m , где r – наименьший неотрицательный вычет из данного класса), то утверждения настоящей леммы становятся очевидными.

 Скачать реферат