Решение сравнений и их приложения
жүктеу/скачать 131,78 Kb.
|
- Бұл бет үшін навигация:
- , или . Итак, для любого целого числа а имеем: Примеры. № 1
- Ответ
| Доказательство.
а) Если (а,p)=1, то согласно теореме Ферма После умножения обеих частей этого равенства на а, получим: б) Если (а,p) = 1 , то а делится на p. Но тогда и произведение а(-1) =а тоже делится на p , то есть а , или . Итак, для любого целого числа а имеем: Примеры. №1. Найдем остаток от деления 243132 на 34. Решение: 243 5 (mod 34). Тогда 243132 5132 (mod 34). Согласно теореме Эйлера 5φ(34) 1 (mod 34), или 5161 (mod 34). Далее делим 132 на 16: 132 = 16 • 8 + 4. Тогда 243132 5132 516·8+4(516)· 54625 Таким образом, 243132 13 (mod 34). Следовательно, г= 13. №2. Девятая степень однозначного числа n оканчивается цифрой 7; найти это однозначное число. Решение: так как девятая степень однозначного числа n оканчивается цифрой 7, то остаток от деления числа n9 на 10 должен быть равен 7, что равносильно справедливости сравнения n97(mod 10) Так как (7,10)=1, то (n,10)=1. Воспользуемся теоремой Эйлера, получим: n4 (mod 10), где φ(10)=4. Возведём обе части последнего сравнения в квадрат n8(mod 10). Тогда n9= n8·n1·n(mod 10) и следовательно, n(mod 10). Ответ: n=7 №3. Показать, что Решение: Воспользуемся малой теоремой Ферма: если (а,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: №4. Показать, что ( Решение: Каноническое разложение числа 105 = 3·5·7. Замечая, что (73,3)=(73,5)=(73,7)=1 и 73-простое число, применим малую теорему Ферма к числу 73 по модулям 3,5,7, получим сравнения: Путём возведения обеих частей сравнений в соответствующие степени, получим сравнения: Воспользуемся свойством: если некоторое сравнение имеет место по нескольким модулям, то оно справедливо по модулю, являющемуся наименьшим общим кратным данных модулей; следовательно, , откуда ( §1. Основные понятия, связанные с решением сравнений. Корни сравнений. Пусть т — целое число и f(х) = а0хп + а1хп-1 + ... + ап —многочлен с целыми коэффициентами a0 ,a1, …, ап .Если подставить вместо х целые числа, значения многочлена f(х) тоже будут целыми числами. жүктеу/скачать 131,78 Kb. Достарыңызбен бөлісу:
|