Доказательство делимости: математическая индукция и примеры

Делимость

Предположим, вы и четверо ваших друзей выиграли лотерейный билет с выигрышем в 1000 рублей. И вот, в конечном итоге вы выигрываете, поэтому вам нужно разделить 1000 рублей между вами пятерыми. Чтобы подсчитать доход каждого человека, нужно разделить 1000 на 5.

1000/5 = 200

Каждый из вас получит приятную сумму в целых 200 рублей. Это потому, что 5 делится на 1000 поровну. С математической точки зрения мы бы сказали, что 1000 делится на 5 или что 5 делит 1000.

В общем, если мы разделим число a на число b и получим целое число m, то мы скажем, что a делится на b или что b делит a. То есть,

  • Если a/b = m или a = b * m, где m — целое число, то a делится на b или b делит a.

Это определение делимости также применимо к математическим выражениям. Если математическое выражение A делится на число b, то A = b*m, где m — целое число.

Этот факт, наряду с математической индукцией, оказывается чрезвычайно полезным в процессе доказательства делимости. Математическая индукция — это метод доказательства, который мы можем использовать для доказательства делимости. Давайте рассмотрим эту технику.

Математическая индукция

Математическая индукция — это метод доказательства, основанный на следующем факте:

  • В хорошо упорядоченном наборе (или наборе, который имеет первый элемент и элементы в наборе упорядочены, как натуральные числа), если свойство истинно для n и n + 1, где n — любой элемент набора , то это верно для всех элементов множества.

Процесс доказательства утверждений посредством математической индукции состоит из трех этапов:

  • Базовый шаг: докажите, что утверждение верно для первого элемента набора.
  • Предположим, что утверждение верно для элемента k из множества
  • Докажите, что утверждение верно для элемента k + 1 из множества.

Эти три шага покажут, что свойство истинно для k и k + 1, где k — любой элемент в наборе, что доказывает, что свойство истинно для всех элементов в наборе.

Мы можем использовать математическую индукцию вместе с нашими фактами о делимости, чтобы доказать, что выражение делится на число из хорошо упорядоченного множества. Мы обнаружим, что третий шаг — самый сложный, но как только вы попрактикуетесь в этом процессе несколько раз, он станет проще. Давайте сделаем это!

Примеры

Предположим, мы хотим показать, что 9n делится на 3 для всех натуральных чисел n. Для этого мы можем использовать математическую индукцию.

Доказательство математической индукции

Первым шагом (также называемым базовым шагом) будет показать, что 9n делится на 3 при n = 1, поскольку 1 — первое натуральное число.

  • 91 = 9 и 9 = 3 * 3. Поскольку 91 = 3 * 3, а 3 — целое число, из нашего определения делимости следует, что 91 делится на 3. Это доказывает наш базовый шаг.

Это было не так уж плохо! Переходим к следующему шагу!

Второй шаг — предположить, что утверждение верно для натурального числа k. То есть мы предполагаем, что 9к делится на 3. Следовательно, по определению делимости имеем, что:

  • 9k  = 3*m, где m — целое число

Это уравнение пригодится на шаге 3.

Остался один шаг!

Третий и последний шаг — показать, что 9k+1  делится на 3. Используя определение делимости, мы хотим показать, что:

  • 9k+1 = 3 * j, где j — целое число

Начнем с рассмотрения выражения 9k+1. Заметить, что:

  • 9k+1 = 9 ⋅ 9k

Кроме того, из шага 2 мы имеем, что 9k = 3 * m, где m — целое число. Следовательно, мы можем подставить в выражение 3м вместо 9k и упростить.

  •  9k+1= 9 ⋅ 9k = 9 ⋅ 3m = 3 * (9m)

Теперь, поскольку m — целое число, 9m — целое число. j = 9m, поэтому 3 * (9m) = 3j, где j — целое число. В совокупности это показывает, что:

  • 9k+1 = 3j, где j — целое число

Это именно то, что мы хотели показать! Таким образом, методом математической индукции мы доказали, что 9n делится на 3 для всех натуральных чисел n.

Итоги урока

Если мы разделим число a на число b и получим целое число m, то можно сказать, что a делится на b или b делит a. То есть,

  • Если a/b = m или a = b * m, где m — целое число, то a делится на b или b делит a

Это определение делимости также применимо к математическим выражениям. Итак, если математическое выражение A делится на число b, то A = b*m, где m — целое число.

Когда мы пытаемся доказать делимость всех элементов в хорошо упорядоченном множестве, где хорошо упорядоченное множество — это множество, в котором первый элемент и все его элементы упорядочены, мы можем использовать технику доказательства, называемую математической индукцией. Математическая индукция состоит из трех этапов:

  • Базовый шаг: докажите, что утверждение верно для первого элемента набора.
  • Предположим, что утверждение верно для элемента k из множества
  • Докажите, что утверждение верно для элемента k + 1 из множества.

Этот метод доказательства — один из тех процессов, к которому нужно привыкнуть, поэтому продолжайте практиковаться, и станет легче! Ведь практика приводит к совершенству!

Поделитесь материалом
Автор статьи: Наталья Венедиктова
Наталья Венедиктова
Историк-исскусствовед, специалист в области истории, географии и искусства. Много путешествовала, изучала эволюцию художественных стилей, культурные контексты произведений и влияние искусства на общественные и исторические процессы.
Наталья Венедиктова опубликовал статей: 315

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *