Deza_Kotova_Sbornik_zadach_po_teorii_chisel

1. Докажите, что:

а) произведение двух последовательных целых чисел делится на 2; б) произведение четырех последовательных целых чисел делится на 4; в) произведение пяти последовательных целых чисел делится на 5;

r)произведение n последовательных целых чиселделится на n, n Е N.

2.Докажите, что для любого целого а:

3. Докажите, что:

а) разность четных степеней двух нечетных чисел делится на 4; б) сумма кубов двух последовательных нечетных чисел делится на 4; в) разность квадратов двух нечетных чисел делится на 8;

r)сумма кубов трех последовательных целых чисел делится на 3.

4.Докажите, что:

в) 2аЬ делится на 98, если а4 + Ь4 делится на 7; r) 3аЬ делится на 363, если а2 + Ь2 делится на 11.

задачu

1. Докажите, что n ·(n2 + 1) · (n2 + 4) делится на 5 при любом целом п.

2.Докажите, что целое число а не может быть квадратом целого числа, если число а - 5 делится на 9.

стых чисел бесконечно: предположив, что множество простых чисел конеч­

но, и что JID = {р1,р2, ••• ,pk} - все простые числа, он построил число Е = Р1 · Р2 · ... · Pk + 1 и рассмотрел простое число р, делящее Е. Легко

видеть, что число р не может совпадать ни с одним из чисел р1 , Р2, ... , Pk,

так как иначе р должно делить разность E-pi ·р2-.. "Pk = 1, что невозмож­

но. Таким образом, р - простое число, не попавшее в вышеприведенный

список, то есть множество простых чисел не может исчерпываться числа­

ми Р1,р2, · · · ,Pk·

Простейший метод нахождения всех простых чисел на данном интер­ вале был предложен греческим математиком Эратосфеном. Он называется решетом Эратосфена и состоит в следующем. Рассмотрим последователь­ ность 2, 3, 4, 5"" натуральных чисел, больших единицы. Так как 2 является

первым простым числом, р1 , вычеркнем из нашей последовательности все

числа, большие р1 и делящиеся на Р1, то есть, начиная с 2, каждое вто­ рое число таблицы - они заведомо составные. Первое из оставшихся

чисел 3 - второе простое число, Р2. Вычеркнем все числа, большие р2 и делящиеся на Р2, то есть, начиная с 3, каждое третье число таблицы.

· Первое из оставшихся чисел 5 - третье простое число, Рз, и т. д. Следуя

чает п-е простое число.

Существует много других возможностей определить, является ли дан­

ное натуральное число простым. Классический тест такого рода основы­

вается на следующем утверждении: если п является составным числом, то

