Свойства сравнений, подобные свойствам равенств

46. Два числа, сравнимые с третьим, сравнимы между собою.

Следует из 44.

 

47. Сравнения можно почленно складывать.

Действительно, пусть

a b (mod m), a b (mod m), …, a_k b_k (mod m), (1)

Тогда (из 45)

a = b + mt , a = b + mt , …, a_k b_k + mt_k, (2)

откуда

a + a + … + a_k b + b + … + b_k + m (t + t + … + t )

или (из 45)

a + a + … + a_k b + b + … + b_k + (mod m).

Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, переменив знак на обратный.

Действительно, складывая сравнение a + b c(mod m) с очевидным сравнением –b –b(mod m), получим а c – b(mod m).

К каждой части сравнения можно прибавить любое число, кратное модуля.

Действительно, складывая сравнение a b(mod m), с очевидным сравнением mk 0(mod m), получим a + mk b(mod m).

 

48. Сравнения можно почленно перемножать.

Действительно, рассмотрим снова сравнения (1) и вытекающие из них равенства (2). Перемножая почленно равенства (2), получим

a a … a = b b … b + mN,

где N – целое. Следовательно (45.1),

a a … a b b … b + (mod m),

Отсюда следует, что обе части сравнения можно возвести в одну и ту же степень.

Обе части сравнения можно умножить на одно и то же целое.

Действительно, перемножив сравнение a b(mod m) с очевидным сравнением

k k(mod m), получим ak bk(mod m)

 

49. Свойства 47 и 48 (сложение и умножение сравнений) обобщаются следующей теоремой.

Если в выражении многочлена с целыми коэффициентами

S = A , …, x … x заменим A , …, , x , …, x числами В , …, , y , …, y , сравнимыми с прежними по модулю m, то новое выражение S будет сравнимо с прежним по модулю m.

Действительно, из

A , …, В , …, (mod m),

x y (mod m), …, x y (mod m)

находим (с)

x y (mod m), …, x y (mod m),

A , …, x … x В , …, y … y (mod m),

откуда, суммируя, получим

A , …, x … x В , …, y … y (mod m).

Если

a b(mod m), a b (mod m), …, a b (mod m), x x (mod m),

то

ax + a x + … + a bx + b x + … + b (mod m).

Это утверждение есть частный случай предыдущего.

 

50.Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.

Действительно, из a b(mod m), a = a d, b = b d, (d, m) = 1 следует, что разность a – b, равная (a – b )d, делится на m. Поэтому (из 11) a – b делится на m, т.е. a b ( mod m).

Особые свойства сравнений

51. Обе части сравнения и модуль можно умножить на одно и то же целое.

Действительно, из a b(mod m) следует

а = b + mt, ak = bk + mkt

и, следовательно, ak bk(mod mk)

 

52. Обе части сравнения и модуль можно разделить на любой их общий делитель.

Действительно, пусть

a b(mod m), a = a d, b = b d, m = m d.

Имеем

a = b + mt, a d = b d + m dt, a = b + m t

и, следовательно, а₁ º b (mod m ).

 

53. Если сравнение а b имеет место по нескольким модулям, то оно имеет место и по модулю, равному общему наименьшему кратному этих модулей.

В самом деле, из a º b(mod m ), a b(mod m ), …,
a b(mod m )следует, что разность а – b делится на все модули m , m , …, m . Поэтому (из 29) она должна делиться и на общее наименьшее кратное т этих модулей, т.е. a b(mod m).

 

54. Если сравнение имеет место по модулю т, то оно имеет место и по модулю d, равному любому делителю числа т.

В самом дело, из a b(mod m) следует, что разность a – b должна делиться на m; поэтому (из 1) она должна делиться на любой делитель d числа т, т.е. a b(mod d).

 

55. Если одна часть сравнения и модуль делятся на какое-либо число, то и другая часть сравнения должна делиться на то же число.

Действительно, из a b(mod m) следует а = b + mt; если а и m кратны d, то (из теоремы 2) и b должно быть кратным d, что и утверждалось.

 

56. Если a b(mod m), то (a, m) = (b, m).

Действительно, ввиду теоремы 5 это равенство непосредственно следует из а = b + тt.

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

57. Числа равноостаточные, или, что то же самое, сравнимые по модулю т, образуют класс чисел по модулю т..

Из такого определения следует, что всем числам класса отвечает один итот же остаток r, и мы получим все числа класса, если в форме mq + r заставим q пробегать все целые числа.

Соответственно т различным значениям r имеем т классов чисел по модулю т.

 

58. Любое число класса называется вычетом по модулю т по отношению ко всем числам того же класса. Вычет, получаемый при q = 0, равный самому остатку r, называется наименьшим неотрицательным вычетом.

