Как найти остаток от деления числа в степени на число

8

Теоремы Эйлера и Ферма. Нахождение остатков от деления степеней

В теории чисел большую роль играет числовая функция, называемая функцией Эйлера.

Определение 3.1. Функцией Эйлера называется функция, определенная на множестве натуральных чисел и равная числу натуральных чисел, не превосходящих и взаимно простых с ним.

Действительно числа взаимно простые с числом 10 это числа 1; 3; 7; 9 всего 4.

2. . Действительно, так как число 7 — простое, взаимно простыми с ним являются все натуральные числа меньшие 7: 1; 2; 3; 4;5; 6, всего их 7.

Важным свойством функции Эйлера является её мультипликативность в случае, когда и числа взаимно простые т.е.

Способ вычисления функции Эйлера основан на следующих теоремах:

Теорема 3.2. Пусть простое число, — любое натуральное число, тогда

Теорема 3.3. Если

— каноническое разложение натурального числа на простые множители, то

Особую роль в теории сравнений играют теоремы Эйлера и Ферма.

Теорема 3.4. (Эйлера) Для любого модуля и любого взаимно простого с справедливо сравнение:

Теорема 3.5. (Ферма) Если число не делится на простое число , то

Следствие 3.6. При любом целом положительном

Теоремы Ферма — Эйлера позволяют часто находить остатки от деления на модуль больших степеней заданного числа. Действительно, если нам надо найти остаток от деления на , где

то можно представить в виде

где может быть значительно меньше, чем .

Задача 4. Найти функцию Эйлера от числа 875.

Решение. 1. Разложим данное число на простые множители

2. По теореме 3.3

Задача 5. Доказать, что если

2. Число 7 — простое, поэтому по теореме Ферма

Возведем обе части этого сравнения в квадрат (свойство сравнений 8) и получим верное сравнение:

откуда в соответствии с п.1. следует что

Найти остаток от деления на 52.

Решение. 1. Обозначим искомый остаток через

найдем такое число.

2. Вычислим функцию Эйлера от 52:

Поделим 2147 на 24 с остатком:

таким образом, остаток от деления на 52 равен 7.

Контрольная работа №2 для учащихся 9 классов

Приведенные ниже задания являются контрольной работой №2 для учащихся 9 классов. Каждая задача оценивается в 5 баллов, для зачета нужно набрать не менее 15 баллов.

Правила оформления работ:

Решения по каждому предмету оформляется отдельно. Каждое задание имеет свой шифр (М9.2.1 и т.д.), который указывается перед записью решения. Переписывать текст задачи не надо, достаточно краткой записи, если это необходимо. Оформлять решения в порядке следования заданий. Можно присылать нам столько решений, сколько удалось вам сделать, даже если оказалось невозможным выполнить всю работу.

М 9.2.1. Доказать, что если

М 9.2.2. Показать, что числа 32; -9; 15; 42; -18; 30; 6 составляют полную систему вычетов по модулю .

М 9.2.3. Показать, что числа 19; 23; 25; -19 составляют приведенную систему вычетов по модулю .

М 9.2.4. Найти функцию Эйлера от числа 1000.

М 9.2.5. Найти остатки от деления

• А) на 7;
• Б) на 13;
• В) на 31.

М 9.2.6. Найти две последние цифры следующих чисел 1) ; 2) .

Применение движений плоскости к решению задач элементарной геометрии

Актуальность темы «Преобразования плоскости» очевидна, так как одной из важнейших идей, лежащих в построении курса геометрии, является идея геометрических преобразований, которую обосновал выдающийся немецкий математик Ф. Клейн (1872г.). Групповая точка зрения на геометрию оказала положительное влияние на развитие геометрии, как науки и её приложения. Групповая точка зрения на геометрические свойства фигур широко используется в физике, химии, биологии, технике. Это сближает математику с данными областями наук. Методы геометрических преобразований позволяют решать большой класс задач элементарной геометрии: задачи на доказательство, построение, вычисление, нахождение геометрических мест точек.

