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

 

Отношение делимости. Признаки делимости. Простые и составные числа. Кратные и делители. Наименьшее общее кратное, наибольший общий делитель, их свойства. Взаимно простые числа. Признак делимости на составное число.

Литература: [1] с. 290-306, [2] с. 135-142, [3] с. 150-179, [4] с. 69-78, [5] с. 143-151, [6] с.107-122, [7] с. 159-171.

 

ТЕОРИЯ ДЕЛИМОСТИ НАТУРАЛЬНЫХ ЧИСЕЛ

(задания I уровня)

 

1А. Среди следующих предложений укажите истинные и ложные:

а) 156 = 2²・3・13; б) числа 124 и 25 являются взаимно простыми;

в) число 199 – составное.

 

1Б. Подтвердите истинность либо опровергните высказывания:

а) если сумма делится на число а, то каждое слагаемое делится на а;

б) если число кратно 4, то оно кратно 2.

 

2А. Среди следующих предложений укажите истинные и ложные:

а) число 543 – простое; б) НОД (48, 60) = 12; в) 810 = 2²・3⁴・5.

 

2Б. Подтвердите истинность либо опровергните высказывания:

а) если произведение делится на число а, то хотя бы один множитель делится на а; б) числа 9 и 24 – взаимно простые.

 

3А. Среди следующих предложений укажите истинные и ложные:

а) число 159 – простое; б) НОК (45, 30) = 180; в) 216 = 2³・3³.

 

3Б. Подтвердите истинность либо опровергните высказывания:

а) существует наибольшее простое число;

б) каждое число, кратное 3, является кратным 9.

 

4А. Среди следующих предложений укажите истинные и ложные:

а) 144 = 2⁴・3²; б) НОД (12, 72) = 72; в) число 224 кратно 7.

 

4Б. Подтвердите истинность либо опровергните высказывания:

а) существует наибольшее составное число; б) числа 12 и 16 взаимно простые.

 

5А. Среди следующих предложений укажите истинные и ложные:

а) 1440 = 2⁴・3²・5; б) число 437 – простое;

в) число 2204 является кратным числа 48.

 

5Б. Подтвердите истинность либо опровергните высказывания:

а) НОД (а, в) = 1, если числа а и в – взаимно простые;

б) число 9 имеет только два делителя.

 

0А. Среди следующих предложений укажите истинные и ложные:

а) число 189 – составное; б) 1620 = 2²・3⁴・5;

в) число 18 является кратным числа 54.

 

Решение:

а) составным числом называют число, которое имеет более двух делителей. Найдем каноническое разложение данного числа 189:

189	3	189 = 33・7; число 189 имеет 5 делителей {1;3;9;7;189} Значит, 189 – составное число.
63	3
21	3
7	7
1

б) Представим число 1620 в каноническом виде:

1620	2
810	2
405	3
135	3
45	3
15	3
5	5
1

Следовательно, 1620 = 2²・3⁴・5.

в) Представим числа 54 и 18 в каноническом виде:

54	2		18	2
27	3	9	3
9	3	3	3
3	3	1
1

54 = 2・3³; 18 = 2・3²; НОД (54; 18) = 2・3² = 18. Число 18 является делителем числа 54, а не кратным.

 

0Б. Подтвердите истинность либо опровергните высказывания:

а) НОК (а, в) = а × в, если числа а и в взаимно простые;

б) если запись числа оканчивается цифрой 8, то оно кратно 4.

Решение:

а) Данное высказывание истинно. Т.к. если числа а и в – взаимно простые, то они имеют только один общий делитель – 1. Значит, наименьшим общим кратным этих чисел будет их произведение.

б) Данное высказывание ложно. Число делится на 4, если две последних цифры образуют число, которое делится на 4.

 

ТЕОРИЯ ДЕЛИМОСТИ НАТУРАЛЬНЫХ ЧИСЕЛ

(задания II уровня)

 

