Бардушкин В.В., Кожухов И.Б., Прокофьев А.А., Фадеичева Т.П. Основы теории делимости чисел. Решение уравнений в целых числах

Упражнения

5.1. Найдите наименьшее общее кратное чисел:

1)

645 и 381; 2) 846 и 246; 3) 5338 и 11618.

Ответ: 1)

81915; 2) 34686; 3) 197506.

5.2.* Приведите к общему знаменателю дроби

21120

111

и

30720

1237

.

Ответ:

337920

1776

и

337920

13607

.

5.3.* Сложите дроби

192

7

и

1620

187

.

Ответ:

25920

3937

.

5.4.* Найдите наименьшее натуральное число, бóльшее двух и дающее

при делении на 2, 3, 4, 5, 6 остаток, равный 1.

Ответ:

61.

5.5. Для каких двух различных натуральных чисел в пределах от

1 до

1000 их наименьшее общее кратное является наибольшим из всех воз-

можных

?

Ответ:

999 и 1000.

5.6. Натуральное число при делении на

2, 3, 4, 5, 6 и 7 дает в остатке

соответственно

1, 2, 3, 4, 5 и 6. Найдите:

1) наименьшее такое число;

2) общий вид таких чисел.

Ответ: 1)

419 ; 2) 1420

−

n (

∈

п N ).

51

5.7. Натуральное число при делении на

4, 5 и 6 дает в остатке соответ-

ственно

3, 4 и 5, а на 7 делится без остатка. Найдите:

3) наименьшее такое число;

4) общий вид таких чисел.

Ответ: 1)

119 ; 2) 119420

+

n (

∈

п N

0

).

5.8. Найдите наименьшее общее кратное натуральных чисел

п и 3

+

n .

Ответ:

, если п не делится на 3; )3( +nn

)3(

3

1

+nn , если п делится на 3.

5.9.* Чему может быть равно наименьшее общее кратное трех чисел

(где N )? 2,1, ++ ппп ∈п

5.10. Чему может быть равно наименьшее общее кратное четырех чисел

(где 3,2,1, +++ nппп

∈

п N )?

Ответ:

)3)(2)(1(5.0 ++

+

nnnn , если п не делится на 3;

)3)(2)(1(

6

1

+++ nnnn , если п делится на 3.

5.11. Среди первых ста натуральных чисел найдите три различных чис-

ла, наименьшее общее кратное которых – наибольшее из всех возмож-

ных

?

Ответ:

97, 99 и 100.

5.12. Три теплохода заходят в порт после каждого рейса. Первый тепло-

ход совершает рейс за

4 дня, второй – за 6, третий – за 9. однажды они

встретились в порту все вместе. Через какое наименьшее число дней

они снова встретятся в порту все вместе

?

Ответ: через

36 дней.

5.13. На гранях кубиков нужно написать буквы русского алфавита, по

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

52

для того, чтобы все

33 буквы алфавита были написаны одинаковое ко-

личество раз и все грани кубиков были заполнены

?

Ответ:

11.

5.14. Отец и сын шли по занесенной снегом дороге друг за другом. Дли-

на шага отца –

80 см, сына – 60 см. Их шаги совпали 601 раз, в том

числе в самом начале и в конце пути. Какое расстояние они прошли

?

Ответ:

1 км 440 м.

5.15. Два школьника вышли одновременно из пункта

А в пункт В и от-

правились друг за другом по занесенной снегом тропинке. Шаг одного

из них равен

75 см, другого – 65 см. В первый раз их шаги совпали че-

рез

18 секунд после начала движения, а после 10 минут движения их

шаги совпали впервые в пункте

В. Найдите расстояние АВ.

Ответ:

331,5 м.

5.16.* Докажите, что наименьшее общее кратное натуральных чисел

совпадает с наименьшим общим кратным чисел

.

пп 2,12,...,2,1 −

ппп 2,...,2,1 ++

5.17.* Найдите натуральные числа

а и b, если известно, что они не де-

лятся друг на друга и

, 6),( =bаНОД 90),(

=

bаНОК .

Ответ:

18 и 30 или 30 и 18.

5.18. Найдите все такие натуральные числа

а и b, где bа

≤

, что

и . 840),( =bаНОК 15),( =bаНОД

Ответ:

, или 15=a 840=b 105

=

a , 120

=

b .

5.19. Найдите два натуральных числа, зная, что их разность равна

66, а

наименьшее общее кратное равно

360.

Ответ:

90 и 24.

53

§ 6. Каноническое разложение натуральных чисел

Канонические разложения натуральных чисел удобно использовать

для выяснения соотношений делимости. Добавляя при необходимости

сомножители с нулевыми показателями степени в канонические разло-

жения, всегда можно конечное число любых натуральных чисел пред-

ставить в виде произведения одних и тех же различных простых чисел с

целыми неотрицательными показателями степени.

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

простых чисел с целыми неотрицательными показателями степени сле-

дующие числа:

, , .

35

1352 ⋅⋅=а

42

73 ⋅=b

23

175 ⋅=c

Решение.

030105

17137532 ⋅⋅⋅⋅⋅=а ,

004020

17137532 ⋅⋅⋅⋅⋅=b ,

200300

17137532 ⋅⋅⋅⋅⋅=c .

Теорема 9. Пусть даны натуральные числа:

s

k

s

kk

pppт ⋅⋅⋅= ...

21

, ,

s

l

s

ll

pppn ⋅⋅⋅= ...

21

где

– различные простые числа, а показатели степени

и – целые неотрицательные. Для того, чтобы число т делилось на

число

п, необходимо и достаточно, чтобы для всех

.

s

ррр ,,,

21

…

i

k

i

l

ii

lk ≥

si ,...,2,1=

Доказательство.

Ö Если

х

пт = , где

∈

х

N, то всякий простой

делитель числа

х является одним из чисел . Поэтому х

может быть представлено в виде

, где .

Следовательно,

.

s

ррр ,,,

21

…

s

t

s

tt

pppх ⋅⋅⋅= ...

21

0≥

i

t

sss

tl

s

tltl

k

s

kk

pppppp

+

++

⋅⋅⋅=⋅⋅⋅ ......

221121

2121

Благодаря единственности разложения натурального числа на про-

стые множители имеем , а значит, для всех

.

iii

tlk +=

ii

lk ≥

si ,...,2,1=

54

Õ Если для всех

ii

lk ≥ si ,...,2,1

=

, то для натурального числа

ss

lk

s

lklk

pppх

−

−−

⋅⋅⋅= ...

2211

21

,

очевидно, имеет место равенство

х

пт = 

Следствие 1. Пусть натуральное число т представлено в каноническом

виде:

s

k

s

kk

pppт ⋅⋅⋅= ...

21

.

Тогда все натуральные делители

т представляют собой всевозможные

числа вида:

s

l

s

ll

ppp ⋅⋅⋅ ...

21

,

где

для всех . При этом всякий натуральный

делитель числа

т однозначно задается выражением указанного вида.

ii

kl ≤≤0 si ,...,2,1=

Пример. Число делится на число

. Частное от деления 82280 на 170 равно

.

17115282280

23

⋅⋅⋅=

1752170 ⋅⋅=

484112

22

=⋅

Условие делимости, доказанное в предыдущей теореме 9, дает но-

вый способ нахождения наибольшего общего делителя и наименьшего

общего кратного нескольких чисел. При этом достаточно рассматривать

лишь натуральные числа.

Следствие 2. Пусть натуральные числа представлены

в каноническом виде:

r

mmm ,,,

21

…

s

k

s

kk

pppт

11211

...

211

⋅⋅⋅=

,

s

k

s

kk

pppт

22221

...

212

⋅⋅⋅=

,

…………………………………...

rsrr

k

s

kk

r

pppт ⋅⋅⋅= ...

21

,

где

– различные простые числа, а показатели степени –

целые неотрицательные. Тогда:

s

ррр ,,,

21

…

55

1) ,

s

u

s

uu

r

pppтттНОД ⋅⋅⋅= ...),,,(

21

…

где

для .

{}

riiii

kkku ,...,,min

21

= si ,...,2,1=

2)

,

s

v

s

vv

r