В данной статье мы рассмотрим применение движений — частного случая преобразований плоскости — при решении задач на доказательство. Однако, овладеть этим методом нелегко, поскольку трудно указать какие-либо общие способы использования движений и в большинстве случаев это зависит от конкретной задачи. Суть этого метода состоит в том, что заданную фигуру или её части подвергают некоторому движению или наряду с заданной фигурой рассматривают её образ или образы её частей при этом движении.

В выработке навыков решения помогут рассматриваемые в этой статье образцы решения задач с применением движений.

Как обычно, в конце статьи приводятся задачи для самостоятельного решения, которые составляют контрольную работу по математике для слушателей ХКЗФМШ, обучающихся в 10 классе.

1. Некоторые определения и свойства движений

Определение 1. Взаимно однозначное отображение f плоскости Р на себя называется преобразованием f плоскости Р.

Определение 2. Движением плоскости Р называется такое преобразование f плоскости Р, при котором сохраняется расстояние между двумя любыми точками этой плоскости, т. е.

где А= f(А), В=f(В) — образы, соответственно, точек А и В в движении f.

Движения бывают первого и второго рода, при этом движения первого рода не меняют ориентацию фигур, а движения второго рода — меняют её на противоположную.

Определение 3. Движение h плоскости Р называется произведением (композицией) каких-либо движений f и g этой же плоскости, если оно заключается в последовательном выполнении преобразования f, а затем преобразования g (обозначается: ).

Определение 4. Преобразование плоскости называется тождественным, если оно любую точку плоскости переводит в себя, т. е.

Тождественное преобразование обозначается е и удовлетворяет условию:

где f — любое преобразование плоскости Р, в том числе и движение.

Частными видами движений являются осевая симметрия, центральная симметрия, параллельный перенос, вращение (поворот), скользящая симметрия и тождественное преобразование плоскости.

Определение 5. Симметрией относительно прямой (оси симметрии) называется движение плоскости, которое:

каждую точку прямой преобразует в себя;

каждую точку А преобразует в точку А такую, что (АА) и середина отрезка АА лежит на . Обозначается осевая симметрия: (рис.1).

Определение 6. Параллельным переносом на вектор называется движение плоскости, которое всякую точку АР преобразует в точку АР такую, что выполняется условие:

Обозначается параллельный перенос:

Определение 7. Вращением (или поворотом) вокруг точки О на угол называется такое преобразование плоскости, при котором:

Произвольная точка АО переходит в точку А такую, что:

• а) ОА=ОА;
• б) АОА = (рис. 3)

Здесь и далее =АОА означает величину заданного ориентированного угла АОА. Обозначается: .

Определение 8. Симметрией относительно точки О (центр симметрии) называется движение плоскости, которое всякую точку АО преобразует в такую точку А, что точка О является серединой отрезка АА, а точку О преобразует в себя. Обозначается: Z0 (рис. 4)

Заметим, что центральная симметрия Z0 есть поворот Ro на угол 180.

Определение 9. Скользящей симметрией называется произведение осевой симметрии с осью и параллельного переноса на вектор , который параллелен оси : т.е. если l|| , то — скользящая симметрия.

Теорема. Всякое движение I рода есть либо тождественное преобразование, либо параллельный перенос, либо поворот плоскости. Всякое движение II рода есть либо осевая симметрия, либо скользящая симметрия.

Определение 10. Точка называется инвариантной (или неподвижной) точкой преобразования f , если при преобразовании f она отображается на себя.

Прямая называется инвариантной прямой преобразования f, если она отображается на себя.

Если при этом каждая точка прямой остается неподвижной, то прямая называется осью преобразования.

Движения обладают следующими свойствами:

• 1 движение отображает отрезок на отрезок;
• 2 движение отображает точки, лежащие на одной прямой, в точки, лежащие на одной прямой;
• 3 движение отображает прямую на прямую, полуплоскость на полуплоскость;
• 4 движение сохраняет параллельность прямых;
• 5 движение отображает луч на луч;
• 6 движение сохраняет величину угла;
• 7 движение отображает многоугольник на многоугольник со сторонами и углами соответственно той же величины, что и у данного многоугольника;
• 8 движение отображает окружность на окружность того же радиуса;

