Теория делимости натуральных чисел

Задание 15. Докажите, что утверждение верно при любом натуральном числе n.

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

Решение. В данном произведении п(п + 1) число п или четное (2а), или нечетное (2а+1).

Если п = 2а, то п(п + 1) = 2а(2а + 1) – делится на 2 по теореме о делимости произведения; если п = 2а + 1, то п(п + 1) = (2а + 1)(2а + 2) = 2(2а + 1)(а + 1) – также делится на 2.

Следовательно, данное произведение делится на 2 при любом натуральном числе п.

Варианты.

1. п³ - п делится на 6;

2. п⁵ - п делится на 6;

3. п⁴ – п² делится на 4;

4. п⁵ - п делится на 5;

5. Если числа а и b при делении на 3 дают разные остатки, то а· b+1 делится на 3;

6. Квадрат натурального числа или делится на 4, или при делении на 4 дает в остатке 1;

7. Если натуральное число а не делится на 5, то (а²+1) или (а²-1) делится на 5;

8. п² (п² – 1) делится на 12;

9. Разность квадратов двух последовательных нечетных чисел делится на 8;

10. - натуральное число.

Задание 16. Докажите методом математической индукции, что утверждение верно для любого натурального числа п.

Пример. (4^п – 1)  3.

Решение. 1) Проверим, истинно ли данное утверждение при n = 1. Имеем 4¹ - 1 = 3, и 3  3, следовательно, при n = 1 данное утверждение верно.

2) Предположим, что данное утверждение верно и при n = т > 1, т.е. (4^т – 1) 3 - истинно.

Докажем, что данное утверждение истинно и при n = т + 1, т.е. (4^{т + 1} – 1) 3 - истинно.

В самом деле: 4^т+1 – 1 = 4^т · 4 – 1 = 4^т(3 + 1) – 1 = 3 · 4^т + 4^т – 1 = 3 · 4^т + (4^т – 1).

В данном выражении 3 · 4^т делится на 3, т.к. один из множителей делится на 3; второе слагаемое (4^т – 1) делится на 3 по предположению. Откуда, на основании теоремы о делимости суммы вытекает делимость на 3 всего выражения 3 · 4^т + (4^т – 1).

Вывод: из того, что данное выражение делится на 3 при n = 1 и из предположения, что оно делится на 3 при n = т>1, вытекает, что данное выражение (4^п - 1) делится на 3 и при n= т + 1; по аксиоме индукции можно утверждать, что оно будет делиться на 3 при любом натуральном n.

Варианты.

1. (6^2п + 3^п+2 + 3^п) делится на 11;

2. (7^п+2 +8^2п+1) делится на 57;

3. (11^п+2 + 12^2п+1) делится на 133;

4. (3^3п+2 + 5·2^3п+1) делится на 19;

5. (4^п + 15п – 1) делится на 9;

6. (2·7^п + 1) делится на 3;

7. (9^п – 8п –1) делится на 8;

8. (3^2п+1 +1) делится на 4;

9. (4·6^п + 5п – 4) делится на 5;

10. (5^2п-1 + 1) делится на 6.

Задание 17. С помощью признаков делимости и теорем о делимости суммы и разности выясните, простыми или составными являются данные числа.

Пример. 971, 247.

Решение. Рассмотрим число 247. Используя признаки делимости, устанавливаем, что оно не делится на простые числа 2, 3, 5.

247 7, т.к. (210 +37) 7 по теореме делимости суммы; 247 11, т.к. (220 + 27) 11; но 247  13, т.к. (260 – 13)  13. Следовательно, 247 - составное число, т.к. имеет натуральный делитель 13, отличный от 1 и самого числа 247.

Рассмотрим число 971.

Используя признаки делимости и теоремы о делимости суммы и разности, устанавливаем, что число 971 не делится на 2, на 3, на 5, на 7, на 11, на 13, на 17, на 19, на 23, на 29, на 31. Следовательно, число 971 - простое, т.к. следующее за 31 простое число 37 превышает , ибо 37² = 1369.

Варианты.

1. 521, 437, 969;

2. 613, 741, 221;

3. 283, 647, 1001;

4. 481, 433, 319;

5. 473, 613, 119;

6. 754, 239, 373;

7. 409, 885, 541;

8. 221, 449, 805;

9. 521, 741, 383;

10. 253, 241, 391.

Задание 18. Найдите по алгоритму Евклида и методом разложения на простые множители НОК и НОД данных чисел.

Пример. 37730 и 46550.

Решение. Для разложения числа на простые множители будем испытывать последовательно простые числа в порядке их возрастания: 2, 3, 5, 7, 11, ..., p_n,... на тот факт, не является ли испытуемое простое число делителем данного числа а.

37730 делится на простое число 2, частное равно 18865. Полученное число 18865 не делится на 2, на 3, но делится на 5, частное равно 3773.

Полученное число 3773 не делится на 5, но делится на 7, частное равно 539.