1А. Найдите каноническое разложение чисел: а) 78; б) 504; в) 2748.

 

1Б. Не выполняя арифметических действий, выясните, делятся ли заданные числовые выражения на указанные числа и объясните, почему:

а) 25 · 321 + 456018 на 3; б) 134 · 270 на 4; в) 150 + 225 на 15.

 

2А. Найдите каноническое разложение чисел: а) 96; б) 810; в) 2061.

 

2Б. Не выполняя арифметических действий, выясните, делятся ли заданные числовые выражения на указанные числа и объясните, почему:

а) 229 + 631 на 7; б) 16・23・124 на 3; в) 15・749 + 16 на 6.

 

3А. Найдите каноническое разложение чисел: а) 80; б) 675; в) 4368.

 

3Б. Не выполняя арифметических действий, выясните, делятся ли заданные числовые выражения на указанные числа и объясните, почему:

а) 123・749 на 7; б) 225 + 130 на 5; в) 540・8310 + 750 на 15.

 

4А. Найдите каноническое разложение чисел: а) 84; б) 162; в) 3744.

 

4Б. Не выполняя арифметических действий, выясните, делятся ли заданные числовые выражения на указанные числа и объясните, почему:

а) 2808 + 6500 + 1875 на 15; б) 123・201・44 на 18;

в) 72・29・47 + 2304 на 9.

 

5А. Найдите каноническое разложение чисел: а) 56; б) 270; в) 1124.

 

5Б. Не выполняя арифметических действий, выясните, делятся ли заданные числовые выражения на указанные числа и объясните, почему:

а) 2512 + 127 на 3; б) 134・270 на 5; в) 123・207 + 36 на 18.

 

0А. Найдите каноническое разложение чисел: а) 81; б) 225; в) 94180.

Решение:

а)	81	3	б)	225	3	в)	94180	2
27	3	75	3	47090	2
9	3	25	5	23545	5
3	3	5	5	4709	17
1		1		277	277
				1

81 = 3⁴ 225 = 3² · 5² 94180 = 2² · 5 · 17 · 277

Проверим, что 277 – простое число, по признаку простого числа: » 17; 2,3,5, 7, 11, 13, 17 – простые числа, не превосходящие 17. Проверяем: - по признаку делимости на 2; - по признаку делимости на 3; - по признаку делимости на 5; ; - по признаку делимости на 11; ; .Значит, 277 делится только на 1 и на 277.

0Б. Не выполняя арифметических действий, выясните, делятся ли заданные числовые выражения на указанные числа и объясните, почему:

а) 30861 + 45063 + 2304 на 9;

б) 22050 + 2380 + 6175 на 15;

в) 540・127 на 6.

Решение:

а) Воспользуемся теоремой о том, что если каждое слагаемое суммы делится на число, то и сумма делится на это число, и признаком делимости на 9: число делится на 9, если сумма цифр в записи числа делится на 9.

30861 M 9, т. к. 3 + 0 + 8 + 6 + 1 = 18, 18 M 9;

45063 M 9, т. к. 4 + 5 + 0 + 6 + 3 = 18, 18 M 9;

2304 M 9, т. к. 2 + 3 + 0 + 4 = 9, 9 M 9.

Каждое слагаемое данной суммы делится на 9.

Значит, сумма (30861 + 45063 + 2304) M 9.

б) Признак делимости на составное число: число делится на 15, если оно делится на 5 и на 3.

22050 M 15, поскольку 22050 M 5 (т.к. число оканчивается на 0), 22050 M 3 (т.к. 2 + 2 + 5 = 9; 9 M 3)

, поскольку 2380 M 5 (т.к. число оканчивается на 0), (т.к., 2 + 3 + 8 = 13; )

, поскольку 6175 M 5 (т.к. число оканчивается на 5), (т.к. 6 + 1 + 7 + 5 = 19; )

Получим, что два слагаемых суммы не делятся на 15, поэтому сумма 22050 + 2380 + 6175 может делиться, а может и не делиться на 15.