Справедлива так же следующая теорема: если АВС и АВС — два треугольника и если АВ=АВ, АС=АС, ВС=ВС, то существует единственное движение плоскости, отображающие точки А, В, С соответственно на точки А, В, С.

Определение 11. Фигура Ф называется равной фигуре Ф (Ф=Ф), если существует движение, при котором фигура Ф преобразуется в фигуру Ф.

2. Примеры решения задач

Задача 1. Обозначим через М — точку пересечения диагоналей равнобедренной трапеции с основаниями АВ и СD а через P и Q — центры окружностей, описанных вокруг треугольников ADM и BCM. Докажите, что:

c) прямая, соединяющая точку М с точками пересечения прямых BP и AQ, делит основания пополам.

Решение. Пусть ось симметрии трапеции — , а P и Q — центры описанных окружностей, соответственно, вокруг треугольников AMD и BCM (рис. 5).

Тогда образом треугольника ADM при осевой симметрии относительно оси будет треугольник ВСМ, т.е.

Следовательно, образом окружности, описанной вокруг треугольника AMD, при симметрии относительно будет окружность, описанная вокруг треугольника ВСМ. Следовательно,

Отсюда PQ||AB, BP=AQ. Пусть

тогда N , так как

Три равные окружности попарно пересекаются и имеют только одну общую точку D. Доказать, что окружность, проходящая через вторые точки пересечения данных окружностей, равна данным трем окружностям.

Решение. Выполним чертеж, обозначив вторые точки пересечения данных окружностей через А, В, С (рис. 6).

Рассмотрим прямую АD и через точку А проведем прямую, ей перпендикулярную, обозначив точки пересечения этой прямой с окружностями S (O1, R) и S (O2, R) через E и F соответственно. Так как (O1, R) и S (O2, R) симметричны относительно прямой AD, то S(AD)(E)=F, т. е. AD есть серединный перпендикуляр к отрезку EF. Через точку С проведем прямую перпендикулярную CD. Пусть эта прямая пересекает прямую

EF в точке Q, а окружность S(O3, R) — в точке Р.

то точка Q лежит на окружности S (O2, R) и, значит, совпадает с точкой F. Аналогично доказанному выше получаем, что перпендикуляр к прямой BD из точки В проходит через точки Е и Р, причем BD является серединным перпендикуляром к отрезку РЕ. Из того, что отрезки АС, ВА и ВС являются средними линиями , очевидно вытекает равенство и , а значит, окружность S (O1, R) равна окружности, проходящей через точки А, В, С, как окружности, описанные около равных треугольников. Что и требовалось доказать.

Доказать, что если отрезок KF, соединяющий середины двух противоположных сторон четырехугольника ABCD (K — середина стороны AB, F — середина стороны DC), равен полусумме сторон BC и AD, то четырехугольник есть трапеция (рис.7).

Решение. Выполним параллельный перенос на вектор . Пусть

Следовательно, линия BFE есть прямая. Тогда KF — средняя линия треугольника ABE:

Но по условию 2

Отсюда следует, что

AE=AD+DE, т. е. DAE. Но DE||BC, тогда и AD||BC.

На сторонах AB и CD параллелограмма ABCD построены квадраты: первый — вне параллелограмма, а второй — по ту же сторону от CD, что и сам параллелограмм. Доказать, что расстояние между центрами квадратов равно ВС.

Обозначим центры построенных квадратов

соответственно, через О1 и О2 (Рис. 8). Докажем, что . Выполним параллельный перенос на вектор .

равны между собой и при параллельном переносе переходят друг в друга, тогда и их центры и также перейдут друг в друга.

и из определения следует, что

Задача 5. Дан произвольный треугольник ABC, на сторонах которого построены квадраты. Доказать, что отрезок, соединяющий центры двух квадратов, построенных на сторонах АВ и ВС, равен и перпендикулярен отрезку, соединяющему точку В с центром третьего квадрата.

Решение. Выполним чертеж (рис.9) и рассмотрим поворот вокруг точки А на угол, равный . Из условия задачи очевидно, что

