Ученики на Учителя.com


Презентация "Теорема Эйлера, малая теорема Ферма; теорема Вильсона"

Скачать материал
Подписи к слайдам:
Теорема Эйлера, малая теорема Ферма; теорема Вильсона
  • Выполнила: Апухтина Валерия
  • Руководитель Чистова Ирина Анатольевна
  • Учитель математики
  • МБОУ-гимназия№ 13
  • п. Краснообск
  • Цель:
  • Познакомиться с теоремами Эйлера, Ферма и теоремой Вильсона.
  • 2. Рассмотреть примеры решений задач с помощью данных теорем
  • Содержание:
  • 1.Теорема Эйлера
  • 2.Доказательство теоремы Эйлера
  • 3.Примеры решения задач по теореме Эйлера
  • 4.Малая теорема Ферма
  • 5.Примеры решения задач по теореме Ферма
  • 6.Теорема Вильсона
  • 7.Следствие
  • 8.Доказательство
  • 9.Примеры решения задач по теореме Вильсона
  • 10.Литература
Теорема Эйлера
  • Теоре́ма Э́йлера в теории чисел гласит, что
  • Если a и m взаимно просты, то , где — функция Эйлера Частным случаем теоремы Эйлера при простом m является малая теорема Ферма. В свою очередь, теорема Эйлера является следствием теоремы Лагранжа.
  • Доказательство
  • Пусть   — все различные натуральные числа, меньшие m и взаимно простые с ним.
  • Рассмотрим всевозможные произведения xia для всех i от 1 до .
Доказательство теоремы Эйлера
  • Поскольку a взаимно просто с m и xi взаимно просто с m, то и xia также взаимно просто с m, то есть
  • для некоторого j.
  • Отметим, что все остатки xia при делении на m различны. Действительно, пусть это не так, то есть существуют такие
  • , что
  • или
  • Так как a взаимно просто с m, то последнее равенство равносильно тому, что или
  • Это противоречит тому, что числа
  • попарно различны по
  • модулю m.
Доказательство теоремы Эйлера
  • Перемножим все равенства
  • Получим:
  • или
  • Так как число
  • взаимно просто с m, то последнее равенство
  • равносильно тому, что
  • или
Примеры решения задач по теореме Эйлера
  • 1. Девятая степень однозначного числа оканчивается на 7. Найти это число.
  • Решение. a 9 º 7(mod 10) – это дано. Кроме того, очевидно, что (7, 10)=1 и ( a , 10)=1. По теореме Эйлера, a j (10) º 1(mod 10). Следовательно, a 4 º 1(mod 10) и, после возведения в квадрат, a 8 º 1(mod 10). Поделим почленно a 9 º 7(mod 10) на a 8 º 1(mod 10) и получим a º 7(mod 10). Это означает, что a=7.
  • 2. Найти две последние цифры числа 243 402 .
  • Решение. Две последние цифры этого числа суть остаток от деления его на 100. Имеем: 243=200+43; 200+43 º 43(mod 100) и, возведя последнее очевидное сравнение в 402-ую степень, раскроем его левую часть по биному Ньютона (мысленно, конечно). В этом гигантском выражении все слагаемые, кроме последнего, содержат степень числа 200, т.е. делятся на 100, поэтому их можно выкинуть из сравнения, после чего понятно, почему 243 402 º 43 402 (mod 100). Далее, 43 и 100 взаимно просты, значит, по теореме Эйлера, 43 j (100) º 1(mod 100). Считаем:
  • j (100)= j (2 2 × 5 2 )=(10–5)(10–2)=40.
Примеры решения задач по теореме Эйлера
  • Имеем сравнение: 43 40 º 1(mod 100), которое немедленно возведем в десятую степень и умножим почленно на очевидное сравнение, проверенное на калькуляторе: 43 2 º 49(mod 100). Получим:
  • , следовательно, две последние цифры числа 243^ 402 суть 4 и 9 .
Малая теорема Ферма
  • Ма́лая теоре́ма Ферма́ — классическая теорема теории чисел, которая утверждает что
  • Если p — простое число и целое a не делится на p, то a p − 1 ≡ 1 (mod p)  (или a p − 1 − 1 делится на p).Иная формулировка:
  • Для любого простого p и целого a, (a p − a) делится на p.
  • Примеры решений по теореме Ферма:
  • 1. Какие числа являются элементами в Z14*?
  • Решение
  • Элементы – это 1, 3, 5, 9, 11 и 13.
Малая теорема Ферма (примеры решения задач)
  • 2. Найдите результат 312 mod 11.
  • Решение
  • Здесь степень (12) и модуль (11) не соответствуют условиям теоремы Ферма. Но, применяя преобразования, мы можем привести решение к использованию малой теоремы Ферма.
Теорема Вильсона
  • Если p — простое, то выполняется сравнение
  • (p − 1)! + 1 ≡ 0(modp), (1.1)а если p — составное, то (1.1) не выполняется.
  • Для доказательства нам потребуется вспомогательное утверждение, которое интересно также и само по себе.
  • Лемма 1.1.1 Если  НОД(a,b) = 1, то существуют целые u,v, такие, что
  • au + bv = 1. (1.2)
  • Доказательство. Очевидно, достаточно доказать утверждение для случая, когда a, b — натуральные числа.
  • Нетривиальной частью доказательства является идея индукции по сумме a + b. При a + b = 2 имеем a = b = 1 и (1.2) выполняется с u = 1,v = 0. Пусть теорема верна для всех a,b, таких что  НОД(a,b) = 1, a + b < k, где k > 2. Тогда, так как a + b > 2,  НОД(a,b) = 1, то a ≠ b. Не теряя общности можно считать, что a > b. Поскольку  НОД(a − b,b) = 1 и (a − b) + b = a < k, по индуктивному предположению существуют целые x,y, такие, что
  • (a − b)x + by = 1,
  • или
  • ax + b(y − x) = 1.
  • Положив x = u,y − x = v, получим (1.2).