в) Произведение делится на число, если хотя бы один из множителей делится на число. Число делится на 6, если оно делится на 2 и на 3.

540 M 6, т. к. 540 M 3 (5 + 4 = 9, 9 M 3) и 540 M 2 (заканчивается нулем). Значит, (540・127) M 6.

 

 

ТЕОРИЯ ДЕЛИМОСТИ НАТУРАЛЬНЫХ ЧИСЕЛ

(задания III уровня)

 

 

1А. Найдите двумя способами НОД и НОК чисел: 1960 и 588.

 

1Б. Определите, какие из чисел являются простыми, а какие – составными: а) 209; б) 331; в) 389.

 

2А. Найдите двумя способами НОД и НОК чисел: 3960 и 4375.

 

2Б. Определите, какие из чисел являются простыми, а какие – составными: а) 223; б) 377; в) 437.

 

3А. Найдите двумя способами НОД и НОК чисел: 536 и 1024.

 

3Б. Определите, какие из чисел являются простыми, а какие – составными: а) 299; б) 1227; в) 139.

 

4А. Найдите двумя способами НОД и НОК чисел: 2416 и 604.

 

4Б. Определите, какие из чисел являются простыми, а какие – составными: а) 187; б) 571; в) 395.

 

5А. Найдите двумя способами НОД и НОК чисел: 540 и 1512.

 

5Б. Определите, какие из чисел являются простыми, а какие – составными: а) 463; б) 189; в) 183.

 

0А. Найдите двумя способами НОД и НОК чисел: 192 и 1620.

Решение:

1-ый способ: с помощью канонического разложения:

192	2	1620	2	192 = 26 · 3; 1620 = 22 · 34 · 5; НОД (192; 1620) = 22 · 3 = 4 · 3 = 12; НОК (192; 1620) = 26 · 3 · 5 = 64 · 81 · 5 = 25920.
96	2	810	2
48	2	405	3
24	2	135	3
12	2	45	3
6	2	15	3
3	3	5	5
1		1

2-ой способ: с использованием алгоритма Евклида

–	1620 1536	192
8
–	192 168	84
2
–	84 72	24
3
–	24 24	12
2
	0

НОД (192; 1620) = 12

НОК (192; 1620) = = = 25920.

 

0Б. Определите, какие из чисел являются простыми, а какие – составными: а) 829; б) 703; в) 481.

Решение:

а) Воспользуемся признаком простого числа. Если n Î N, n > 1 не делится ни на одно простое число, не превосходящее , то n – простое число.

» 29; 2, 3, 5, 7, 11, 13, 17, 19, 23 – простые числа, не превосходящие .

, т. к. последняя цифра в записи числа не делится на 2;

, т. к. сумма цифр в записи числа не делится на 3 (8+2+9 = 19, );

, т. к. последняя цифра в записи числа не 5 и не 0;

, т. к. 829: 7 = 118 (ост. 2);

, т. к. сумма цифр, занимающих четные места, не равна сумме цифр, занимающих нечетные места, либо эти суммы отличаются на число, делящееся на 11 (8 + 9 ¹ 2).

, т. к. 829: 13 = 63 (ост. 10);

, т. к. 829: 17 = 48 (ост. 13);

, т. к. 829: 19 = 43 (ост. 12);

, т. к. 829: 23 = 36 (ост. 1).

Значит, 829 – простое число.

б) Воспользуемся признаком простого числа.

» 27; 2, 3, 5, 7, 11, 13, 17, 19, 23 – простые числа, не превосходящие .

, т. к. последняя цифра в записи числа не делится на 2;

, т. к. сумма цифр в записи числа не делится на 3;

, т. к. последняя цифра в записи числа не 5 и не 0;

, т. к. 703: 7 = 100 (ост. 3);

, т. к. сумма цифр, занимающих четные места, не равна сумме цифр, занимающих нечетные места, либо эти суммы отличаются на число, делящееся на 11;