а образом точки Р будет некоторая точка F. При этом имеем, что

Из равенства треугольников АСР и ARF вытекает

но тогда будут равны и углы АСВ и QRF. Рассматривая центральную симметрию , легко убедиться, что

так как эта симметрия точку С переводит в R, луч СВ — в луч RF и

является серединой BF, с учетом соотношений

сразу получаем равенство и перпендикулярность отрезков и . Утверждение задачи доказано.

Задача 6. Дан равносторонний треугольник АВС и произвольная точка М. Доказать, что больший из трех отрезков MA, МВ и МС не больше суммы двух других отрезков. В каком случае больший из отрезков MA, МВ и МС будет равен сумме двух других?

Решение. Пусть ВМ — наибольший из указанных отрезков (рис.10). Выполним поворот плоскости вокруг точки В на 600.

Треугольник — равносторонний. Поэтому

Равенство будет в том и только в том случае, если точка М лежит на окружности, описанной вокруг треугольника АВС.

На сторонах параллелограмма ABCD вне его построены правильные треугольники ABQ, BCN, CDP и DAM. Доказать, что отрезки PQ и MN имеют общую середину.

Выполним чертеж (рис.11) и рассмотрим центральную симметрию с центром в точке О — точке пересечения диагоналей параллелограмма. Очевидно, что

А это означает, что О является общей серединой отрезков PQ и MN, что и утверждалось в условии задачи.

Остаток от деления числа в большой степени

Как можно быстро вычислить (x^n)mod y. Уже когда-то копал этот вопрос и обнаружил теорему Эйлера (теория чисел).
Не относится к вопросу: Но вся проблема в том, что я учусь в школе, и мы не проходили еще подобных выражений, найденных мною на wiki, и теории чисел. Объясните пожалуйста:

• Как использовать эту теорему на практике(например, реализация на C).
• (Не так важно, но просто интересно)Кратко значение формулировки на
  wiki. Буду рад какой-нибудь статье, etc для тех, кто еще не знаком с теорией чисел и математикой >9 классов.

Наприклад ми хочемо обчислити 7 222 (mod 10). Маємо, що 7 і 10 є взаємно простими і φ(10) = 4 . Одже згідно з теоремою Ейлера 7 4 ≡ 1 (mod 10) і як наслідок

7 222 ≡ 7 4×55 + 2 ≡ (7 4 ) 55 x 7 2 ≡ 1 55 x 7 2 ≡ 49 ≡ 9 (mod 10).

Моя попытка перевода:

Например мы хотим вычислить "7 222 (mod 10)". 7 и 10 являются взаимно-простыми и φ(10) = 4 (это число натуральных чисел не больших чем 10 и являющихся взаимнопростыми по отношению к 10 . Это следующие числа: 1,3,7,9 и всего их 4 ).

Следовательно согласно теореме Эйлера 7 4 ≡ 1 (mod 10) и как следствие:

7 222 ≡ 7 4×55 + 2 ≡ (7 4 ) 55 x 7 2 ≡ 1 55 x 7 2 ≡ 49 ≡ 9 (mod 10).

Следствия из теоремы:

если a φ(n) ≡ 1 (mod n), то и (a φ(n) ) k ≡ 1 (mod n) для любого положительного k , т.к.

(a φ(n) ) k ≡ a φ(n) mod n * (a φ(n) ) k — 1 mod n ≡ (a φ(n) ) k — 1 (mod n) и т.д.

теория-чисел — Как найти остаток от деления числа в степени?

Найдите остаток от деления числа: 34^611(mod 611). Нужно подробное решение. Заранее большое спасибо!

задан 18 Апр ’20 15:05

Нужно подробное решение. — наверняка есть в учебниках.

1 ответ

Я думаю, что «в виде исключения» здесь можно изложить полное решение. Сам пример составлен достаточно удачно, и на его основе можно пронаблюдать разные «тонкости», касающиеся того, какие методы можно применять. Способы хотя и стандартны, но некоторыми из них пример решается легче, а некоторыми сложнее. К тому же, примеры этого типа часто звучат на форуме, и написанное потом можно будет давать в качестве ссылки.

