Задание на метод математической индукции

Математика Теория Чисел
1

Нужно доказать, что 5^{k+3} + 11^{3k+1} делится без остатка на 17. Приведу часть своего решения:

  1. k = 1
    (5^4 + 11^4) \ \vdots \ 17 – верно

  2. k = n
    5^{n+3} + 11^{3n+1} \ \vdots \ 17 – пусть верно

  3. k = n+1
    5^{n+4 } + 11^{3n+4} \ \vdots \ 17

А дальше возникли сложности, я пытался представить 11^{3n+4} как 11^{3n+1} * 6^3 + 11^{3n+1} * 5^3 , чтобы вынести 5 за скобки и получить случай при k=n, но не получилось

2

Я делал так:

Для случая k=n+1 получается 5 \cdot 5^{k+3}+11^3 \cdot 11^{3k+1}. Если искусственно прибавить и отнять на 5 \cdot 11^{3k+1}, то я могу это переписать как 5 \cdot (5^{k+3}+11^{3k+1})+(11^3-5) \cdot 11^{3k+1}. Как оказывается,

\frac{11^3-5}{17}=78

а значит всё полученное выражение делится нацело на 17. Это не так очевидно, да и заметил я это подбором на калькуляторе)

6 лайков
3

Можно еще так сделать

5^{k+3} + 11^{3k+1}=5^k\cdot 125+1331^k\cdot 11 \equiv 5^k\cdot 6 + 5^k\cdot 11=5^k\cdot 17\equiv 0 \pmod{17}.
7 лайков
4

Можешь, пожалуйста, пояснить, как именно 5 * (5^k+3 + 1^3k+1) + (11^3 - 5) * 11^3k+1 появилось, я просто не очень понимаю этот момент с вынесением какого то числа за скобки и прибавлением/вычитанием другого числа

5

На самом деле логика проста: надо максимально вытащить изначальное выражение ( 5^{k+3} + 11^{3n+1} ) от нового. Видим, что как минимум 5 штук есть. Вытаскиваем и доказываем, что остальное тоже делится

5^{k+4} + 11^{3k+4} = (5*5^{k+3} + 5*11^{3k+1}) [вытащили 5 штук] + (11^3-5)*11^{3k+1} [добавили остаток]

5 лайков
6

Хорошо, но лучше переписывай этот ход решения в тетради, потому что всё равно тяжеловато пробежаться глазами и сразу понять вывод)
Пусть P(k)=5^{k+3}+11^{3k+1} \space \vdots \space 17. Для следующей итерации

P(k+1)=5^{(k+1)+3}+11^{3(k+1)+1} = 5^{k+3} \cdot 5+11^{3k+1} \cdot 11^3

Теперь прибавляю и отнимаю на 11^{3k+1} \cdot 5, тогда я получаю:

P(k+1)= 5^{k+3} \cdot 5+11^{3k+1} \cdot 11^3 + 11^{3k+1} \cdot 5 - 11^{3k+1} \cdot 5.

Теперь соберу первое и третье слагаемые, вынося 5 за скобки, а второе и четвёртое слагаемые собираю с выносом 5 \cdot 11^{3k+1}:

P(k+1)= 5 \cdot (5^{k+3}+11^{3k+1}) + (11^3-5) \cdot 11^{3k+1}.

Иначе:

P(k+1)=5P(k) + (11^3-5)\cdot 11^{3k+1}.

Как видим, первое слагаемое (предположительно) делится на 17, а у второго слагаемого есть коэффициент 11^3-5, который тоже делится на 17. Значит P(k+1) тоже делится нацело на 17, что доказывает P(k) \space \vdots \space 17.

ну так и нужно в принципе, но я говорил про то, что делимость 11^3-5 на 17 не сразу увидишь.

5 лайков