1 шаг. Проверим справедливость утверждения при n=1:
- верно
2 шаг. Предположим, что при n=k следующее утверждение верно:
3 шаг. Докажем, что при n=k+1 следующее утверждение также будет верно:
Для доказательства выполним преобразования:
Рассмотрим получавшуюся сумму. Первое слагаемое делится на 9 по предположению, сделанному на предыдущем шаге. Во втором слагаемом первый множитель делится на 3. Значит, остается доказать, что второй множитель также делится на 3. Докажем это, используя арифметику остатков:
Мы получили, что выражение дает при делении на 3 такой остаток, как и число 3. Но число 3 кратно 3, значит и выражение кратно 3.
Возвращаясь к выражению , повторим, что первое слагаемое делится на 9, второе слагаемое представляет собой произведение двух множителей, каждое из которых делится на 3, то есть само слагаемое делится на 9. Сумма двух выражений, делящихся на 9, также делится на 9, или другими словами, кратна 9. Доказано.
Простыми преобразованиями эту задачу не решить, будем использовать арифметику остатков.
1-ое свойство, которое понадобится
То есть мы спокойно можем заменить каждое слагаемое сравнимым с ним по модулю m. То есть каждое слагаемое в нашей сумме будем рассматривать отдельно.
2-ое свойство, которое нам понадобится:
То есть довольно аналогичная вещь в произведении
На нашем примере все увидим
Находим остатки по модулю 31
Рассматриваем первое слагаемое. Просто двойка не годится, нам нужно найти ближайшее к 31 число, превосходящее его (иногда там в отрицательные числа залезаем, например, , но сейчас это не нужно), нам повезло, это 32
Учитываем, что , получаем
То есть остаток от деления первого слагаемое на 31 получился равным 10. Прекрасно, аналогично со вторым
Остаток 21, чудесно. Выполняем последний шаг.
То есть остаток от деления исходного числа на 31 равен 0, следовательно, исходное число делится на 31, что и требовалось доказать.
1 шаг. Проверим справедливость утверждения при n=1:
- верно
2 шаг. Предположим, что при n=k следующее утверждение верно:
3 шаг. Докажем, что при n=k+1 следующее утверждение также будет верно:
Для доказательства выполним преобразования:
Рассмотрим получавшуюся сумму. Первое слагаемое делится на 9 по предположению, сделанному на предыдущем шаге. Во втором слагаемом первый множитель делится на 3. Значит, остается доказать, что второй множитель также делится на 3. Докажем это, используя арифметику остатков:
Мы получили, что выражение дает при делении на 3 такой остаток, как и число 3. Но число 3 кратно 3, значит и выражение кратно 3.
Возвращаясь к выражению , повторим, что первое слагаемое делится на 9, второе слагаемое представляет собой произведение двух множителей, каждое из которых делится на 3, то есть само слагаемое делится на 9. Сумма двух выражений, делящихся на 9, также делится на 9, или другими словами, кратна 9. Доказано.
Простыми преобразованиями эту задачу не решить, будем использовать арифметику остатков.
1-ое свойство, которое понадобится
То есть мы спокойно можем заменить каждое слагаемое сравнимым с ним по модулю m. То есть каждое слагаемое в нашей сумме будем рассматривать отдельно.
2-ое свойство, которое нам понадобится:
То есть довольно аналогичная вещь в произведении
На нашем примере все увидим
Находим остатки по модулю 31
Рассматриваем первое слагаемое. Просто двойка не годится, нам нужно найти ближайшее к 31 число, превосходящее его (иногда там в отрицательные числа залезаем, например, , но сейчас это не нужно), нам повезло, это 32
Учитываем, что , получаем
То есть остаток от деления первого слагаемое на 31 получился равным 10. Прекрасно, аналогично со вторым
Остаток 21, чудесно. Выполняем последний шаг.
То есть остаток от деления исходного числа на 31 равен 0, следовательно, исходное число делится на 31, что и требовалось доказать.