Но, тем не менее, даже для понимания решения нужно владеть следующим «теорминимумом»: линейные сравнения и их системы; китайская теорема об остатках; малая теорема Ферма; функция Эйлера; теорема Эйлера. Всё это можно прочитать, например, в учебнике Бухштаба.

Прежде всего, нужно разложить на простые множители число $%611$%. Если бы оно было простым, ответ мгновенно получался бы из малой теоремы Ферма: $%x^p\equiv x\pmod

$%. Но здесь число составное: деля его последовательно на простые, видим, что оно делится на $%13$% и равно $%pq=13\cdot47=611$%.

Понятно, что число $%a=34$% не делится ни на $%p$%, ни на $%q$%, поэтому оно взаимно просто с $%n=pq$%, и можно применить теорему Эйлера: $%a^<\varphi(n)>\equiv1\pmod$%. Здесь $%\varphi(n)=\varphi(pq)=(p-1)(q-1)$%; показатель степени приводим по модулю $%\varphi(n)$%, получая $%pq-(p-1)(q-1)=p+q-1=59$%. При этом задача сводится к нахождению остатка от деления $%34^<59>$% на $%611$%. В таком виде можно было бы посчитать остаток при помощи «быстрого возведения в степень», последовательно возводя числа в квадрат и беря остатки от деления. Далее через двоичное разложение $%59$% мы получили бы ответ, но это требовало бы длинных вычислений. Тем не менее, сам этот метод иногда применим, и его полезно иметь в виду. Здесь же проще найти остатки от деления числа на $%13$% и $%47$% по отдельности, а потом применить китайскую теорему об остатках.

Итак, по модулю $%p=13$% мы заменяем $%34$% на $%-5$%, а показатель степени $%pq$% приводим по модулю $%p-1=12$%, получая $%q=47$%, что сравнимо с $%-1$%. Это удобно, так как вместо возведения в степень нужно найти элемент, обратный $%-5$% по модулю $%13$%. Это делается устно за счёт того, что $%5\cdot5\equiv25\equiv-1\pmod<13>$%, то есть число $%x=34^<611>$% из условия при делении на $%13$% даёт в остатке $%5$%. Более подробно повторим то, что было выше: $%x\equiv(-5)^<611>\equiv(-5)^<12q-1>\equiv(-5)^<-1>\equiv5\pmod<13>$%.

Теперь рассуждаем по модулю $%q=47$%. Здесь основание степени приводим по модулю $%47$%, заменяя на $%-13$%, а показатель приводим по модулю $%q-1=46$%, заменяя на $%13$%. Получается $%x\equiv(-13)^<13>\pmod<47>$%, и здесь уже применяем быстрое возведение в степень:

Итак, оба остатка найдены, и остаётся решить систему из двух сравнений:

Это делается стандартно: из второго уравнения получаем $%x=47y+24$%, где $%y$% целое, и подставляем в первое. После упрощений получается $%-5y-2\equiv5\pmod<13>$%, то есть $%-5y\equiv7\pmod<13>$%. Домножая обе части на $%5$%, имеем $%y\equiv35\equiv-4\pmod<13>$%, то есть $%y=13k-4$%, где $%k$% целое. Отсюда $%x=47(13k-4)+24=611k-164$%. Остаток от деления на $%611$% равен $%611-164=447$%, и это ответ.

§ 10. Теоремы Эйлера и Ферма

Теорема (Эйлера). Для любого целого числа a, взаимно простого с натуральным модулем m, выполнено сравнение (mod m) .

Доказательство. 1. Сведём задачу к числам 0  a < m. Для этого разделим a с остатком на m : a = mq + r (0  r < m). При этом по свойству наибольшего общего делителя имеем

НОД(r, m) = НОД(a – mq, m) = НОД(a, m) = 1,

т.е. r удовлетворяет условию теоремы. Если уже доказано, что r  ( m )  1 (mod m), то ввиду a  r (mod m) получим a  ( m )  r  ( m )  1 (mod m).

Таким образом, можно предполагать, что 0  a < m.