оно имеет простой делитель р ~ .Jii,. Действительно, составное п обладает нетривиальным натуральным делителем а {/. {1, п}, то есть представимо

в виде п =а· Ь, 1 <а~ Ь < п. При этом а~ y'ri,, так как в противном случае мы получаем противоречие: поскольку а> .Jii, и Ь ~а, то Ь > .Jii,, откуда следует, что п = а· Ь > .Jii, ·.Jii, = п, то есть п > п. Посколь­

ку а - натуральное число, большее единицы, то оно обладает простым делителем р. При этом, с одной стороны, делитель р числа а является

делителем п, и, с другой стороны, р ~а~ .Jii,. Таким образом, мы на­

шли для составного числа п его простой делитель р, удовлетворяющий

условию р ~ .;п.

Представление п = р~' · ... · р~· натурального числа п, большего

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

чисел р1 , ••• , р8 называется каноническим.

Фундаментальная теорема арифметики утверждает, что любое натураль­

ное число, большее 1, можно, причем единственным образом (с точностью до порядка сомножителей), представить в виде произведения простых чисел.

примеры решения задач

1. Разложите на простые множители число 495; число 101.

Реwение. Для разложения числа 495 на простые множители прове­

рим делимость данного числа на простые числа, не превосходящие

V495: 2, 3, 5, 7, 11, 13, 17 и 19. Легко видеть, что число 495 не делится

на 2, но делится на 3: 495 = 3 · 165. Далее, число 165 делится на 3: 165 = 3 · 55. В свою очередь, число 55 делится на 5: 55 = 5 · 11. Таким

образом, мы получили разложение числа 495 на простые множители:

495 = 32 ·5·11. Для разложения числа 101 на простые множители про­

верим делимость данного числа на простые числа, не превосходящие

vffOI: 2, 3, 5 и 7. Легко видеть, что число 101 не делится ни на одно

2.Докажите, что всякое простое число р, большее трех, представимо

в виде 6q ± 1, q Е N.

Реwение. Пусть р - простое число. По теореме о делении с остат­

ком, р = 6k + r, где k, r Е Z, причем О ~ r < 6. Таким образом, r Е {О, 1, 2, 3, 4, 5}. Если r =О, тор= 6k, и, следовательно, р делит­

ся на 2 и на 3, что дает противоречие с определением простого числа.

Если r = 1, то р = 6k +1, причем k - число натуральное в силу того, что р > 1. Если r = 2, то р = 6k +2, и, следовательно, р делится на 2,

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

2. Если r = 3, тор= 6k + 3, и, следовательно, р делится на 3, что

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

Если r = 4, тор= 6k+4, и, следовательно, р делится на 2 и не равно

2 (почему?), что дает противоречие с определением простого числа. Если r = 5, тор= 6k + 5 или, что то же, р = 6(k + 1) - 1, причем k + 1 - число натуральное в силу того, что р > 1. Таким образом,

мы доказали, что любое простое число р, большее трех, представимо

Замечание. В процессе рассуждений мы доказали, что любое простое число либо равно 2, либо равно 3, либо имеет вид бk +1, k Е N, либо имеет вид бq- 1, q Е N. Этот факт часто используется при решении задач.

3.Найдите все р Е JP, для которых р + 10,р + 14 Е JP.

Реwение. Как было показано в ходе решения предьщущей задачи,

любое простое число либо равно 2, либо равно 3, либо имеет вид

6k+I, k Е N, либо имеет вид 6q-l, q Е N. Если р = 2, то p+lO = 12, то есть р + 1О (/. JP. Если р = 3, то р + 1О = 13, и р + 14 = 17, то есть р+ 10,р+ 14 Е JP. Если р = 6k+ 1, k Е Z, тор+ 14=6k+15, или, что

то же, р+ 14 = 6(k + 2) + 3, то есть р+ 14 делится на 3 и не равно 3, а,

следовательно, является составным числом: р+ 14 ~ JP. Наконец, если

р = 6q-1, q Е Z, то p+lO = 6q+9, или, что тоже, p+lO = 6(k+l)+3,

то есть р + 10 делится на 3 и не равно 3, а, следовательно, является

составным числом: р+ 10 ~ JP. Таким образом, числа р, р+ 10ир+14

являются простыми одновременно только при р = 3. r>

4. Докажите, что сумма квадратов трех._простых чисел, больших трех,

есть число составное.

Реwение. Как было показано ранее, любое простое число р, большее

трех, имеет вид 6q ± 1, q Е N. В каждом из этих случаев квадрат

простого числа р имеет вид 6t+ 1, t Е N: (6k± 1)2 =36k2 ±12k+ 1 = = 6(6k2 ±2k)+ 1. Таким образом, сумма квадратов трех простых чисел,

больших трех, имеет вид 6m + 3, т Е N, и, следовательно, делится

5.Найдите все натуральные n, для которых 8" - 1 - простое число.

Реwение. Поскольку для любых целых чисел а и Ь и для любого

натурального числа n имеет место тождество an - Ь" =(а- Ь)(an-I +

+а"-2Ь+. "+аьn-2 +ьn-1 ), то 8"-1 = {8-1)·(8"- 1 +8"-2 +. "+8+ 1),

или, что то же, 8" - 1=7К, где К Е N. Следовательно, число 8" - 1

делится на 7 для любого натурального n. При этом если n = 1, то

8" - 1 = 7, то есть является простым числом. Если же n > 1, то 8" - 1

делится на 7 и не равно семи, то есть является числом составным.

Таким образом, 8" - 1 Е 1Р' только при n = 1. r>

6. Докажите, что для любого натурального n число 32n + 1 является

составным.

Реwение. Поскольку для любых целых чисел а и Ь и для любо­ го нечетного натурального числа n имеет место тождество а" + Ь" =

=(а+Ь)(а"-1 -а"-2Ь+". -аьп-2 +ьn-1 ), то 32n + 1 = (2")5 + 1 =