, т. к. 703: 13 = 54 (ост. 1);

, т. к. 703: 17 = 41 (ост. 6);

703 M 19, т. к. 703: 19 = 37.

Значит, 703 – составное число.

в) Воспользуемся признаком простого числа.

» 22; 2, 3, 5, 7, 11, 13, 17, 19– простые числа, не превосходящие .

, т. к. последняя цифра в записи числа не делится на 2;

, т. к. сумма цифр в записи числа не делится на 3;

, т. к. последняя цифра в записи числа не 0 и не 5;

, т. к. 481: 7 = 68 (5 ост.);

, т. к. сумма цифр, занимающих четные места, не равна сумме цифр, занимающих нечетные места, либо эти суммы отличаются на число, делящееся на 11;

, т. к. 481: 13 = 39 (4 ост.);

, т. к. 481: 17 = 27 (2 ост.);

, т. к. 481: 19 = 25 (6 ост.).

Значит, 481 – простое число.

ТЕОРИЯ ДЕЛИМОСТИ НАТУРАЛЬНЫХ ЧИСЕЛ

(задания IV уровня)

 

1А. Докажите с помощью метода математической индукции, что для "nÎ N (n³ + 5n) M 6.

 

1Б. Найдите числа а и в, если НОД (а, в) = 5, НОК (а, в) = 105.

 

2А. Докажите с помощью метода математической индукции, что для "nÎ N (4ⁿ – 1) M 3.

 

2Б. Найдите числа а и в, если НОД (а, в) = 7, а・в = 294.

 

3А. Докажите с помощью метода математической индукции, что для "nÎ N (6²ⁿ – 1) M 35.

 

3Б. Найдите числа а и в, если НОК (а, в) = 75, а・в = 375.

 

4А. Докажите с помощью метода математической индукции, что для "nÎ N (n⁵ – n) M 5.

 

4Б. Найдите числа а и в, если НОД (а, в) = 4, а:в = 19:15.

 

5А. Докажите с помощью метода математической индукции, что для "nÎ N (n³ + 11n) M 6.

 

5Б. Найдите числа а и в, если а・в = 25200, НОК (а, в) = 12600.

 

 

ТЕОРИЯ ДЕЛИМОСТИ НАТУРАЛЬНЫХ ЧИСЕЛ

(задания V уровня)

 

1А. Докажите двумя способами, что если n Î N, то Î N

 

1Б. Мимо станции железной дороги проходят один за другим три поезда: в первом 418 пассажиров, во втором – 494, в третьем – 456. сколько пассажирских вагонов в каждом поезде, если известно, что в каждом вагоне находится по одинаковому числу пассажиров и их число наибольшее из возможных?

2А. Докажите двумя способами, что если n Î N, то Î N

 

2Б. Сколько яиц лежит в корзине, если при раскладывании кучками по 15, по 20 и по 24 одно яйцо остается лишним, а при раскладывании по 11 не остается ни одного лишнего яйца?

 

3А. Докажите двумя способами, что если n Î N, то Î N

 

3Б. Найдите наименьшее натуральное число, которое при делении на 2, 3, 4, 5, 6, 8 дает остаток 1 и без остатка делится на 7.

 

4А. Докажите двумя способами, что если n Î N, то Î N

 

4Б. И 156 желтых, 234 белых и 390 красных роз составили букеты так, что в каждом букете было одинаковое количество каждого (в отдельности) цвета роз. Таких букетов составили максимально возможное количество. Сколько было букетов и сколько роз в каждом букете?

 

5А. Докажите двумя способами, что если n Î N, то Î N

 

5Б. В некоторый момент времени планеты Венера и Меркурий занимают определенное положение относительно неподвижных звезд. Через сколько суток обе планеты будут находиться вновь в том же положении относительно звезд, если известно, что Меркурий делает один полный оборот вокруг Солнца за 88 суток, а Венера – за 225 суток?