2. Пусть M = <0, 1, 2, … , m – 1> и a₁ , … , a_k – все взаимно простые элементы множества M, из которых образуем множество M₁ . По определению функции Эйлера k = (m), а по условию теоремы имеем a  M₁ .

3. Рассмотрим элементы b₁ = aa₁ , … , b_k = aa_k . По свойствам взаимно простых чисел все эти элементы взаимно просты с m. Пусть r₁ , … , r_k – остатки от деления чисел b₁ , … , b_k на m : b_i = mq_i + r_i (0  r_i < m, 1  i  k). Тогда r_i  M (1  i  k), и кроме того,

НОД(r_i , m) = НОД(b_i – mq_i , m) = НОД(b_i , m) = 1,

так что r_i  M₁ (1  i  k).

4. Докажем, что среди чисел r₁ , … , r_k нет одинаковых. Действительно, если r_i = r_j , то b_i = mq_i + r_i , b_j = mq_j + r_i (0  r_i < m). Тогда b_i  r_i  b_j (mod m), т.е. aa_i  aa_j , a(a_i – a_j)  0 (mod m) и ввиду НОД(a, m) = 1 по свойствам сравнений верно a_i – a_j  0, a_i  a_j (mod m), что значит a_i = a_j , что возможно только при i = j.

5. Итак, все числа r₁ , … , r_k различны, их число k = (m) и все они принадлежат k—элементному множеству M₁ = <a₁ , … , a_k>. Это значит, что r₁ , … , r_k – это те же числа a₁ , … , a_k , возможно, в другом порядке. Поэтому

a₁ … a_k = r₁ … r_k  b₁ … b_k = (aa₁) … (aa_k) = a k a₁ … a_k (mod m).

Значит, a₁ … a_k  a k a₁ … a_k (mod m), (a  (m) – 1)a₁ … a_k (mod m). Учитывая, что a₁ … a_k взаимно просто с m (т.к. все a_i взаимно просты с m), получим по свойствам сравнений a  ( m ) – 1  0 (mod m).

Теорема Эйлера доказана.

Упражнение. Пусть m = – каноническое разложение натурального числа m, . Тогда для любого целого числа a выполнено сравнение a  (a  ( m ) – 1))  0 (mod m).

Теорема (малая теорема Ферма). Для любого простого числа p и целого числа a , не делящегося на p, имеет место сравнение a p–1  1 (mod p).

Доказательство следует из теоремы Эйлера при m = p с учётом равенства (p) = р – 1.

Следствие. Для любого простого числа p и целого a верно сравнение a p  a (mod p).

Доказательство следует из теоремы Ферма: a p – a  a(a p–1 – 1)  0 (mod p) как для a, делящегося на p, так и для взаимно простого с p.

Упражнения: 1. Докажите, что для любого целого a выполняется сравнение a 561  a (mod 561), но число 561 – не простое. Таким образом, обращение теоремы Ферма не верно.

2. Докажите, что 561 – наименьший контрпример к обращению теоремы Ферма.

Теоремы Эйлера и Ферма можно использовать для нахождения остатков некоторых арифметических выражений, значения которых трудно вычислить.

I. Остатки полиномиальных выражений. Пусть требуется найти остаток от деления на заданное число m некоторого выражения P(a₁ , … , a_n), полученного из целых чисел а₁ , … , а_n с помощью операций сложения, вычитания и умножения.

Для решения этой задачи достаточно, исходя из значений а_i (mod m), найти значение P(a₁ , … , a_n) по модулю m.

Примеры: 1. Найти остаток от деления 123349 – 88560 + 893 2 на 4.

Вычислим значения всех участвующих в данном равенстве чисел по модулю 4: 123  –1 (mod 4), 349  1 (mod 4), 88  0 (mod 4), 893  1 (mod 4). Поэтому по свойствам сравнений имеем

123349 – 88560 + 893 2  (–1)1–0560+1 2 = 0 (mod 4).

Значит, исходное выражение делится на 4, т.е. искомый остаток равен 0.

2. Найти остаток от деления на 6 выражения

–3356299 – 333 8 5551 – 325(–287 + 679825).

