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



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

Примеры.

  1. Доказать, что сравнение 2m+1(m+1)²(mod m) является верным.

Имеем: 2m+1-(m+1)²= 2m+1 - m²-2m-1=- m², а (- m²) делится на m => наше сравнение верно.

  1. Доказать, что следующее сравнения являются неверными:

  1. 25 (mod 10)

Если числа сравнимы по модулю m, то они имеют с ним один и тот же НОД.
Имеем: 4=2·2, 10=2·5, 25=5·5
НОД(4,10) = 2, НОД(25,10) = 5, следовательно наше сравнение неверно.

  1. (2n+1)·(2m+1) 2k (mod 6), где n, m, k – целые числа.

§2. Свойства сравнений



  1. Свойства сравнений, не зависящие от модуля.

Многие свойства сравнений аналогичны свойствам равенств.

  1. Отношение a b (mod m) является отношением эквивалент­ности, т. е. удовлетворяет требованиям:

а) рефлексивности: a a (mod m) (всякое целое число a срав­нимо с самим собой по модулю m);
в) симметричности: если a b (mod m), то и b a (mod m);
с) транзитивности: если a b (mod m), а b с (mod m), то aс (mod m).

  1. Сравнения no одному и тому же модулю можно почленно складывать, то есть если a b (mod m), c (mod m), то a+c b+d (mod m).

Доказательство._По_условию_m/(a-b)_и_m/_(c-d)._Следовательно,_m/(a-b)+(c-d),_m/(a+c)-(b+d)_=>_a+c_b+d_(mod_m).__Примеры.'>Доказательство.
По условию m/(a-b) и m/ (c-d). Следовательно, m/(a-b)+(c-d), m/(a+c)-(b+d) => a+c b+d (mod m).
Примеры.
Найти остаток при делении на 13.
Решение: -1 (mod 13) и 1 (mod 13), тогда (-1)+1 0 (mod 13), то есть остаток от деления на 13 равен 0.

  1. Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого, то есть если a b (mod m), c (mod m), то

a-c b-d (mod m).
Доказательство.
По условию m/(a-b) и m/(c-d). Следовательно, m/(a-b)-(c-d), m/(a-c)-(b-d) => (a-c) b-d (mod m).

  1. (следствие свойств 1, 2, 3). К обеим частям сравнения можно прибавлять одно и то же целое число.

Доказательство.
Пусть a b (mod m) и k –любое целое число. По свойству рефлексиности
k=k (mod m), а согласно свойствам 2 и 3 имеем a+k b+k (mod m).

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

a·c·d (mod m).
Доказательство.
По условию, a-b є mz, c-d є mz. Следовательно a·c-b·d = (a·c - b·c)+(b·c- b·d)=(a-b)·c+b·(c-d) є mz, то есть a·c·d (mod m).
Следствие. Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если а b (mod т) и s — целое неотрицательное число, то as bs (mod m).



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




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

    Басты бет