Отправлено: 15.08.07 14:19. Заголовок: Малая теорема Ферма

Теорема: Если р = простое число и а = целое число, не делящееся на р, то a^p-1 = 1 делится на р, т. е. a^{p-1 0}1(modp).
Доказательство: ведётся с помощью математической индукции. Если кому интересно, можете найти его в Википедии.

Теорему высказал без доказательства П. Ферма, первое доказательство дал Л. Эйлер.

 Отправлено: 15.08.07 14:20. Заголовок: Re:

А ты нам найди сама доказательство

 Отправлено: 15.08.07 14:37. Заголовок: Re:

 Отправлено: 15.08.07 14:39. Заголовок: Re:

Всё понятно с тобой... А мне вот неинтересно, так что искать не буду.

 Отправлено: 25.10.07 13:27. Заголовок: Re:

Девушка в чёрном пишет:

цитата:

Теорема: Если р = простое число и а = целое число, не делящееся на р, то ap-1 = 1 делится на р, т. е. ap-1 01(modp). Доказательство: ведётся с помощью математической индукции. Если кому интересно, можете найти его в Википедии. Теорему высказал без доказательства П. Ферма, первое доказательство дал Л. Эйлер.

Во-первых это теорема Эйлера!

С помощью теории групп эта теорема доказывается очень легко без индукции.

множество {a, a², a³,...., a^p-1} образуют циклическую группу(по умножению классов вычетов по модулю m, порожденную элементом а (т.е. все остальные элементы группы являются степенями элемента a)
Но как известно, любой элемент конечной группы при возведении в степень порядка(порядок=кол-во элементов группы) группы дает единицу.
т.е a^p-1 =1 mod m .

Но теорема Эйлера утверждает даже больше:

a ^f(p) =1 mod m ; где f - функция Эйлера равная числу чисел меньших p и таких что их НОД =1 т.е. взаимно простых с p. В частности f(p)=p-1 если p-простое число.

 Отправлено: 19.12.07 14:47. Заголовок: Здравствуйте! Есть ..

Здравствуйте!

Есть простое доказательство малой теоремы Ферма, не использующее индукцию и теорию групп. Вот оно.

Рассмотрим последовательность 1,2, .. ,p-1, где p - простое. Пусть a не делится на p. Умножим каждое число k_i в последовательности на a и возьмём остаток от деления на p:

x_i = k_i*a mod p ````` (1)

При этом получатся те же числа, но, возможно, в другом порядке. Действительно, не может получиться 0 (так как k_i и a не делятся на p). Не могут также получиться одинаковые значения, иначе было бы:

k_i*a mod p = k_j*a mod p, или (k_i - k_j)*a = 0 (mod p),

что невозможно, если i не равно j. Перемножая сравнения (1), получим

1*2* .. *(p-1)*a^(p-1) = 1*2* .. *(p-1) (mod p).

Т.к. 1*2*..*(p-1) не делится на p, то

a^(p-1) = 1 (mod p).

------

Точно также доказывается теорема Эйлера (см. Википедия, статья называется "Теорема Эйлера (теория чисел)"). Введение в теорию групп и доказательство малой теоремы Ферма, использующее теорию групп, есть в книге Гроссмана и Магнуса "Группы и их графы" серии "Популярная математика".

 Отправлено: 31.12.07 02:48. Заголовок: Вот мат-индукция - о..

Вот мат-индукция - одна из мерзейших тем ! да!