Решение сравнений и их приложения



бет7/14
Дата09.06.2022
өлшемі131,78 Kb.
#36581
түріРешение
1   2   3   4   5   6   7   8   9   10   ...   14
Байланысты:
reshenie sravnenii i ih prilozheniya 0

Доказательство.
Рассмотрим
ах1 + b, ах2 + b,…, ахm + b (2)

  1. Каждое из чисел совокупности (2) принадлежит некоторому классу.

  2. Любые два числа axi +b и axj + b из (2) несравнимы между собой, то есть принадлежат различным классам.

Действительно, если бы в (2) имелись такие два числа, что
axi +b axj + b (mod m), (i = j), то получили бы axi axj (mod т). Так как (а, т) = 1, то свойству сравнений можно сократить обе части сравнения на а. Получаем xi xj (mod m).

По условию же xi xj (mod т) при (i = j) , так как х12, ..., хm — полная система вычетов.

  1. Совокупность чисел (2) содержит т чисел, то есть столько, сколько имеется классов по модулю m.

Итак, ах1 + b, ах2 + b,…, ахm + b — полная система выче­тов по модулю m.
Пример.
Пусть т = 10, а = 3, b = 4.
Возьмем какую-нибудь полную систему вычетов по модулю 10, например: 0, 1, 2,…, 9. Составим числа вида ах + b. Получим: 4, 7, 10, 13, 16, 19, 22, 25, 28, 31. Полученная совокупность чи­сел — полная система вычетов по модулю 10.


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

Докажем следующую теорему.


Теорема 1.
Числа одного и того же класса вычетов по моду­лю m имеют с m один и тот же наибольший общий делитель: если ab (mod m), то (а, m) = (b, m).
Доказательство.
Пусть ab (mod m). Тогда а = b+mt, где t є z. Из этого равенства следует, что (а, т) = (b, т).
Действительно, пусть δ-общий делитель a и m, тогда a δ, m δ. Так как а = b+mt, то b=a-mt, следовательно b δ. Поэтому любой общий делитель чисел a и m является общим делителем m и b.
Обратно, если m δ и b δ, то а = b+mt делится на δ, a потому любой общий делитель m и b является общим делителем a и m. Теорема доказана.


Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   10   ...   14




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет