Решение сравнений и их приложения.
Предварительный просмотр:
Подписи к слайдам:
Два целых числа a и b называют сравнимыми по модулю m , если m делит a - b . Если числа a и b сравнимы по модулю m , то пишут: a b ( mod m ).
Пример: m =3; 8 5( mod 3), так как 8-5=3 и 3 делится на 3
Теорема. (признак сравнимости дух чисел по модулю m ): Два целых числа a и b сравнимы по модулю m тогда и только тогда, когда a и b имеют одинаковые остатки при делении на m .
Примеры. Имеем - 5 23( mod 4), так как при делении с остатком на 4 числа -5 и 23 имеют одинаковые остатки - 5=4·(-2)+3 23=4·5+3 Числа 24 и 10 не сравнимы по модулю 3: 24 10( mod 3), поскольку при делении с остатком на 3 они дают разные остатки. 24=3·8+0 10=3·3+1
Два или несколько чисел, дающие при делении на m одинаковые остатки, называются равноостаточным или сравнимыми по модулю m .
Пример. Доказать, что сравнение 2 m +1 ( m +1)²( mod m ) является верным. Имеем: 2 m +1-( m +1)²= 2 m +1 - m ²-2 m -1=- m ², а (- m ²) делится на m => наше сравнение верно.
1. Отношение a b ( mod m ) является отношением эквивалентности, т. е. удовлетворяет требованиям : рефлексивности : a a ( mod m ); симметричности: если a b ( mod m ), то и b a ( mod m ); 2 . . Сравнения no одному и тому же модулю можно почленно складывать, то есть если a b ( mod m ), c d ( mod m ), то a + c b + d ( mod m ). транзитивности: если a b ( mod m ), а b с ( mod m ), то a с ( mod m ). Свойства сравнений не зависящие от модуля 5. Сравнения по одному и тому же модулю можно почленно перемножать, то есть если a b ( mod m ), c d ( mod m ), то a · c b · d ( mod m ). 3. . Два сравнения по одному и тому же модулю можно почленно вычитать одно из другого, то есть если a b ( mod m ), c d ( mod m ), то a - c b - d ( mod m ) . 6. Обе части сравнения можно умножать на одно и то же целое число . 4. (следствие свойств 1, 2, 3). К обеим частям сравнения можно прибавлять одно и то же целое число.
8 . Обе части сравнения и модуль можно умножить на одно и то же целое п оложительное число. 10. Обе части сравнения и модуль можно разделить на их общий делитель. 9. Обе части сравнения можно разделить на их общий множитель, если он взаимно простой с модулем. 7 . Если a b ( mod m ) и m n , то a b ( mod n ) Свойства сравнений , зависящие от модуля 11. Пусть Р ( х ) — многочлен с целыми коэффициентами, а и Ь — переменные, принимающие целые значения. Тогда если a b ( mod т ), то Р (а) Р ( b ) ( mod m ).
Полная система вычетов Системы вычетов Приведённая система вычетов.
-Полная система наименьших неотрицательных вычетов: 0, 1,…, т - 1 -Полная система наименьших положительных вычетов (из каждого класса берётся наименьший положительный вычет) : 1, 2, …, m . -Полная система абсолютно наименьших вычетов. В случае нечетного m абсолютно наименьшее вычеты представляются рядом . - ,…, -1, 0, 1 ,…, , а в случае четного m каким – либо из двух рядов + 1, …, -1, 0, 1,…, , , …, -1, 0, 1, …, .
www.themegallery.com Теорема 2 . Пусть (а, т) = 1, b — произвольное целое число; тогда если х 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 . Любая совокупность m целых чисел: x l , x 2 ,…, х m (1) попарно не сравнимых по модулю m , образует полную систему вычетов по модулю m . Пример .
Теорема 1 . Числа одного и того же класса вычетов по модулю m имеют с m один и тот же наибольший общий делитель: если a b ( mod m ), то ( а, m ) = ( b , m ). Определение 2 . Класс вычетов а по модулю т называется взаимно простым с модулем m , если наибольший общий делитель а и т равен 1 (то есть если т и любое число из а взаимно просты ). Определение 1. Наибольший общий делитель модуля т и любого числа а из данного класса вычетов по т называется наибольшим общим делителем т и этого класса вычетов. Определение 3 . Совокупность вычетов по модулю m , взятых по одному из каждого взаимно простого с т класса вычетов по этому модулю, называется приведенной системой вычетов.
Функция Эйлера. Вычисление функции Эйлера: 1) Если т = р — простое число, то φ ( р ) = р - 1. 2) Если т = р к — степень простого числа р , то φ ( p ) = ( р - 1) . Теорема 1. Функция Эйлера мультипликативна , то есть для взаимно простых чисел m и n имеем φ ( mn ) = φ ( m ) φ ( n ). Пример : φ (6)= φ (2) φ (3)=1·2=2
Теорема Эйлера . Если целое число a взаимно простое с m , то Теорема Ферма . Если целое число а не делится на простое число p , то Теорема Ферма часто формулируется иначе: Если p -простое и а -любое целое число, то
www.themegallery.com Пример 1 Найдем остаток от деления 243 132 на 34. Решение: 243 5 ( mod 34). Тогда 243 132 5 132 ( mod 34). Согласно теореме Эйлера 5 φ(34) 1 ( mod 34), или 5 16 1 ( mod 34). Далее делим 132 на 16: 132 = 16 • 8 + 4. Тогда 243 132 5 132 5 16·8+4 (5 16 )· 5 4 625 13 ( mod 34). Таким образом, 243 132 13 ( mod 34). Следовательно, г = 13.
Пример 2 Показать, что Решение: Воспользуемся малой теоремой Ферма: если ( а , p )=1, то . Числа 1,2,3,4,5,6 взаимно просты с числом 7. На основании указанной теоремы , ( 1) где а = 1,2,3,4,5,6. Сравнение (1) почленно возведём в куб, получим: ( 2) Складывая почленно сравнения вида (2) имеем при а = 1,2,3,4,5,6: .
Сравнения первой степени Любое сравнение первой степени с неизвестным x можно привести к виду: ax b(mod m), (1) где a 0(mod m ). Теорема 1 . Если (а, m ) = 1, то сравнение (1) имеет решение и притом единственное . Метод подбора Пример. Решить сравнение 7х 2( mod 13). Решение: Составим полную систему наименьших неотрицательных вычетов по модулю 13: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 . Имеем: х 4( mod 13). Следовательно, решением данного сравнения является класс вычетов по модулю 13.
Теорема 2. Если (а, m ) = 1, то решением сравнения ах b ( mod m ) является класс x ( mod m ). Способ Эйлера Пример Решить сравнение 5х 3 ( mod 6). Решение: Так как (5, 6) = 1, то сравнение имеет единственное решение: х 3 · 3 • 5 15 3 ( mod 6); так как φ (6) = φ (3) · φ (2) = =2 · 1 = 2. Ответ: х 3 ( mod 6).
Метод алгоритма Евклида Пример. Найти решение сравнения 3х 8( mod 13) используя алгоритм Евклида. Решение: 3х 8( mod 13) Данное сравнении можно представить в виде неопределённого уравнения: 3х-8=13у 3х-13у=8 Строим последовательность Евклида для чисел 13 и 3: 13=3·4+1 3=3·1+0 Тогда 1=13-3·4; домножим обе части равенства на 8: - 3·4·8+13·8=8 (-32)·8+13·8=8 Следовательно, х - 32( mod 13) или х 7( mod 13)
Метод цепных дробей Обращаясь к разысканию решений сравнения (1) укажем способ, основанный на теории цепных дробей, причём достаточно ограничиться лишь случаем ( a , m )=1. Пример. Найти решение сравнения 23х 17 (mod 71) . Решение: Воспользуемся методом цепных дробей. Здесь а=23, b =17, m =71 , то есть Составим таблицу: Воспользуемся формулой х . Имеем: х х х . Ответ: решением сравнения является класс по модулю 71. n 0 1 2 3 11 2 1 3 34 71
Сравнения высоких степеней. Теорема. Сравнение с неизвестными по простому модулю f ( x ) ( mod p) эквивалентно сравнению r(x) (mod p) , где r ( x ) есть полином, степень которого не превосходит p -1, являющийся остатком при делении с остатком f ( x ) на x p - x .
Пример Решить сравнение х 13 -х 11 +х 9 -х 7 +х 5 +х 3 +х+1 0 ( mod 7) . Разделим с остатком полином, стоящий в левой части, на х 7 -х. х 13 -х 11 +х 9 -х 7 +х 5 +х 3 +х+1 х 7 -х х 13 -х 7 х 6 -х 4 +х 2 -х 11 +х 7 +х 9 -х 11 +х 5 х 9 +х 7 -х 5 -х 7 х 9 -х 5 +х 5 х 9 +х 3 х 9 +х 3 2х 3 +х+1 Согласно предыдущей теореме получаем сравнение, эквивалентное исходному: 2х 3 +х+1 0 ( mod 7) . Проверяя теперь вычеты полной системы абсолютно наименьших вычетов 0,1,2,3,-3,-2,-1, находим решения данного сравнения: класс чисел х -3 ( mod 7) .
х 5 +10х 3 +х+60 ( mod 108) Д ля нахождения всех решений исходного сравнения по модулю 108 следует решить следующие системы: , , , , , , . Решая эти системы, находим все решения заданного сравнения: х х -6( mod 108), х 58( mod 108), х -14( mod 108), х 32( mod 108), -2( mod 108), х 34( mod 108), х -38( mod 108).
Спасибо за внимание