= (2"+ 1)·(24"-23"+22"-2"+ 1), или, что тоже, 32"+ 1 = (2"+ l)L,

где L Е N. Следовательно, число 32" + 1 делится на 2" + 1 для любого натурального n. При этом натуральное число 2" + 1 является нетри­ виальным делителем большего единицы натурального числа 32" + 1,

поскольку 2" + l -:/:- 1 и 2" + 1 -:/:- 32" + 1. Таким образом, для любого

натурального n число 32" + 1 является составным. r>

7. Может ли сумма пяти последовательных целых чисел быть простым числом?

Реwение. Сумма пяти последовательных целых чисел z, z + 1, "., z + 4 имеет вид Sz +(О+ 1+2 + 3 + 4) = S(z + 2), или, что то же,

вид Sq, где q Е Z. Следовательно, данная сумма делится на 5 и может

быть простым числом только в случае совпадения с 5. Это возможно

вида. Легко видеть, что число р не может совпадать ни с одним

2. Докажите, что всякое простое число р, большее двух, представимо

ввиде 4q ± 1, q Е N.

3.Докажите, что всякое простое число р, большее трех, представимо

в виде 12q ± 1 или 12q ± 5, q Е N.

4.Найдите все р Е 1Р, для которых р + 5, р + 11 Е 1Р.

5.Найдите все р Е !Р', для которых р4 + 15 Е 1Р.

б. Докажите, что сумма квадратов двух нечетных простых чисел есть

число составное.

7. Докажите, что сумма квадратов четырех нечетных простых чисел есть

число составное.

8. Найдите все натуральные n, для которых:

9. Докажите, что для любого натурального n:

10. Может ли быть простым числом сумма трех последовательных целых чи­

сел; сумма четырех последовательных целых чисел; сумма шести после­

довательных целых чисел; сумма семи последовательных целых чисел?

11.При каких натуральных n число n4 + n2 + 1 является простым?

12.При каких натуральных n число n4 + 64 является составным?

13.Докажите, что любое натуральное число вида 4k - 1, k Е Z, имеет

простой делитель того же вида. Верно ли аналогичное утверждение для целых чисел вида 4k + 1, k Е Z?

14. Докажите, что существует бесконечно много простых чисел вида

4k- 1, k Е N.

1.Составьте таблицу простых чисел р, 100 ~ р ~ 200.

2.Составьте таблицу простых чисел р, 400 ~ р ~ 500.

3.Найдите все тройки р, р + 2, р + 4 последовательных нечетных

простых чисел.

4.Существуют ли четверки р, р + 2, р + 4, р + 6 последовательных нечетных простых чисел?

5.Может ли сумма k последовательных нечетных чисел быть простым числом?

11.Для каких простых р число р + 4 является квадратом целого числа?

12.Найдите все простые числа р, для которых 2р + 1 является кубом

целого числа.

13. Докажите, что если р и 2р - 1 - простые числа, большие трех, то

р- 1 делится на 6.

14.Найдите все числа р, для которых каждое из шести чисел р, р + 2,

р + 6, р + 8, р + 12, р + 14 является простым.

15.Докажите, что для любого натурального п число (n + 1)! +2 является

составным.

16. Докажите, что в натуральном ряду существуют сколь угодно длинные

промежутки, не содержащие простых чисел.

17.Докажите, что 61! + 1 имеет простой делитель р > 66.

18.Докажите, что если простое числор является делителем числа 100! + 1О1,

ТО р ~ 103.

19.Докажите, что разложение натурального числа п в произведение про­

стых чисел содержит не более log2 п множителей.

20.Пусть п - нечетное натуральное число. Докажите, что в разложе­

нии п на простые множители не более log3 п множителей.

23. Какой остаток от деления на 12 дает сумма двух простых-близнецов,

если меньшее из них больше 3?

24.Пусть (р, q) - пара простых-близнецов.. Докажите, что либо 6\(q-1),

либо (р, q) = (3, 5).

25.Найдите все пары простых-близнецов, в которых одно из чисел

есть число Мерсенна Мп = 2п - 1, n Е N, а второе - число Ферма

Fn = 22" + 1, n Е N U {О}.

§4. нод инок

Наибольший общий делитель (а1, ... , an) целых чисел а1, ... , an, хо­

тя бы одно из которых не равно нулю, есть наибольшее целое число,

делящее каждое из чисел а1, ... , an.

Наименьшее общее кратное [а1, ... , an] целых чисел а1, ... , an, каждое

из которых не равно нулю, есть наименьшее натуральное число, делящееся

и Oi = max{ai,f3i}, i = 1, 2, ... , s.

2.Каждый общий делитель чисел а и Ь делит (а, Ь).

3.Каждое общее кратное чисел а и Ь делится на [а, Ь].

4.Если (а,Ь) = d,тосуществуютцелыечислахиу,такиечтоах+Ьу = d.