Вычет , самый малый по абсолютной величине, называется абсолютно наименьшим вычетом.

Очевидно при r < имеем = r, при r > – имеем
= r – m; наконец, если т чётное и r = , то за можно принять любое из двух чисел и – m = – .

Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю т. Чаще всего в качестве полной системы вычетов употребляют наименьшие неотрицательные вычеты 0, 1, ..., m – 1или также абсолютно наименьшие вычеты; последние, как это следует из вышеизложенного, в случае нечётного т представляются рядом

– , …, -1, 0, 1, …, ,

а в случае четного т каким-либо из двух рядов

– + 1, …, –1, 0, 1, …, ,

– , …, –1, 0, 1, …, – 1,

 

59. Любые т чисел, попарно несравнимые по модулю т, образуют полную систему вычетов по этому модулю.

Действительно, будучи несравнимы, эти числа тем самым принадлежат к различным классам, а так как их т, т.е. столько же, сколько и классов, то в каждый класс наверно попадёт по одному числу.

 

60. Если (a, m) = 1 и х пробегает полную систему вычетов по модулю т, то ах + b, где b – любое целое, тоже пробегает полную систему вычетов по модулю т.

Действительно, чисел ax + b будет столько же, сколько и чисел х, т.е. m. Согласно с остаётся, следовательно, только показать, что любые два числа ax + b и ax + b, отвечающие несравнимым x и x , будут сами несравнимы по модулю т.

Но допустив, что ax + b ax + b(mod m), мы придем к сравнению ax ax (mod m), откуда, вследствие(a, m)= 1, получим x x (mod m), что противоречит предположению о несравнимости чисел x и x .

 

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

61. Согласно свойству 56 числа одного и того же класса по модулю т имеют с модулем одни и тот же общий наибольший делитель. Особенно важны классы, для которых этот делитель равен единице, т.е. классы, содержащие числа, взаимно простые с модулем.

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

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

 

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

Действительно, будучи несравнимыми и взаимно простыми с модулем, эти числа тем самым принадлежат к различным классам, содержащим числа, взаимно простые с модулем, а так как их (m), т.е. столько же, сколько и классов указанного вида, то в каждый класс наверно попадёт по одному числу.

 

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

Действительно, чисел ах будет столько же, сколько и чисел х, т.е. (m). Согласно b остаётся, следовательно, только показать, что числа ах по модулю т несравнимы и взаимно просты с модулем. Но первое доказано в 60 для чисел более общего вида ах + b, второе же следует из (а, т) = 1, (х, m)= 1.

 

Теоремы Эйлера и Ферма

64. При т > 1 и (а, т) = 1 имеем (теорема Эйлера):

1(mod m).

Действительно, если х пробегает приведённую систему вычетов

x = r , r , …, r ; c = φ (m),

составленную из наименьших неотрицательных вычетов, то наименьшие отрицательные вычеты , , …, чисел ax будут пробегать ту же систему, но расположенную, вообще говоря, в ином порядке (согласно 63).

Перемножая почленно сравнения

ar (mod m), ar (mod m), …, ar (mod m),

получим

a r r …r … (mod m),

откуда, деля обе части на произведение r r …r = … , получим

a^с 1 (mod m).

65.Приp простом и а, не делящимся на p, имеем (теорема Ферма):

a 1(mod p). (1)

Эта теорема является следствием теоремы 64 при m = p. Последней теореме можно придать более удобную форму. Именно, умножая обе части сравнения (1) на а, получим сравнение

а а(mod p),

справедливое уже при всех целых а, так как оно верно и при а, кратном р.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. Активность избирателей; неравенство доходов; показатель качества демократии по Р. Далю
2. Гарантии равенства прав и свобод человека и гражданина.
3. Жироподобные вещества (липоиды)
4. Каковы же возможности достижения гендерного равенства?
5. Компромисс общества между эффективностью и равенством
6. На интернет-сайтах погоды можно встретить подобные таблицы. Внимательно изучи прогноз погоды на трое суток.
7. Нарушение равенства прав и свобод человека и гражданина.
8. НЕРАВЕНСТВО ДОХОДОВ В РЫНОЧНОЙ ЭКОНОМИКЕ. КРИВАЯ ЛОРЕНЦА. КОЭФФИЦИЕНТ ДЖИННИ
9. Неравенство Клаузиуса. Общая формулировка второго закона термодинамики
10. Подобные упражнения лучше всего делать в приемной у врача, на автобусной остановке или выстаивая какую-либо очередь, конечно, если есть спокойное место, куда можно отойти.
11. Преобразуем ограничения в неравенства
12. Принцип состязательности и равенства сторон в процессе