pppтттНОК ⋅⋅⋅= ...),,,(

21

…

где

для .

{}

riiii

kkkv ,...,,max

21

= si ,...,2,1=

В частности, числа

взаимно просты тогда и толь-

ко тогда, когда при любом

одно из чисел

равно нулю, т.е. когда у данных чисел

нет общих простых делителей.

r

mmm ,,,

21

…

si ,...,2,1=

riii

kkk ,,,

21

…

r

mmm ,,,

21

…

Пример. Найдите

, используя

канонические разложения данных чисел.

)3360,3960,91476(НОД

Решение. Находим канонические разложения:

91476 2 3960 2 3360 2

45738 2 1980 2 1680 2

22869 3 990 2 840 2

7623 3 495 3 420 2

2541 3 165 3 210 2

847 7 55 5 105 3

121 11 11 11 35 5

11 11 1 7 7

1 1

232

1173291476 ⋅⋅⋅= , , . 115323960

23

⋅⋅⋅= 75323360

5

⋅⋅⋅=

Следовательно,

12117532)3360,3960,91476(

00012

=⋅⋅⋅⋅=НОД . Ответ: 12.

Пример. Найдите , используя канонические

разложения данных чисел.

)91,252,462(НОК

Решение. Находим канонические разложения:

462 2 252 2 91 7

231 3 126 2 13 13

77 7 63 3 1

11 11 21 3

1 7 7

1

56

11732462 ⋅⋅⋅= , , 732252

22

⋅⋅= 13791

⋅

= .

Следовательно,

360361311732)91,252,462(

11122

=⋅⋅⋅⋅=НОК .

Ответ:

36036.

Покажем теперь, что для любых натуральных чисел

имеет место делимость произведения

на произведение

r

mmm ,,,

21

… )2( ≥r

r

mmm ⋅⋅⋅ …

21

),...,,(),,,(

2121 rr

тттНОКmmmНОД ⋅… ,

и поэтому

rrr

ттттттНОКmmmНОД

⋅

≤

⋅ ...),...,,(),,,(

212121

… .

Действительно, едставим чи

m ,

1

ниче-

ском виде:

пр сла

,,

2

… в кано

r

mm

s

k

s

kk

pppт

11211

...

211

⋅⋅⋅=

,

s

k

s

kk

pppт

22221

...

212

⋅⋅⋅=

,

…………………………………...

rsrr

k

s

kk

r

pppт ⋅⋅⋅= ...

21

,

где

– различные простые числа, а показатели степени –

целые неотрицательные. Справедливость данного утверждения следует

из того, что сумма наибольшего и наименьшего из показателей степеней

каждого простого множителя в разложениях данных чисел не превосхо-

дит суммы всех показателей степеней этого простого множителя.

s

ррр ,,,

21

…

Заметим, что при

2=

r

получается равенство этих чисел, т.е. дру-

гим способом доказана справедливость известного соотношения:

212121

),(),( ттттНОКmmНОД

⋅

=

⋅ .

Легко видеть, что при

2>

r

можно получить строгое неравенство.

Например,

36632661)6,3,2()6,3,2(

=

⋅

<

=

⋅=⋅ НОКНОД .

Тем самым показано, что результат

212121

),(),( ттттНОКmmНОД

⋅

=

⋅

не может быть обобщен на бóльшее, чем два, количество чисел.

57

Рассмотрим теперь некоторые другие приложения основной тео-

ремы арифметики. Для любого натурального п обозначим через )(n

τ

количество всех натуральных делителей

п, а через )(n

σ

– их сумму.

Таким образом,

, .

∑

=τ

nd

n

|

1)(

∑

=σ

nd

dn

|

)(

Теорема 10. Пусть число п задано в канонической форме:

. Тогда

k

pppn

α

αα

⋅⋅⋅= ...

21

∏

=

+α=τ

k

i

n

1

)1()(

,

∏

=

+α

−

=σ

k

i

p

n

i

1

)(

.

Доказательство. Каждый натуральный делитель

п единственным об-

разом представляется в виде

, где

k

ppp

β

ββ

⋅⋅⋅ ...

21

ii

α

≤

β

для всех

. Поэтому число натуральных делителей п равно количе-

ству всевозможных наборов

. Поскольку каждое

ki ,...,2,1=

),...,,(

21 k

βββ

i

β

может принимать

различных значений от 0 до 1+α

i i

α

, то число та-

ких наборов равно

)1(...)1()1(

21

+

α⋅⋅+α

⋅

+α

k

.

Таким образом, формула для

)(n

τ

доказана.

Для доказательства второй формулы заметим, что

1

−

+α

i

p

i

мож-

но записать как сумму членов геометрической прогрессии со знамена-

телем

:

i

p

∑

α

=β

βα

+α

=+++=

−

i

ii

i

iii

i

ppp

p

0

1

...1

1

.

Следовательно, раскрывая скобки, получим

k

i

kk

k

i

pppppp

p

β

ββ

βββ

α

=β

β

α

=β

β

α

=β

β

=

+α

⋅⋅⋅=⋅⋅⋅=

−

∑∑∑∑

∏

......

1

21

2

1

21

,...,,00

2

0

1

.

58

Последняя сумма в этой формуле есть сумма всех натуральных де-

лителей п, т.е.  )(nσ

Пример. Найдите число и сумму натуральных делителей

180.

Решение. Каноническое разложение имеет вид

. 532180

22

⋅⋅=

Следовательно,

18)11()12()12()180(

=

+

⋅+⋅

+

=τ ,

546

15

13

12

)180(

233

=

−

⋅

−

⋅

−

=σ

.

Пример. Найдите число вида

, если известно, что сумма всех его

натуральных делителей равна

403.

ml

32

Решение. Очевидно, что показатели

l и m не могут быть одновременно

равными

0. Если , то каноническая запись числа имеет вид

и, применяя формулу суммы всех натуральных делителей, получа-

ем равенство

. Отсюда , или

. Последнее уравнение не имеет решений при целых т,

т.к. число

269 простое. Если , то каноническая запись числа

имеет вид и потому , что также невозможно.

0=l

ml

32

m

3

403213

1

⋅=−

+m

8073

1

=

+m

26933

1

⋅=

+m

0=m

ml

32

l

2 40312

1

=−

+l

Таким образом,

, и – каноническая запись ис-

ходного числа. По формуле суммы всех натуральных делителей получа-

ем равенство

, или

(где, отметим, 2, 13 и 31 – простые

числа). Так как

и , то разложение на простые

множители

произведения этих чисел должно составляться из

соответствующих разложений сомножителей. Поскольку число

0>l 0>m

ml

32

4032)13()12(

11

⋅=−⋅−

++ ml

31132)13()12(

11

⋅⋅=−⋅−

++ ml

112

1

>−

+l

113

1

>−

+m

31132 ⋅⋅

12

1

−

+l

нечетно и равенства

и невозможны при

целых значениях

l, имеем и . Отсюда

1312

1

=−

+l

311312

1

⋅=−

+l

3112

1

=−

+l

2613

1

=−

+m

4

=

l

и

, а значит, искомое число есть . 2=m 14432

24

=⋅

Ответ:

. 14432

24

=⋅

59

При рассмотрении числовых функций важным является следующее

свойство.

Определение. Числовая функция

называется мультипликатив-

ной, если для любых взаимно простых чисел

а и b выполняется равен-

ство

)(nf

)()()( bfafbaf ⋅=

⋅

.

Пример. Докажем, что функции

и являются мультиплика-

тивными.

)(nτ )(nσ

Решение. Для любых взаимно простых натуральных чисел

а и b их ка-

нонические разложения имеют вид

s

k

s

kk

pppa ⋅⋅⋅= ...

21

, ,

r

l

r

ll

qqqb ⋅⋅⋅= ...

21

где ни одно из простых чисел

не совпадает ни с одним из простых

чисел

. В этом случае каноническое разложение произведения ab

имеет вид

i

p

j

q

r

s

l

r

llk

s

kk

qqqpppab ⋅⋅⋅⋅⋅⋅⋅= ......

2121

.

Согласно теореме 10 получаем:

)()()1...()1()1(...)1()(

11

ballkkab

rs

τ

⋅

τ

=

+

⋅+⋅

+

⋅⋅+=τ ,

)()(

1

...

1

...

1

)(

1

11

ba

q

p

ab

r

l

r

l

s

k

s

k

r

s

σ⋅σ=

−

⋅⋅

−

⋅

−

⋅⋅

−

=σ

+

.

С суммой делителей натурального числа связано одно интересное

понятие.

Определение. Натуральные числа

а, для которых aa 2)(

=

σ

, называ-

ются совершенными.

Иначе говоря, число

а совершенно, если сумма его собственных

(т.е. не равных

а) натуральных делителей равна а.

Понятие совершенного числа появилось в математике Древней

Греции. Древние греки знали четыре совершенных числа:

6, 28, 496 и

8128. В действительности, четные совершенные числа можно описать

следующим образом.

60

Бардушкин В.В., Кожухов И.Б., Прокофьев А.А., Фадеичева Т.П. Основы теории делимости чисел. Решение уравнений в целых числах

Подождите немного. Документ загружается.