Задача 3
Доказать, что 3n(13n-10n-6n)+65n делится на 56 при всех нечетных n.
Решение: так как 56=7·8, то достаточно доказать делимость данного выражения на 7 и на 8. Это можно сделать, представив заданное выражение в следующем виде:
3n(13 n-10n-6n)+65n=39n-30n-18n+65n=3n(13n-6n)+5n(13n-6n)=(13n-6n)(3n+5n). Первый сомножитель делится на 7, а второй на 8 при всех нечетных n.
Четность и нечетность чисел
Как известно, все целые числа можно разбить на две группы – четные и нечетные числа. Все четные имеют вид 2n, нечетные 2n+1, где n – любое целое число. Посмотрим, как понятие четности и нечетности чисел может быть использовано при решении некоторых задач.
Задача 1
Доказать, что уравнение x2+1982=y2 не имеет решений в целых числах.
Решение: предположим, что уравнение имеет решения в целых числах. Запишем данное уравнение в таком виде: 1982=y2-x2. Так как 1982 четное число, то, чтобы уравнение имело решение, необходимо, чтобы разность y2-x2 была четным числом, а это возможно только тогда, когда x и у числа одинаковой четности, т.е. x и у одновременно четные, или оба нечетные числа.
Теперь запишем уравнение в таком виде: 1982=(y+x)(у-x). Так как x и у числа одинаковой четности, то и сумма, и разность их будут четными числами, следовательно, правая часть уравнения будет делится на 4, но левая часть на 4 не делится. Полученное противоречие и показывает, что уравнение решений в целых числах иметь не может.
Задача 2
Решить в простых числах уравнение х2-2у2=1. Так как вычитаемое 2у2 четно, а разность нечетна, то уменьшаемое х2 должно быть нечетно, откуда и x нечетно. Запишем уравнение в таком виде: (х-1)(х+1)=2у2. Так как x нечетно, то х-1 и х+1 четные числа, произведение их делится на 4. Но раз левая часть делится на 4, то, чтобы уравнение имело решение, необходимо, чтобы правая часть также делилась на 4, что возможно только при четном у. Но x и у простые числа, следовательно, у=2, откуда х=3.
Квадрат натурального числа
Задачи, связанные с квадратом натурального числа, часто решаются на основании следующих положений.
1. Квадрат натурального числа либо делится на 4, либо при делении на 8 дает в остатке 1. Действительно, если а=2k, то а2=4k2делится на 4. Если а=2k+1, то а2=4k2+4k+1=4k(k+1)+1 и остаток от деления на 8 есть единица, ибо 4k(k+1) делится на 8.
2. а2 либо делится на 9, либо при делении на 3 дает в остатке 1. Если а=3k, то а2=9k2; если а=3k-/+1, то а2=9k2-/+6k+1, что и доказывает наше утверждение.
3.Между квадратами а2 и (а+1)2 не содержится не содержится ни одного точного квадрата.
4.Точный квадрат не может оканчиваться цифрами 2, 3 , 7, 8, а также нечетным числом нулей.
5.Если разность двух натуральных чисел равна 2k, то произведение этих чисел, увеличенное на k2, есть точный квадрат. Доказательство. Пусть а-b=2k, откуда, а=b+2k. Тогда аb+k2=(b+2k)b+k2=b2+2bk+k2=(b+k)2.
Задача 1
Доказать, что при любом натуральном n число 3n+2 не является квадратом целого числа.
Решение: мы знаем, что квадрат натурального числа либо делится на 9, либо при делении на 3 дает в остатке 1. Наше число 3n+2 при делении на 3 дает в остатке 2, а значит, оно не является квадратом натурального числа.
Задача 2
Доказать, что не существует целых чисел x и y, удовлетворяющих уравнению 15x2=9+7y2.
Решение: левая часть уравнения кратна 5, выясним, делится ли на 5 и правая часть уравнения. Квадрат любого натурального числа может оканчиваться цифрами 0,1,4,5,6,9, тогда
7y2 может оканчиваться на 0,7,8,5,2,3, а 9+7y2 будет оканчиваться на 9,6,7,4,1,2, но ни одно из таких чисел на 5 не делится, т.к. на 5 делятся числа, оканчивающиеся 0 или 5. Значит, уравнение не имеет решений в целых числах.
Задача 3
Доказать, сумма квадратов двух нечетных чисел не может быть квадратом целого числа.
Решение: сумму квадратов двух нечетных чисел можно представить так:
(2k+1)2+(2n+1)2=4k2+4k+1+4n2+4n+1=4k2+4k+4n2+4n+2=4(k2+k+n2+n)+2=4(k(k+1)+n(n+1))+2. Эта сумма не делится нацело на 4, (так как дает остаток 2), а при делении на 8 остаток тоже равен 2, так как (k(k+1)+n(n+1)) – число четное, ведь k(k+1) и n(n+1) – произведения двух последовательных натуральных чисел, одно из которых обязательно делится на 2. Значит, 4(k(k+1)+n(n+1)) делится на 8, а 2 на 8 не делится. Но мы знаем, что квадрат натурального числа либо делится на 4, либо при делении на 8 дает в остатке 1, поэтому сумма квадратов двух нечетных чисел не может быть квадратом целого числа.
Бином Ньютона
Многие задачи на делимость чисел могут быть решены с использованием разложения бинома Ньютона. Оно имеет вид: (х+а)n=cn0xn+cn1xn-1a+cn2xn-2a2+…+cnkxn-kan+…+cnnan, где сnk=n!/k!(n-k)!. Число членов разложения равно n+1. Если бином имеет вид (х-а)n, то все члены разложения, стоящие на четных местах, имеют знак минус, на нечетных местах – знак плюс.
Задача 1
Доказать, что 29n+32n-2n+3 делится на 9 при всех натуральных n.
Решение: 29n+32n-2n+3 =(27-2)n+9n-8·2n=27·К-2n+9n-8·2n=27K+9n-8·2n-2n=27K+9n-9·2n. Все члены разложения бинома, кроме последнего, имеют множителем число 27, следовательно, делятся на 9. Последний член разложения (–2n). Тогда данное число можно записать так: 27K+9n-9·2n, где K – частное от деления n первых членов разложения бинома Ньютона на 27. В полученной сумме каждое слагаемое делится на 9, значит, и сумма делится на 9.
Задача 2
Найти остаток от деления числа 1015+1017+74 на 9.
Решение: 1015=(9+1)15=9·К+115, где К - частное от деления первых 15 членов разложения двучлена (9+1)15 в многочлен.
1017=(9+1)17=9·N+117, где N - частное от деления первых 17 членов разложения двучлена (9+1)17 в многочлен.
74=9·8+2
Тогда 1015+1017+74=9K+1+9N+1+9·8+2=9(K+N+8)+4, значит, остаток равен 4.
Малая теорема Ферма
Некоторые задачи на делимость целых чисел могут быть решены при помощи так называемой «малой» теоремы Ферма.
Теорема Ферма (малая). Если р число простое, р и а взаимно просты, то ар-1-1 делится на р.
Иногда применяют следствие из этой теоремы: для простого р и любого натурального а ар-а делится без остатка на р.
Задача 1
Найти остаток от деления 230 на 13.
Решение: 230=226·24=413·16-16·4+16·4=16(413-4)+64. Первое слагаемое делится на 13 по теореме Ферма, а так как 64=13·4+12, то остаток от деления равен 12.
Задача 2
Доказать, что а12-b12 делится на 65, если а и b взаимно простые числа с 65.
Решение: 65=13·5. Сначала докажем делимость данной разности на 13. Для этого запишем так: a12-b12=(a12-1)-(b12-1). По теореме Ферма каждое слагаемое делится на 13, следовательно, разность a12-b12 делится на 13. Теперь докажем делимость на 5. a12-b12=((a4)3-1)-((b4)3-1)=(a4-1)(a8+a4+1)-(b4-1)(b8+b4+1). Из того, что a4-1 и b4-1 делятся на 5, следует делимость на 5 всего данного числа. Но раз число делится и на 5 и на 13, то оно делится на 65, т.к. 5 и 13 взаимно просты.
Последняя цифра числа
Если число оканчивается на 0, 1, 5, 6, то и любая натуральная степень его оканчивается соответственно на 0, 1, 5, 6. Если же рассмотреть 1, 2 , 3, 4 и т.д. степени числа 2, то получим, что последними цифрами будут соответственно 2, 4, 8, 6, 2, 4, 8, 6…Слндовательно, последние цифры будут периодически повторятся через 4. Таким образом, 24n+1 оканчивается цифрой 2, 24n+2 – 4, 24n+3 – 8, 24n+4 – 6, где nЄN.
Аналогичная картина будет и в случае, когда число будет оканчиваться цифрами 3, 7, 8. Так, 34k+1 оканчивается цифрой 3, 34k+2 – цифрой 9, 34k+3 – цифрой 7, 34k+4 – цифрой 1, где kЄN, 74k+1 оканчивается цифрой 7, 74k+2 – цифрой 9, 74k+3 – цифрой 3, 74k+4 – цифрой 1, kЄN, 84k+1 – цифрой 8, 84k+2 – цифрой 4, 84k+3 – цифрой 2, 84k+4 – цифрой 6, kЄN.
Для чисел, оканчивающихся на цифры 4 и 9, период повторяемости равен 2.
42k-1 оканчивается цифрой 4, 42k – цифрой 6, kЄN.
92k-1 – цифрой 9, 92k – цифрой 1, где kЄN.
Задача 1
Какой цифрой оканчивается число 19821982?
Решение: 19821982=19824· 495+2 – оканчивается такой же цифрой, как и 22, т.е. 4.
Задача 2
Доказать, что число 1111+1212+1313 делится на 10.
Решение: 1111+1212+1313=1111+124·3+134·3+1.
1111 оканчивается цифрой 1, 124·3 оканчивается цифрой 6, 134·3+1 оканчивается цифрой 3, значит, вся сумма 1111+124·3+134·3+1 оканчивается цифрой 0, т.к. 1+6+3=10, а если число оканчивается 0, то оно кратно 10.
Этот метод основан на Арифметике сравнений или Арифметике остатков.
«Остатки» играют в нашей жизни большую роль. Мы встречаемся с ними буквально на каждом шагу. Приведем несколько примеров.
1. Говоря «30 год», мы указываем век, так как 30 год может быть и в XX в., и в XIX в., и в XVIII в.; 30 – это остаток от деления полного числа лет на 100.
2. Вы взглянули на часы, которые показывают 8 ч. Но это может быть и 8 ч и 20 ч, так как часы показывают остаток от деления полного времени на 12.
3. Счетчик показывает 0314 кВт • ч. Это может быть и 0314 кВт•ч и 10314 кВт•ч и 20314 кВт•ч, так как счетчик показывает остаток от деления израсходованного числа киловатт-часов на 10 000. Таких примеров можно привести множество. Иногда найти остаток совсем нетрудно. А как, например, найти остаток от деления числа 1996•1997•1998•1999•2000•2001 на 7? Перемножить и разделить? Представьте себе проблемы, с которыми придется столкнуться. Эту задачу мы решим немного позже и почти устно, познакомившись с теорией «Арифметика остатков» или «Арифметика сравнений».