Решение сравнений и их приложения
жүктеу/скачать 131,78 Kb.
|
- Бұл бет үшін навигация:
- Теорема
- Доказательство.
| Доказательство.
Рассмотрим ах1 + b, ах2 + b,…, ахm + b (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) , так как х1 ,х2, ..., хm — полная система вычетов. Совокупность чисел (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. Числа одного и того же класса вычетов по модулю 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. Теорема доказана. жүктеу/скачать 131,78 Kb. Достарыңызбен бөлісу:
|