Доказательства малой теоремы Ферма
Во-первых, мы можем предположить, что a находится в диапазоне 0 ≤ a ≤ p − 1 . Это простое следствие законов модульной арифметики ; мы просто говорим, что мы можем сначала уменьшить по модулю p . Это согласуется с уменьшением по модулю p , как можно проверить.
для a в диапазоне 1 ≤ a ≤ p − 1 . В самом деле, если предыдущее утверждение верно для такого a , умножение обеих частей на a дает исходную форму теоремы,
Это, пожалуй, самое простое известное доказательство, требующее минимальной математической подготовки. Это привлекательный пример комбинаторного доказательства (доказательство, включающее подсчет набора объектов двумя разными способами ).
Для простоты предположим, что a — положительное целое число . Рассмотрим все возможные цепочки из p символов , используя алфавит с разными символами. Общее количество таких строк равно p , так как для каждой из p позиций есть возможности ( см . правило произведения ).
Например, если p = 5 и a = 2 , то мы можем использовать алфавит с двумя символами (скажем, A и B ), и имеется 2 5 = 32 строки длины 5:
Ниже мы покажем, что если мы удалим из списка строки, состоящие из одного символа (в нашем примере, AAAAA и BBBBB ), оставшиеся строки a p − a можно разбить на группы, каждая из которых будет содержать ровно p строк. Отсюда следует, что a p − a делится на p .