Полученное число 539 опять делится на 7, частное равно 77.

Число 77 вновь делится на 7, частное равно 11, 11 - простое число.

Указанный процесс удобнее записать так:

37730 18865 3773 539 77 11 1

2 5 7 7 7 11

377730 = 2·5·73·11

Аналогично:

46550 23275 4655 931 133 19 1

2 5 5 7 7 19 46550 = 2·52·72·19

Итак, мы нашли каноническое разложение данных чисел: 377730 = 2 · 5 · 7³ ·11, 46550 = 2 · 5² · 7² ·19.

Чтобы найти НОД данных чисел, нужно вычислить произведение общих простых множителей с наименьшими показателями, с которыми они входят в разложения.

НОД(377730, 46550) = 2 · 5 · 7² = 490.

Чтобы найти НОК данных чисел, нужно вычислить произведение всех простых множителей с наибольшими показателями, с которыми они входят в разложения.

НОД(377730, 46550) = 2 · 5² · 7³·11·19 = 3584350.

Алгоритм Евклида.

Если а разделить с остатком на b  0, затем разделить с остатком b на полученный остаток, затем разделить с остатком первый остаток на второй остаток и т. д., то последний, отличный от нуля остаток, равен наибольшему общему делителю чисел а и b.

_46550 37730

37730 1

_37730 __ 8820

35280 4

_ 8820 _2450

7350 3

_2450 _1470

1470 1

_1470 ___980

_980 1

_980 ___490 - НОД

_980 2

0

НОД (46550, 37730) = 490

Для нахождения наименьшего общего кратного данных чисел воспользуемся теоремой о связи наименьшего общего кратного двух чисел с их наибольшим общим делителем.

НОК (а, b) =

НОК (37730, 46550) =

Варианты.

1. 44064, 37128;

2. 21125, 11560;

3. 18084, 290763;

4. 127008, 90552;

5. 42588, 19305;

6. 49005, 78125;

7. 41382, 103818;

8. 59584, 58482;

9. 41472, 35100;

10. 11340, 37800.

Задание 19. Решите задачу.

Пример. Имеется 56 белых гвоздик, 28 красных и 168 розовых. Какое наибольшее число одинаковых букетов можно сделать из этих цветов?

Решение. Все букеты должны содержать одинаковые количества белых, красных и розовых гвоздик. Следовательно, числа 56, 28 и 168 должны делиться на одно и то же число (число букетов), а так как число букетов должно быть наибольшим, то из всех делителей надо взять наибольший. Таким образом, чтобы определить какое наибольшее число одинаковых букетов можно сделать из всех цветов, надо найти наибольший общий делитель чисел 56, 28 и 168.

56 28 14 7 1

2 2 2 7

28 14 7 1

2 2 7

168 84 42 21 7 1

2 2 2 3 7

НОД (56, 28, 168) =28

Ответ: из всех цветов можно сделать 28 одинаковых букетов.

Варианты.

1. В три магазина поступили яблоки в одинаковых ящиках. В первый магазин доставили 1800 кг яблок, во второй – 4848 кг, в третий – 2520 кг. Сколько ящиков с яблоками доставили в каждый магазин, если ящики были максимально возможной массы?

2. Из 156 желтых, 234 белых и 390 красных роз сделали букеты в возможно большем числе так, что во всех букетах было поровну каждого в отдельности вида роз. Сколько стоил каждый букет, если желтая роза стоила 20 руб., белая – 15 руб., красная – 10 руб.?

3. Для поездки за город работникам завода выделено несколько автобусов с одинаковым числом мест в каждом автобусе. 424 человека поехали в лес, а 477 – на озеро. Все места в автобусах были заняты, и ни одного человека не осталось без места. Сколько автобусов было выделено и сколько пассажиров было в каждом автобусе?

4. Для детских подарков куплено 78 плиток шоколада, 156 пряников, 52 пачки печенья, 104 апельсина, 130 яблок. Какое наибольшее число одинаковых детских подарков можно приготовить из данных предметов?

5. Вдоль дороги от пункта А поставлены столбы через каждые 45 м. Эти столбы решили заменить другими, поставив их на расстоянии 60 м друг от друга. Найдите расстояние от пункта А до ближайшего столба, который будет стоять на месте старого.

6. В учебном году каждый ученик в классе получил комплект тетрадей в клетку и линейку. Во все комплекты вместе входило 232 тетради в клетку и 208 тетрадей в линейку. Сколько тетрадей в клетку и сколько тетрадей в линейку получил каждый ученик?

7. На нефтебазу прибыло 3 состава с нефтью: в первом составе было 360 т нефти, во втором – 432 т, в третьем – 792 т. Сколько цистерн с нефтью в каждом составе, если в каждой цистерне было одинаковое число тонн нефти, наибольшее из возможных?

8. В портовом городе начинаются три теплоходных рейса, первый из которых длится 15 суток, второй – 20 суток, а третий – 12 суток. Вернувшись в порт, теплоходы в этот же день отправляются в рейс. Сегодня из порта вышли теплоходы по всем маршрутам. Через сколько суток они впервые вместе уйдут в плавание?