Имеем 3356  2 (mod 6), 299  –1 (mod 6), 333  3 (mod 6), 5551  1 (mod 6), 325  1 (mod 6), 287  –1 (mod 6), 679  1 (mod 6), 825  3 (mod 6). Поэтому получаем

–3356299–333 8 5551–325(–287+679825)  –2(–1)–(3 2 ) 4 1–1(–(–1)+13) 

 2–(3 2 ) 2 –(–2)  2–3 2 + 2  –5  1 (mod 6),

т.е. искомый остаток равен 1.

II. Остатки экспоненциальных выражений. Пусть требуется найти остаток от деления на число m некоторого выражения P(a₁ , … , a_n), полученного из целых чисел а₁ , … , а_n с помощью операций сложения, вычитания, умножения и возведения в большие степени.

Как и ранее, для решения этой задачи достаточно, исходя из значений а_i (mod m), вычислить P(a₁ , … , a_n) (mod m). При вычислении степенных выражений с большими показателями степеней удобно пользоваться теоремами Эйлера и Ферма.

Примеры: 1. Найти остаток от деления числа 3 546 – 88 на 5.

Так как НОД(3, 5) = 1, то по теореме Эйлера, 3  (5)  1 (mod 5) или 3 4  1 (mod 5), поскольку (5) = 4. Значит, 3 546 = (3 4 ) 136 3 2  1 136 3 2   9  4 (mod 5), и 3 546 – 88  4 – 3  1 (mod 5), так что искомый остаток равен 1.

2. Найти последнюю цифру числа 7 954 .

Заметим, что для заданного числа a = в десятичной системе счисления, выполняется сравнение (mod 10 s ):

.

Таким образом, для нахождения s последних цифр числа a достаточно найти остаток от деления его на 10 s . В данном примере нужно искать остаток от деления числа 7 954 на 10.

Поскольку НОД(7, 10) = 1, то можно воспользоваться теоремой Эйлера: 7  (10)  1 (mod 10). Вычисляем (10) = (25) = (2)(5) = 14 = 4 и получаем: 7 4  1 (mod 10).

Поэтому 7 954 = (7 4 ) 238 7 2  1 238 7 2 = 49  9. Итак, последняя цифра числа 7 954 равна 9.

3. Найти две последние цифры числа 8 345 .

Здесь нужно искать остаток от деления числа 8 345 на 100 = 10 2 .

Поскольку НОД(8 345 , 100) = НОД(2 3  345 , 2 2 5 2 ) = 2 2 = 4  1, непосредственно воспользоваться теоремой Эйлера нельзя. Если 8 345 = 4y , то 8 345   4y (mod 100)  428 344  4y (mod 100)  28 344  y (mod 25), причём 8 уже взаимно просто с 25, и можно использовать теорему Эйлера: 8  (25)  1 (mod 25). Поскольку (25) = (5 2 ) = 5 2 – 5 1 = 20, то

8 344  (8 20 ) 17 8 4  1 17 (8 2 ) 2  14 2 = 196  –4 (mod 25).

Таким образом, y  28 344  2(–4) = –8  17 (mod 25), и 8 345 = 4y   417 = 68 (mod 100). Итак, число 8 345 оканчивается на 68.

4. Найти две последние цифры числа 6 34 – 3 58 .

Действуем аналогично предыдущему: поскольку НОД(6 34 , 100) = 4, имеем 6 34 = 4x, 6 34  4x (mod 100)  3 2 6 32  x (mod 25) и 6 20  1 (mod 25), так что x  3 2 6 32  3 2 6 12  936 6  911 6  9121 3  9(–4) 3   –964  –914 = –126  –1 (mod 25) и 6 34  4(–1) = –4  21 (mod 100).

Значительно проще найти остаток от второго слагаемого: 3  (100)  1 (mod 100), т.е. 3 40  1 и 3 58  3 18 = 81 4 3 2  19 4 3 2  61 2 3 2 = 183 2   (–17) 2 = 289  89 (mod 100). Таким образом, 6 34 – 3 58  21 – 89 = – 68   32 (mod 100), т.е. исходное число оканчивается на 32.