Теорема Вильсона (следствие)
  • Следствие 1.1.1 Если a > 1,b > 1,  НОД(a,b) = 1, то для каждого k = 0, 1,… существуют единственные целые числа u, v, такие, что выполняется
  • au − bv = 1,kb + 1 < u < (k + 1)b,k = 0, 1,… (1.3)
  • Доказательство. Существование u, v следует из леммы 1.1.1. Докажем единственность. Предположим, от противного, что имеются такие числа u′, v′, для которых u′ ≠ u, v′ ≠ v с условием kb + 1 < u′ < (k + 1)b и
  • au′− bv′ = 1. (1.4)Вычитая из (1.3) почленно (1.4) получим
  • a(u − u′) = b(v − v′).
  • Так как  НОД(a,b) = 1, то (u − u′)⋮b, но
  • 1 − b < u − u′ < b − 1,
  • следовательно, u − u′ = 0, и, поэтому, v − v′ = 0. Таким образом, u = u′, v = v′ и получено противоречие.
Теорема Вильсона (доказательство)
  • Доказательство теоремы 1.1.1 Вильсона. Предположим p — простое, p > 3 (для случаев p = 2, p = 3 утверждение теоремы не трудно проверить непосредственным вычислением). Докажем, что все числа
  • 2, 3,…,p − 2 (1.5)распадаются на пары чисел2 , произведение которых даёт при делении на p остаток 1. Пусть q пробегает ряд (1.5), тогда по следствию из леммы 1.1.1 найдутся единственные целые u,v, такие что qu − pv = 1,1 < u < p
  • Следовательно, множество чисел (1.5) можно разбить на такие пары (qi; qi¯), i = 1, 2,…, (p − 3)∕2, для которых
  • qiqi¯ = pvi + 1,i = 1, 2,…, (p − 3)∕2 (1.6)Перемножая (1.6) по всевозможным значениям i получим
  • (p − 2)! = pV + 1,
  • где V — некоторое натуральное число. После умножения обеих частей последнего равенства на p − 1 имеем
  • (p − 1)! = p(p − 1)V + p − 1,
  • или
  • (p − 1)! + 1 = p(p − 1)V + 1,
  • то есть соотношение (1.1).
  • Пусть теперь p — составное, тогда оно имеет простой делитель p1, причём p1 < p и, следовательно, (p − 1)!⋮p1. Тогда получим, что (p − 1)! + 1 не делится на p1 и, тем более, на p.
Теорема Вильсона (примеры решения задач)
  • 1. Доказать, что если простое число р представимо в виде 4n+1 , то существует такое число х , что х 2 +1 делится на р .
  • Решение. Пусть р=4n+1 – простое число. По теореме Вильсона, (4n)!+1 делится на р . Заменим в выражении 1 × 2 × 3 × ... × (4n)+1 все множители большие (p-1)/2=2n через разности числа р и чисел меньших (p-1)/2=2n . Получим: (p-1)!+1 = 1 × 2 × 3 × … × 2n × (p-2n)(p-2n+1) × … × (p-1) = (1 × 2 × 3 × … × 2n)[A × p+(-1) 2n × 2n × (2n-1) × … × 2 × 1]+1 = A 1 p+(1 × 2 × 3 × … × 2n) 2 )+1 .
  • Так как это число делится на р , то и сумма (1 × 2 × 3 × … × 2n) 2 +1 делится на р , т.е. x=(2n)!=((p-1)/2)!
  • 2. Число 2 является квадратом по модулю 7 , т.к.
  • 4 2 º 16 º 2(mod7). Значит, 2 - квадратичный вычет. (Сравнение x 2 º 2(mod7) имеет еще и другое решение: 3 2 º 9 º 2(mod7).) Напротив, число 3 является квадратичным невычетом по модулю 7 , т.к. сравнение x 2 º 3(mod7) решений не имеет, в чем нетрудно убедиться последовательным перебором полной системы вычетов: x = 0,1,2,3,4,5,6.
Литература:
  • С. Г. Гиндикин Малая теорема Ферма // Квант. — 1972. — № 10.
  • Э. Б. Винберг Малая теорема Ферма и ее обобщения // Математическое просвещение. — 2008. — В. 12. — С. 43–53.
  • Бухштаб А. А. Теория чисел, 2-е издание, М., 1966
  • Трост Э. Простые числа, пер. с нем., М., 1959
  • Виноградов И. М. Основы теории чисел. — 5 изд.. — М.-Л.: Гостехиздат, 1952.
  • А. Н. Колмогоров. Математика — наука и профессия. М.: Наука, 1988.
  • С. В. Житомирский. Архимед: Пособие для учащихся. М.: Просвещение, 1981.
  • Плутарх. Сравнительные жизнеописания. М.: Наука, 1994.
  • М. Айгнер, Г. Циглер. Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней. М.: Мир, 2006.
  • Виноградов И. М. Основы теории чисел. М.: Наука, 1981.
  • Чебышёв П. Л. Избранные труды. М.: изд. АН СССР, 1955.

Математика - еще материалы к урокам: