7. Метод математической индукции и делимость чисел.

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

Начнем с доказательства основной теоремы арифметики натуральных чисел: любое натуральное число большее 1, либо является простым, либо разлагается в произведение простых чисел, причем два разложения отличаются друг от друга лишь порядком множителей.

Сначала докажем существование разложения на простые множители. При имеем простое число 2, а потому наше утверждение истинно. Пусть любое натуральное число , меньшее либо простое, либо разлагается на простые множители. Докажем, что тогда и само число либо простое, либо разлагается на простые множители. Если простое, то наше утверждение истинно. Если же составное число, то где а и натуральные числа, меньшие По предположению эти числа разлагаются на простые множители. Заменяя их этими разложениями, получаем разложение на простые множители числа

Итак, теорема о существовании разложения на простые множители истинна при а из ее истинности для всех натуральных чисел, меньших следует, что она истинна и при Значит, она истинна при всех натуральных значениях больших 1.

А теперь докажем единственность (с точностью до порядка множителей) разложения на простые множители. Для этого нам понадобится следующее свойство простых чисел: если натуральное число делится на простое число то в любом разложении на простые множители один из множителей равен . В самом деле, если делится на где простые числа, то в силу свойств простых чисел один из множителей например должен делится на а так как простое число, то он должен совпадать с

При получаем простое число 2, которое, очевидно, не имеет иных разложений на простые множители. Пусть все натуральные числа меньшие имеют единственное разложение на простые множители. Если простое число, то оно не разлагается на множители и для него теорема единственности разложения истинна. Если же составное число, то оно делится хотя бы на одно простое число отличное от Тогда в любое разложение числа на простые множители входит множитель Иными словами, любое разложение на простые множители имеет вид где разложение на простые множители числа Так как - натуральное число, большее 1, но меньшее оно по предположению имеет единственное разложение на простые множители. А тогда и имеет единственное разложение. В силу метода математической индукции наше утверждение доказано.

Следующее утверждение можно сравнительно просто доказать и непосредственно. Покажем, как оно получается с помощью метода математической индукции.

Если натуральное число, то число четное.

При наше утверждение истинно: четное число. Предположим, что четное число. Так как

— четное число, то и

1) четное. Итак, четность доказана при а из четности выведена четность . Значит, четно при всех натуральных значениях

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

Рассмотренные примеры приводят к предположению индукции, что всегда делится на Но уже пример опровергает это утверждение: не делится на 4. При снова получаем, что делится на 5 (доказательство этого утверждения опирается на формулу бинома Ньютона). Числа 2, 3 и 5 простые. Поэтому уточним гипотезу: выражение где простое число, делится на Это утверждение (малая теорема Ферма) истинно для всех простых чисел и всех натуральных чисел Его доказательство проводится методом математической индукции с использованием формулы бинома Ньютона (см. с. 35; 36).