9. Имеется 36 синих, 48 красных, 60 желтых и 84 белых листов бумаги. Какое наибольшее число комплектов можно сделать их этих листов, если в каждом комплекте должно быть одинаковое число листов каждого цвета?

10. Отец и сын решили измерить расстояние между двумя деревьями, для чего прошли одновременно от одного дерева до другого. Длина шага отца – 70 см, сына – 56 см. найдите расстояние между этими деревьями, если известно, что следы совпали в точности 10 раз.

Задание 20. Решите задачу арифметическим способом.

Варианты.

1. а) Школьники ехали на экскурсию в трех автобусах. Всего 80 человек. Во втором автобусе на 2 человека больше, чем в первом, а в третьем на 4 человека больше, чем во втором. Сколько человек ехало в каждом автобусе?

б) За 5 кг пряников и 3 кг печенья заплатили 102 рубля. А за 2 кг пряников и 4 кг печенья заплатили 80 рублей. Сколько стоит 1 кг пряников и 1 кг печенья?

2. а) Если около каждого дома посадить по 9 деревьев, то не хватит 100 деревьев. А если около каждого дома посадить по 5 деревьев, то останется 20 деревьев. Сколько домов?

б) Саша измерял ширину клумбы. Она получилась на 16 см больше роста мальчика, и на 12 см меньше роста его сестры. Найдите рост Саши, если рост его сестры 1м 15см.

3. а) Через мост прошло 40 легковых автомобилей и велосипедов, а всего 100 колес. Сколько прошло за день автомобилей?

б) На двух кустах сидело 25 воробьев. После того как с первого куста перелетело на второй 5 воробьев, а со второго улетело 7 воробьев, то на первом кусте осталось вдвое больше воробьев, чем на втором. Сколько воробьев было на каждом кусте первоначально?

4. а) В двух кусках одинаковое количество ткани. После того как от одного куска отрезали 18 м, а от другого – 25 м, в первом куске осталось вдвое больше ткани, чем во втором. Сколько метров ткани в каждом куске?

б) 12 семитонных и пятитонных грузовиков вывезли за один рейс 70 т земли. Сколько работало на вывозе земли пятитонных и сколько семитонных грузовиков?

5. а) В первой корзине яблок в 3 раза больше, чем во второй. Когда в первую корзину добавили еще 17 яблок, то там стало на 53 яблока больше, чем во второй корзине. Сколько яблок было в каждой корзине первоначально?

б) Бронза содержит 41 часть меди, 8 частей олова и 1 часть цинка. Какова масса куска бронзы, в котором цинка на 1кг 484г меньше, чем олова?

6. а) В колхозе собрано пшеницы, ржи и ячменя 3150 т. Пшеницы собрано в 4 раза больше, чем ржи, а ячменя – вдвое меньше, чем пшеницы. Сколько собрано отдельно пшеницы, ржи и ячменя?

б) За 3 дня на стройке было уложено 29300 кирпичей. Во второй день уложено на 1100 штук больше, чем в первый, а в третий – на 1500 штук больше, чем в первые дня вместе. Сколько кирпичей уложено в каждый день?

7. а) Для детского сада куплено 36 трехколесных и двухколесных велосипедов. У этих велосипедов 93 колеса. Сколько трехколесных и сколько двухколесных велосипедов было куплено?

б) Мальчик и девочка собирали грибы. Мальчик собрал грибов в 4 раза больше и на 9 грибов больше, чем девочка. Сколько грибов собрал каждый?

8. а) 4 пальто стоят столько же, сколько 6 костюмов. Костюм дешевле пальто на 20 рублей. Сколько стоит пальто и сколько стоит костюм?

б) Столовая на несколько дней запасла муки. Если расходовать по 8 кг в день, то не хватит 4 кг; если же расходовать по 7 кг в день, то останется 12 кг муки. На сколько дней завезено муки?

9. а) Если из первой цистерны перекачать во вторую 120 т нефти, то в обеих цистернах нефти станет поровну. Если же из второй цистерны перекачать в первую 120 т, то в первой станет в 4 раза больше нефти, чем осталось бы во второй. Сколько тонн нефти было в каждой цистерне?

б) Масса 5 ящиков болтов и 6 ящиков гвоздей составляет 228 кг, а масса 3 ящиков болтов и 7 ящиков гвоздей – 198 кг. Какова масса ящика с гвоздями и ящика с болтами?

10. а) В одном куске в 3 раза больше полотна, чем в другом. Когда от большего отрезали 45 м полотна, а от меньшего - 5 м, то полотна в кусках стало поровну. Сколько метров полотна было в каждом куске первоначально?

б) Три подружки договорились к праздничному столу купить 12 пирожных. Первая купила 5 пирожных, а вторая 7. Третья же принесла 12 рублей. Как должны поделить эти деньги девочки?