Теоремы о делимости

• (а: с лЬ: с)—> (а + Ь): с (делимость суммы);

• (а: с л Ь: с л Ь < а) -> (а - Ъ): с (делимость разности);

• а: с -» аЬ: с (делимость произведения);

• {а: с лЬ: с/)—> (аЬ): {сс1) (делимость произведения).

Доказательства этих свойств основаны на определении 3.1. Рассмот­рим доказательство утверждения 8.

Доказательство. Если а: с и Ъ: то по определению 3.1. суще­ствуют целые неотрицательные числа ц, и д₂ такие, что а = сц_р Ь - Тогда число аЬ = (сд_})-(йд₂) = с-(д₁ • (с/д_? )) = с < ((д_гс1) -д₂) = = с-((с! •д_}) -д₂) = с.(а.(д^.д₂)) = (с.а) •\д₁-д₂).

Так как д_г д_? е Л^, то д_; • ^еА^. Тогда по определению 3.1 (я/;): («/).

Пример 3.1. Доказать, что сумма двузначного числа и числа, записанного теми же цифрами в обратном порядке, делится на 11.

Для доказательства запишем данное утверждение на языке симво­лов. Одно число обозначим аЬ, другое — Ьа ■ Рассмотрим их сумму: аЬ + Ьа = 10 а + Ь + Ш+а=\\а+\\Ъ = 11 (а + Ь).

32 тде>

Пример 3.2. Доказать, ч то произведение двух последовательных натуральных чисел делится на 2.

Доказательство. Требуется доказать, что п(п +1): 2. Для доказа­тельства разобьем множество всех натуральных чисел на два подмно­жества: четных и нечетных чисел. В каждом случае докажем данное ут­верждение, а затем сделаем общий вывод.

• если п ~ 2 к, то первый множитель п: 2.

• если п =2к + 1, то второй множитель п + \ = 2к + \ + \ - 2к + 2. - 2(к + 1): 2»

В каждом из частных случаев один из множителей произведения делит ся на 2. Значит, данное произведение делится на 2.

Пример 3.3. Доказа ть, что число 2я³ - 3 п² + п делится на 3 при любом натуральном п.

Доказательство. Применим метод полной индукции. Выполним раз­ложение на множители данного числа:

2 п³- 3 п² +п=п( 2 п²- Зл + 1) = п (п - 1)(2п - 1).

Для доказательства делимости на 3 рассмотрим числа вида п - Ък; п - ЗА- + 1; _п - 3 к + 2:

• если п = 3 к, то первый множитель п делится на 3;

• если п- ЗА" + 1, то в торой множитель п - 1 = (ЗА; + 1) -1 = ЗА: делится на 3;

• если п - Ък+ 2, то третий множитель 2п - 1 = 2(3/с + 2) - I = +

+ 4 - 1 = Ьк + 3 = 3 (2А- + 1) делится на 3.

Мы показали, что для любого натурального п, кратного или не кратного 3, произведение п(п ~ 1)(2 п - 1) делится на 3, а значит, число 2 п³~ 3 п² + п делится на 3 при любом натуральном п.

IIр им ер 3.4. Доказать, что при любом натуральном п число а_п- 2п³ + 9 п²+ п делится на 6.

Доказательство. Докажем это утверждение методом математичес­кой индукции.

• Если п = 1, то а = 2- 1³+ 9 • 1²+ 1 = 12, и потому й ₁ делится на 6, а значит, утверждение истинно при п- 1.

• Допустим, что утверждение истинно при п = к, т. е. что число а_к- 2к³ + 9 к² + А- делится наб.

• Докажем, что при л = к + 1 число а_к+! делится на 6. В самом деле,

а., = 2(к+ \у+9(к+ 1 )²+(к+ \)~Ус³+ вк²+Ьк + 2+-9к²+ 18 к +

+9 +к+\- (2 к³ + 9 к²+к) + (6к² + 24к + 12) = а_к+ 6(к² + 4к + 2 ).

Так как каждое слагаемое последней суммы (число а_к соответствен­но по предположению, а число 6(к²+ 4 к + 2) как натуральное, которое содержит множитель 6) делится на 6, то и сумма делится на 6.

Значит, на основании пп.1 и 2 и принципа математической индук­ции можно сделать вывод, что при любом натуральном п число а_п де­лится на 6.

* Задания-упражнения

• Доказать с помощью мет ода полной индукции, что при любом натуральном л число а_п делится на Ь, если:

а) а_п~ п⁴ + Ъп³- п²- Зл, Ь~6;

б) а= п⁴- 2 п³-п²+ 2п, Ь = 24;

в) а~ п⁵- 5п³+ 4п, Ь-\ 20.

• Доказать с помощью метода математической индукции, что при любом натуральном п число а_ делится на Ь, если;

а) а = 5²⁺" + 26 • 5" + 8²" ⁺¹, А = 59;

б) 5" ⁺³ • 2" - 125, /> = 45;

в) а" = 5^5п+! + 4^5п+2 + З⁵», Ъ- 11.