АРИФМЕТИКА

Арифметика – царица математики, и подходящие задачи здесь найдёт для себя каждый – от первоклассника до академика.

Замечательные числа

Назовем натуральное число «замечательным», если оно самое маленькое среди всех натуральных чисел с такой же суммой цифр. Например, число 1 замечательное, потому что оно самое маленькое из чисел 1, 10, 100, 1000 и так далее. 1 – это первое замечательное число. Найдите второе замечательное число. Опишите все числа, у которых сумма цифр такая же. То же для третьего, десятого, 2010-го замечательного числа.

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

Прямоугольники с заданной площадью

На клетчатой бумаге нарисуйте все прямоугольники, у которых площадь равна 24 клеткам. (Стороны должны идти по границам клеток.) Сколько получится таких прямоугольников?

Для каких площадей бывает только один прямоугольник? Для каких – два разных прямоугольника? Три разных прямоугольника? Как зависит количество вариантов от площади?

Найдите из всех прямоугольников с одинаковой площадью тот, у которого периметр наименьший.

Разложение числа

Число 15 можно тремя способами представить в виде суммы последовательных натуральных чисел: 15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5. А сколько таких способов для числа 115? Как найти количество способов для произвольного числа?

Суперкомпьютер

Суперкомпьютер умеет выполнять только одну операцию- операцию смешивания двух чисел: из чисел m, n компьютер получает число (m+n) /2. Если m+n – нечетное, то компьютер зависает. Все полученные числа хранятся в памяти. Пусть нам даны три числа, одно из которых ноль, а два другие натуральные и не равны друг другу. Для каких чисел m и n на суперкомпьютере можно получить единицу?

Диагонали прямоугольников

На листе бумаги в клеточку обвели прямоугольник размером 199 х 991 клеток. Через сколько узлов (т.е. вершин клеточек) проходит диагональ? Сколько клеток пересекает диагональ этого прямоугольника? Попробуйте дать ответ для произвольного размера прямоугольника – размером M x N клеток.

Примечание . Диагональ пересекает клетку, если она заходит «внутрь» этой клетки, а не просто проходит через вершину.

Задача о размене

Какие суммы можно уплатить монетами по 3 и 5 рублей? Обобщение: какие числа выражаются комбинацией ax+by, где a и b – данные натуральные числа, x и y – произвольные целые неотрицательные числа.

7. Скла дные квадраты

Скла дные числа – это числа, квадрат которых оканчивается на это же число. Например:

5 2 =25 ; 6 2 =36 ; 25 2 = 625 .

«Пятью пять – двадцать пять », «шестью шесть – тридцать шесть ».

Найдите как можно больше складных чисел; найдите способ нахождения всех таких чисел.

Поиск чисел с заданным количеством делителей

Есть только одно число, имеющее ровно один делитель, - это единица. Ровно два делителя имеют все простые числа. Ровно три делителя имеют, например, числа 4 и 9, являющиеся квадратами простых чисел. Все ли числа, имеющие ровно три делителя, обладают этим свойством? Каким может быть вид числа, имеющего ровно 4 делителя? 5 делителей? Для данного натурального числа N опишите все натуральные числа, имеющие ровно N делителей.

Разложения дробей

, , , …

Для числа 1/7 разложение в десятичную дробь периодично и состоит из шести цифр, а для 2/7, 3/7, …, 6/7 - из тех же шести цифр в другом порядке (проверьте!). А вот для числа 1/13 и 2/13 наборы цифр разные. Исследуйте разложения этих чисел и чисел вида 1/p, 2/p, …, (p-1)/p, для p = 17, 19, 41, 47 и другим простым числам, и разберитесь, какие бывают циклы.

В разнообразных задачах про целые числа используются основные понятия и теоремы, связанные с делимостью. Приведём некоторые из них.

Задачи с решениями

1. Сколько существует натуральных чисел, меньших 1000, которые не делятся ни на 5, ни на 7?

Вычёркиваем из 999 чисел, меньших 1000, числа, кратные 5: их =199. Далее вычёркиваем числа, кратные 7: их =142. Но среди чисел, кратных 7, имеется =28 чисел, одновременно кратных 5; они будут вычеркнуты дважды. Итого, нами должно быть вычеркнуто 199+142–28=313 чисел. Остаётся 999–313=686.

Ответ: 686 чисел.

2. Номер автобусного билета – шестизначное число. Билет называется счастливым, если сумма трёх первых цифр номера равна сумме последних трёх цифр. Докажите, что сумма всех номеров счастливых билетов делится на 13.

Если счастливый билет имеет номер А, то билет с номером В=999999–А также счастливый, при этом А и В различны. Поскольку А+В=999999=1001·999=13·77·99 делится на 13, то и сумма номеров всех счастливых билетов делится на 13.

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

Любое целое число при делении на 8 имеет остатком одно из следующих восьми чисел 0, 1, 2, 3, 4, 5, 6, 7, поэтому квадрат целого числа имеет остатком при делении на 8 одно из трёх чисел 0, 1, 4. Чтобы при делении на 8 сумма квадратов трёх чисел имела остаток 7, необходимо, чтобы выполнялся один из двух случаев: либо один из квадратов, либо все три при делении на 8 имеют нечётные остатки.

В первом случае нечётный остаток есть 1, а сумма двух чётных остатков равна 0, 2, 4, то есть сумма всех остатков равна 1, 3, 5. Остатка 7 в этом случае получить нельзя. Во втором случае три нечётных остатка это три 1, и остаток всей суммы равен 3. Итак, 7 не может быть остатком при делении на 8 суммы квадратов трёх целых чисел.

4. Докажите, что при любом натуральном n:

а) число 5 5n+1 + 4 5n+2 + 3 5n делится на 11.

б) число 2 5n+3 + 5 n ·3 n+2 делится на 17.

а) Первоначально выполним следующее преобразование заданного выражения:

5 5n+1 +4 5n+2 +3 5n = 5(3125) n + 16(1024) n + (243) n = 5(11·284+1) n + 16(11·93+1) n + (11·22+1) n .

Принимая во внимание бином Ньютона n-й степени, можно записать: (х+1) n = Ах+1, где А – некоторое целое число при целых х. Тогда приведённое выше выражение принимает вид 11В+5+16+1 = 11С, очевидно делящееся на 11, где В и С – некоторые целые числа.

б) Выполним следующие преобразования, из которых следует доказываемое утверждение:

2 5n+3 + 5 n ·3 n+2 = 8·32 n + 9·15 n = 8(17+15) n + 9·15 n = 17А + 8·15 n + 9·15 n = 17А + 17·15 n = 17В,

где А, В – целые положительные числа.

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

а) если х 2 +у 2 делится на 3 и числа х, у целые, то х и у делятся на 3;

б) если сумма трёх целых чисел делится на 6, то и сумма кубов этих чисел делится на 6;

в) если p и q простые числа и p>3, q>3, то p 2 –q 2 делится на 24;

г) если a, b, c – любые целые числа, то найдутся такие взаимно простые k и t, что ak+bt делится на c.

а) Пусть х=3а+r 1 , у=3b+r 2 , где r 1 и r 2 – остатки от деления на 3, то есть какие-то из чисел 0, 1, 2. Тогда х 2 +у 2 =3(3а 2 +3b 2 +2аr 1 +2br 2)+(r 1) 2 +(r 2) 2 . Так как х 2 +у 2 делится на 3, первое слагаемое последней суммы делится на 3, то (r 1) 2 +(r 2) 2 делится на 3, что возможно, с учётом вышесказанного, только при r 1 =r 2 =0.

Таким образом, х=3а и у=3b, то есть х и у делятся на 3, что и требовалось доказать.

б) Достаточно показать, что x 3 +y 3 +z 3 –(x+y+z) делится на 6. Это так и есть, ведь каждое из слагаемых x 3 –x, y 3 –y и z 3 –z делится на 6, поскольку а 3 –а=а(а–1)(а+1) – произведение трёх последовательных целых чисел, которое обязательно делится на 2, 3, а, значит, и 6.

в) Кратность p 2 –q 2 числу 3 можно доказать так. При делении на 3 квадраты целых чисел дают остатки 0 или 1. Так как p и q простые числа больше 3, то это p 2 и q 2 при делении на 3 имеют одинаковые остатки – единицу. Тогда p 2 –q 2 делится на 3.

С другой стороны, p 2 –q 2 =(p+q)(p–q). Так как p и q нечётные и при делении на 4 имеют остатки 1 или 3, то выражение в одних скобках делится на 4, а в других – на 2, а разность квадратов p и q – на 8.

Так как p 2 –q 2 делится на взаимно простые числа 3 и 8, то p 2 –q 2 делится на 3·8=24, что и требовалось доказать.

г) Пусть наибольший общий делитель чисел b и c–a равен d, b=k·d и c–a=t·d. Тогда числа k и t взаимно просты.

Итак, a·k+b·t делится на c.

6. Найдите:

а) наибольший общий делитель чисел 2n+3 и n+7;

б) все пары натуральных чисел х, у таких, что 2х+1 делится на у и 2у+1 делится на х;

в) все целые k, для которых k 5 +3 делится на k 2 +1;

г) хотя бы одно натуральное число n такое, что каждое из чисел n, n+1, n+2, ... , n+20 имеет с числом 30030=2·3·5·7·11·13 общий делитель, больший единицы.

а) Заметим, что если m > n, то НОД (m; n) = НОД (m – n; n).

Иначе говоря, наибольший общий делитель двух натуральных чисел равен наибольшему общему делителю модуля их разности и меньшего числа. Легко доказать это свойство.

Пусть k – общий делитель m u n (m > n). Это значит, что m = ak, n = bk, где a, b – натуральные числа, причем a > b. Тогда m – n = k(a – b), откуда следует, что k – делитель числа m – n. Значит, все общие делители чисел m и n являются делителями их разности m – n, в том числе и наибольший общий делитель.

Воспользуемся вышесказанным:

НОД (2n+3; n+7) = НОД (n+7; 2n+3 – (n+7)) = НОД (n+7; n–4) = НОД (n–4; 11).

Так как 11 – простое число, то искомый наибольший общий делитель равен 1 либо 11. Если n–4 = 11d, то есть n = 4+11d, то наибольший общий делитель равен 11, в противном случае – 1.

Ответ: НОД (2n+3; n+7) = 11, при n равных 4+11d; НОД (2n+3; n+7) = 1, при n не равных 4+11d.

б) Число 2х+1 нечётное и делится на у, поэтому у тоже нечётное. Аналогично х – нечётное.

Числа х и у взаимно простые. Действительно, пусть k – общий делитель х и у, тогда 2х делится на k, и (2х+1) тоже делится на k (k – делитель у, а у – делитель 2х+1). Значит, 1 делится на k, то есть k=1.

Число 2х+2у+1 делится и на х и на у, а значит, – на ху. Тогда 2х+2у+1 не меньше ху.

Ответ: (1; 1), (1; 3), (3; 1), (3; 7), (7; 3).

в) Так как k 5 +3 = (k 3 –k)(k 2 +1) + (k+3), то k 5 +3 делится на k 2 +1, если k+3 делится на k 2 +1. Когда это возможно? Рассмотрим варианты:

1) k+3 = 0, а значит k = –3;

2) k+3 = k 2 +1; решая, находим k = –1, k = 2;

3) проверим целые k при которых k+3 > k 2 +1; после проверки: k = 0, k = 1.

Ответ: –3, –1, 0, 1, 2.

г) пусть m = 2·3·5·7·k. Подбирая k так, чтобы m–1 делилось на 11, а m+1 – на 13, получим, что число n = m–10 удовлетворяет условию задачи.

Ответ: например,9440.

7. Существует ли десятизначное число, делящееся на 11, в записи которого каждая цифра встречается по одному разу?

I способ. Выписывая трёхзначные числа, делящиеся на 11, можно среди них найти три числа, в записи которых участвуют все цифры от 0 до 9. Например, 275, 396,418. С их помощью можно составить десятизначное число, делящееся на 11. Например:

2753964180 = 275·10 7 + 396·10 7 + 418·10 = 11·(25·10 7 + 36·10 4 + 38·10).

II способ. Для нахождения требуемого числа воспользуемся признаком делимости на 11, согласно которому числа n=a 1 a 2 a 3 …a 10 (в данном случае а i не множители, а цифры в записи числа n) и S(n)=a 1 –a 2 +a 3 –…–a 10 одновременно делятся на 11.

Пусть А – сумма цифр, входящая в S(n) со знаком «+», В – сумма цифр, входящая в S(n) со знаком «–». Число А–В, согласно условию задачи, должно делиться на 11. Положим В–А=11, кроме того, очевидно, А+В=1+2+3+…+9=45. Решая полученную систему В–А=11, А+В=45, находим, А=17, В=28. Подберём группу из пяти различных цифр с суммой 17. Например, 1+2+3+5+6=17. Эти цифры возьмём в качестве цифр с нечётными номерами. В качестве цифр с чётными номерами возьмём оставшиеся – 4, 7, 8, 9, 0.

Мы видим, что условию задачи удовлетворяет, например, число 1427385960.

8. Два двузначных числа, записанных одно за другим, образуют четырёхзначное число, которое делится на их произведение. Найти эти числа.

Пусть a и b – два двузначных числа, тогда 100a+b – четырёхзначное число. По условию 100a+b = k·ab, отсюда b = a(kb–100), то есть b делится на a.

Итак, b = ma, но a и b двузначные числа, поэтому m однозначное.

Так как 100a+b = 100a+ ma = а(100+m) и 100a+b = kab, то а(100+m) = kab,

то есть 100+m = kb или 100+m = kma, откуда 100 = m(ka–1).

Таким образом, m – делитель числа 100, кроме того, m – однозначное число, значит, m = 1, 2, 4, 5.

Так как ka = 1+100/m, причём а двузначно, то отпадают для m значения 1 и 5, ибо

при m = 1 число 100/1+1 = 101 не делится ни на какое двузначное число а;

при m = 5 число 100/5+1 = 21 и имеем а=21, при котором b = ma = 5·21 – трёхзначное число.

При m = 2 имеем, ka = 51, a = 17, b = 17·2 = 34;

при m = 4 имеем, ka = 26, a = 13, b = 13·4 = 52.

Ответ: 17 и 34, 13 и 52.

9. Докажите, что при любых натуральных k и n число 1 2k+1 + 2 2k+1 + . . . + n 2k+1 не делится на n + 2.

Воспользуемся тем, что сумма одинаковых нечётных степеней двух чисел делится на сумму этих чисел, что следует из . Можно записать:

2 2k+1 + n 2k+1 = (2 + n)·А 1 ,

3 2k+1 + (n – 1) 2k+1 = (3 + (n – 1))·А 2 = (2 + n)·А 2 ,

4 2k+1 + (n – 2) 2k+1 = (4 + (n – 2))·А 3 = (2 + n)·А 3 и так далее, где А i – некоторые целые числа.

В зависимости от чётности n возможна нехватка числа для образования последней пары, избежать этого позволит умножение на 2, рассматриваемой в условии суммы. Итак,

2(1 2k+1 + 2 2k+1 +...+n 2k+1) = 2·1 2k+1 + (2 2k+1 + n 2k+1) + (3 2k+1 + (n – 1) 2k+1) +...+ (n 2k+1 + 2 2k+1) =

2 + (n + 2)·А, где А – некоторое целое число.

Одно из слагаемых последней суммы делится на n + 2, другое при любых натуральных n – нет. Итак, рассматриваемая в условии сумма не делится на n при любых натуральных n и k.

10. Докажите, что для любого простого числа р > 2 числитель m дроби

делится на p.

Заметим, что число р–1 чётное, и преобразуем дробь m/n к виду

Приводя полученное выражение к общему знаменателю

получаем соотношение

из которого вытекает равенство m(p–1)!=pqn. Поскольку ни одно из чисел 1, 2, 3, … , р–1 не делится на простое число р, то последнее равенство возможно лишь в случае, если m делится на р, что и требовалось доказать.

Задачи без решений

1. Докажите, что при любом натуральном n:

а) число 4 n + 15n – 1 делится на 9;

б) число 3 2n+3 + 40n – 27 делится на 64;

в) число 5 n (5 n + 1) – 6 n (3 n + 2 n) делится на 91.

2. Найдите:

а) натуральные значения n такие, что n 5 – n делится на 120;

б) наименьшее натуральное число n такое, что n делится на 19, а n + 2 делится на 82.

3. Пусть m, n – различные натуральные числа, причём m – нечётное. Докажите, что 2 m –1 и 2 n +1 взаимно простые.

4. Четыре различных целых трёхзначных числа, начинающиеся с одной и той же цифры, обладают тем свойством, что их сумма делится на три из них без остатка. Найдите эти числа.

5. Докажите, что для каждого натурального n > 1 число n n – n 2 + n – 1 делится на (n – 1) 2 .

Любое составное число с может быть записано в виде произведения с = ab, причем ни один из делителей не равен 1 и каждый из них меньше, чем с ; например,

72 = 8 9, 150 = 10 15.

При разложении числа с на множители один из них, и даже оба (а и b ) могут оказаться составными. Если а - составное, то разложение на множители можно продолжить:

а = a 1 a 2 , с = a 1 a 2 b .

Примерами этого могут служить рассмотренные выше числа

72 = 2 4 9, 150 = 2 5 15.

Этот процесс разложения на множители можно продолжить до тех пор, пока он не закончится; это должно произойти, так как делители становятся все меньше и меньше, но не могут стать единицей. Когда ни один из делителей нельзя уже будет разложить на множители, то все делители будут простыми числами.

Таким образом мы показали, что

Каждое целое число, большее 1, является простым числом или произведением простых чисел.

Последовательное разложение числа на множители может быть выполнено многими способами. При этом можно использовать таблицу делителей. Сначала найдем наименьшее простое число р 1 , делящее число с , так что с = р 1 с 1 . Если с 1 - составное число, то по таблице делителей найдем наименьшее простое число р 2 , делящее с 1 , так что

c 1 = р 2 с 2 , c = p 1 p 2 с 2 .

Затем найдем наименьший простой делитель числа с 2 и т. д.

Но главное здесь то, что независимо от способа разложения числа на простые множители результат всегда будет одним и тем же, различаясь лишь порядком их записи, т. е. любые два разложения числа на простые множители содержат одни и те же простые числа; при этом каждое простое число содержится одинаковое число раз в обоих разложениях.

Этот результат мы можем кратко выразить следующим образом:

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

Возможно, что вы так часто слышали об этой так называемой «основной теореме арифметики» и пользовались ею, что она представляется вам очевидной, но это совсем не так. Эта теорема может быть доказана несколькими различными способами, однако ни один из них не тривиален. Здесь мы приведём доказательство, используя способ «от противного», который часто называют его латинским названием reductio ad absurdum (приведением к абсурду). Этот способ заключается в следующем: предположив ложность теоремы, которую нужно доказать, показывают, что это предположение приводит к противоречию.

Доказательство . Предположим, что наша теорема о единственности разложения на множители неверна. Тогда должны существовать числа, имеющие по крайней мере два различных разложения на простые множители. Выберем из них наименьшее и обозначим его через с 0 . Для небольших чисел, скажем, меньших 10, истинность теоремы можно установить прямой проверкой. Число с 0 имеет наименьший простой множитель р 0 , и мы можем записать:

c 0 = p 0 d 0 .

Так как d 0 < c 0 , то число d 0 единственным образом раскладывается на простые множители. Отсюда следует, что разложение числа c 0 на простые множители, содержащее число р 0 , единственно.

А так как, по предположению, имеется по крайней мере два разложения числа c 0 на простые множители, то должно быть разложение, не содержащее число р 0 . Наименьшее простое число в этом разложении мы обозначим через р 1 и запишем

c 0 = p 1 d 1 . (3.1.1)

Так как p 1 > p 0 , то d 1 < d 0 и, следовательно, p 0 d 1 < c 0 . Рассмотрим число

c 0 " = c 0 - p 0 d 1 = (p 1 - p 0) d 1 . (3.1.2)

Так как оно меньше, чем число c 0 , то оно должно раскладываться на простые множители единственным способом; при этом простые множители числа c 0 состоят из простых множителей чисел p 1 - p 0 и d 1 . Так как число c 0 делится на p 0 , то из выражения (3.1.2) следует, что число c 0 " также делится на p 0 . Следовательно, p 0 должно быть делителем либо числа d 1 , либо p 1 - p 0 . Но любой простой делитель числа d 1 больше, чем p 0 , так как p 1 - наименьшее простое число в разложении (3.1.1). Таким образом, остается единственная возможность: p 0 должно быть делителем числа p 1 - p 0 и, следовательно, оно делит p 1 . Итак, мы пришли к противоречию, потому что p 1 является простым числом и не может делиться на другое простое число p 0 .

Выше мы отмечали, что единственность разложения числа на простые множители совсем не очевидна. В действительности, существуют «арифметики», в которых аналогичная теорема не выполняется. Простейшим примером такой арифметики может служить арифметика четных чисел

2, 4, 6, 8, 10, 12…

Некоторые из них могут быть разложены на два четных множителя, а другие - нет; последние мы называем чётно-простыми числами . Это числа, которые делятся на 2, но не делятся на 4:

2, 6, 10, 14, 18….

Очевидно, что каждое четное число либо является четно-простым, либо записывается в виде произведения чётно-простых чисел. Но такое разложение на чётно-простые числа не всегда будет единственным. Например, число 420 может быть разложено на четно-простые числа различными способами:

420 = 6 70 = 10 42 = 14 30.

Система задач 3.1.

1. Найдите разложение на простые множители каждого из чисел 120, 365, 1970.

2. Проделайте то же самое для чисел, указанных в задаче 1 системы задач 2.1 (стр. 25).

3. Запишите все разложения числа 360 на чётно-простые числа.

4. В каких случаях четные числа обладают единственным разложением на четно-простые множители?

§ 2. Делители

Разложим на множители какое-нибудь число, скажем, 3600. Это разложение

3600 = 2 2 2 2 3 3 5 5

может быть записано как

3600 = 2 4 3 2 5 2 .

Вообще при разложении числа n на множители аналогично можно собирать одинаковые простые множители в виде степеней и записывать

n = p 1 α 1 p 2 α 2 …. р r α r , (3.2.1)

где p 1 , p 2 …. р r - различные простые множители числа n , причем число p 1 входит α 1 раз, p 2 входит α 2 раз и т. д.

Если мы знаем вид (3.2.1) для числа, то мы сможем тотчас же ответить на некоторые вопросы об этом числе.

Например, если мы захотим, то можем узнать, какие числа делят число n . Возьмем для примера рассмотренное выше число 3600. Предположим, что число d является одним из его делителей, т. е.

3600 = d d 1 .

Приведенное разложение на простые множители показывает, что единственными числами среди множителей числа d будут лишь 2, 3, 5. Кроме того, число 2 может содержаться не более 4 раз, а числа 3 и 5 не более, чем по 2 раза каждое. Итак, мы видим, что возможными делителями числа 3600 будут числа вида

d = 2 δ 1 3 δ 2 5 δ 3 ,

при этом показатели степени могут принимать значения:

δ 1 = 0, 1, 2, 3, 4;

Так как эти значения могут сочетаться всеми возможными способами, то число делителей равно

(4 + 1) (2 + 1) (2 + 1) = 5 3 3 = 45.

Для любого числа n , разложение которого на простые множители дается формулой (3.2.1), положение точно такое же. Если число d является делителем числа n , т. е.

n = d d 1

то единственными простыми числами, на которые может делиться число d , будут только те, которые делят число n , а именно: p 1 …, р r . Таким образом, мы можем записать разложение числа d на простые множители в виде

d = p 1 δ 1 p 2 δ 2 …. р r α r , (3.2.2)

Простое число p 1 может содержаться не более α 1 раз, как и в самом числе n ; аналогично - для p 2 и других простых чисел. Это значение для числа δ 1 мы можем выбрать α 1 + 1 способом:

δ 1 = 0, 1…, α 1 ;

аналогично и для других простых чисел. Так как каждое из α 1 + 1 значений, которые может принимать число δ 1 , может сочетаться с любым из α 2 + 1 возможных значений числа δ 2 и т. д., то мы видим, что общее число делителей числа n задается формулой

τ(n ) = (α 1 + 1) (α 2 + 1)… (α r + 1). (3.2.3)

Система задач 3.2.

1. Сколько делителей имеет простое число? Сколько делителей имеет степень простого числа р α ?

2. Найдите количество делителей у следующих чисел: 60, 366, 1970, вашего почтового индекса.

3. Какое натуральное число (или числа), не превосходящее 100, имеет наибольшее количество делителей

§ 3. Несколько задач о делителях

Существует единственное число n = 1, которое имеет только один делитель. Числами с ровно двумя делителями являются простые числа n = р : они делятся на 1 и на р . Наименьшим числом, имеющим два делителя, является, таким образом, р = 2.

Исследуем числа, имеющие ровно 3 делителя. В соответствии с (3.2.3) имеем

3 = (α 1 + 1) (α 2 + 1)… (α r + 1).

Так как 3 - простое число, то справа может существовать лишь один множитель, не равный 1. Отсюда r = 1, a α 1 = 2. Таким образом,

n = p 1 2 .

Наименьшим числом с 3 делителями является n = 2 2 = 4. Это соображение, примененное к общему случаю, когда число делителей q является простым числом, позволяет получить, что

q = α 1 + 1, т. е. α 1 = q - 1 и n = р 1 q -1 ;

наименьшим из таких чисел является

n = 2 q -1 .

Рассмотрим следующий случай, когда существует ровно 4 делителя. Тогда соотношение

4 = (α 1 + 1) (α 2 + 1),

возможно только тогда, когда

α 1 = 3, α 2 = 0 или α 1 = α 2 = 1.

Это приводит к двум возможностям:

n = p 1 3 , n = p 1 p 2 ;

наименьшее число с 4 делителями - это n = 6.

В том случае, когда имеется 6 делителей, должно выполняться соотношение

6 = (α 1 + 1) (α 2 + 1),

что возможно лишь тогда, когда

α 1 = 5, α 2 = 0 или α 1 = 2, α 2 = 1.

Это дает две возможности:

n = p 1 5 , n = p 1 2 p 2 ;

при этом наименьшее значение имеет место в последнем случае, когда

p 1 = 2, p 2 = 3, n =12.

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

Существуют таблицы, указывающие количество делителей для различных чисел. Они начинаются следующим образом:

Вы легко можете ее самостоятельно продолжить.

Будем говорить, что натуральное число n является сверхсоставным , если количество делителей у каждого числа, меньшего n , меньше, чем количество делителей у числа n . Глядя на нашу небольшую таблицу, мы видим, что

являются первыми пятью сверхсоставными числами. О свойствах этих чисел известно еще очень мало.

Система задач 3.3.

1. Взвод из 12 солдат может маршировать 6-ю различными способами: 12 × 1, 6 × 2, 4 × 3, 3 × 4, 2 × 6, 1 × 12. Какую наименьшую численность должны иметь группы людей, которые могут маршировать 8, 10, 12 и 72 способами?

2. Найдите наименьшие натуральные числа, имеющие: а) 14 делителей, б) 18 делителей ив) 100 делителей.

3. Найдите два первых сверхсоставных числа, следующих за числом 12.

4. Охарактеризуйте все натуральные числа, количество делителей которых является произведением двух простых чисел.

§ 4. Совершенные числа

Нумерология (или гематрия, как ее иногда еще называют) была распространенным увлечением у древних греков. Естественным объяснением этому является то, что числа в Древней Греции изображались буквами греческого алфавита, и поэтому каждому написанному слову, каждому имени соответствовало некоторое число. Люди могли сравнивать свойства чисел, соответствующих их именам.

Делители или аликвотные части чисел играли важную роль в нумерологии. В этом смысле идеальными, или, как их называют, совершенными числами являлись такие числа, которые составлялись из своих аликвотиых частей, т. е. равнялись сумме своих делителей. Здесь следует отметить, что древние греки не включали само число в состав его делителей.

Наименьшим совершенным числом является 6:

За ним следует число 28:

496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248.

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

6 = 2 3 = 2(2 2 - 1),

28 = 2 2 7 = 2 2 (2 3 - 1),

496 = 24 31 = 2 4 (2 5 - 1).

Это наталкивает нас на гипотезу:

Число является совершенным, если оно представляется в виде

Р = 2 p -1 (2 p - 1) = 2 р q , (3.4.1)

q = 2 p - 1

является простым числом Мерсенна.

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

1, 2, 2 2 …, 2 р-1 ,

q , 2q , 2 2 q …, 2 р-1 q .

Запишем сумму этих делителей

1 + 2 +… + 2 р -1 + q (1 + 2 +… + 2 р -1),

которая равна

(1 + 2 +… + 2 р -1)(q + 1) = (1 + 2 +… + 2 р -1) 2 р

Если вы не помните формулы для суммы членов геометрической прогрессии,

S = 1 + 2 +… + 2 р -1 ,

то умножьте эту сумму на 2:

2S = 2 + 2 2 +… +2 р -1 + 2 р ,

а затем, вычтя S , получите

S = 2 p - 1 = q .

Таким образом, сумма всех делителей числа Р есть

2 p q = 2 2 p -1 q,

а сумма всех делителей, кроме самого числа Р = 2 p -1 q , равна

2 2 p -1 q - 2 p -1 q = 2 p -1 q = Р.

Итак, наше число является совершенным.

Из этого результата следует, что каждое простое число Мерсенна порождает совершенное число. В § 2 второй главы говорилось, что известно всего 23 простых числа Мерсенна, следовательно, мы знаем также и 23 совершенных числа. Существуют ли другие виды совершенных чисел? Все совершенные числа вида (3.4.1) являются четными, можно доказать, что любое четное совершенное число имеет вид (3.4.1). Остается вопрос: существуют ли нечетные совершенные числа? В настоящее время мы не знаем ни одного такого числа, и вопрос о существовании нечетных совершенных чисел является одной из самых знаменитых проблем теории чисел. Если бы удалось обнаружить такое число, то это было бы крупным достижением. Вы можете поддаться соблазну найти такое число, перебирая различные нечетные числа. Но мы не советуем этого делать, так как по последним сообщениям Брайена Такхермана из IBM (1968), нечетное совершенное число должно иметь по крайней мере 36 знаков.

Система задач 3.4.

1. Используя список простых чисел Мерсенна, найдите четвертое и пятое совершенные числа.

§ 5. Дружественные числа

Дружественные числа также входят в наследство, доставшееся нам от греческой нумерологии. Если у двух людей имена были таковы, что их числовые значения удовлетворяли следующему условию: сумма частей (делителей) одного из них равнялась второму числу, и наоборот, то считалось, что это свидетельствует об их духовной близости. В действительности греки знали всего лишь одну пару таких чисел, а именно:

220 = 2 2 5 11, 284 = 2 2 71.

Суммами их делителей являются соответственно

1 + 2 + 4 + 5 +10 + 20 + 11 + 22 + 44 + 55 + 110 = 284,

1 + 2 + 4 + 71 + 142 = 220.

Эта пара дружественных чисел оставалась единственной известной до тех пор, пока Пьеру Ферма не удалось найти следующую пару:

17 296 = 2 4 23 47, 18 416 = 2 4 1151.

Поиски пар дружественных чисел чрезвычайно удобно вести с помощью ЭВМ. Для каждого числа n при помощи машины определяются все делители этого числа (≠ n ) и их сумма m . После этого производится такая же операция с числом m . Если при этом вновь получается первоначальное число n , то пара чисел (n, m ) оказывается дружественной. Недавно этим способом в Йельском университете на ЭВМ IBM 7094 были проверены все числа до одного миллиона. В результате была получена коллекция из 42 пар дружественных чисел; некоторые из них оказались ранее неизвестными. Все пары дружественных чисел до 100 000 приведены в табл. 2. При помощи этого метода, как нетрудно видеть, одновременно «вылавливаются» и совершенные числа. Если возникает желание продолжать поиски дальше, то, конечно, это можно сделать, но придется затратить большое количество машинного времени.

Таблица 2

Дружественные числа до 100 000

В действительности мы очень мало знаем о свойствах пар дружественных чисел, однако, можно на основе наших таблиц высказать несколько предположений. Например, отношение одного из них к другому, по-видимому, должно все больше и больше приближаться к 1 по мере того, как они увеличиваются. Из таблицы видно, что эти числа бывают либо оба четными, либо оба нечетными, но не было найдено случая, когда одно число четно, а другое нечетно, хотя поиски дружественных чисел такого вида были проведены среди всех чисел n ≤ 1 3 000 000 000.

Примечания:

Аликвотные дроби - дроби вида 1/n; в древности было принято всякую дробь представлять в виде суммы аликвотных дробей. Например, 5/12 = 1/12 + 1/3. (Прим. перев .)

Американская фирма, выпускающая вычислительное оборудование. (Прим. перев. )

Как решить задачу, если нет идеи? Нет универсального способа, позволяющего решать любые задачи. Но есть методика, дающая возможность продвинуться и в трудных ситуациях, тем более, в лёгких заданиях, которые предлагаются в тестах ЦТ. Эту методику описывает великий мастер эвристики Д. Пойа. Абутуриенту полезно с ней.
А ниже приводятся эвристические указания к решению задач первой темы курса для абитуриента. Разумеется, ими не следует пользоваться, если не сделано попыток решения более трудных для вас заданий.
Задачи.
№2. Простые числа имеют ровно два делителя. А какие числа имеют ровно 3 делителя?
Начните с числового эксперимента. Подметьте особенность чисел, имеющих три делителя. Обобщите и докажите.
№6. Найдите наименьшее натуральное число, большее десяти, которое при делении на 24, 45 и 56 давало бы в остатке 1.
Если х даёт при делении на n остаток 1, то число х-1 делится на n?
№7. Лист картона со сторонами 54 см и 36 см надо разрезать без отходов на равные квадраты. Найдите площадь наибольшего квадрата, который можно получить из этого листа.
Если сделать рисунок так, чтобы квадраты покрыли прямоугольник соответствующим образом, то идея о длине стороны наибольшего квадрата должна появиться. С каким математическим понятием это связано?
№10. Найдите два натуральных числа, зная, что их сумма равна 85, а наименьшее общее кратное равно 102.
Если НОК искомых чисел равен 102, то они должны быть делителями числа 102. Но их тогда можно все выписать...
№13. Трехзначное число оканчивается цифрой 3. Если ее перенести в начало записи числа, то полученное число будет на 27 больше первоначального. Найти это число.
Записать искомое число в стандартном виде: 100a 10b c, c=3.
№20. Задумано целое положительное число. К его записи приписали справа цифру 7 и из полученного числа вычли квадрат задуманного. Разность уменьшили на 75% и ещё вычли задуманное число. В окончательном результате получили 4. Какое число задумано?
Если задуманное число назвать n, то какое число получим, если к его поразрядной записи приписать 7? Можете поэксперементировать?
№30. Решить в натуральных числах уравнение: а) (х-2у)(2х-1+у)=11; в) (х+3у-2) 2 +(у-4) 2 =29; д) 55х 2 -12ху-91у 2 =59; ж) 4x 3 -2y 3 -z 3 =0.
а) Произведение каких натуральных чисел равно 11?.. в) Сумма квадратов каких целых чисел даёт 29?.. д) Идея из пункта а). ж) Здесь интересно, это для олимпиадников. Во-первых, одно решение (одна тройка чисел x, y, z) сразу видна. Будем искать ненулевые решения. Заметим, что z 3 - чётное число (если перенести другие слагаемые вправо). Следовательно, z - чётно. Тогда его можно записать как 2n, где n - целое. Подставим это вместо z в уравнение... . Порассуждайте в таком духе и дальше.
№32. Найти все тройки целых чисел, которые удовлетворяют неравенству

Ясно, что преобразование неравенства ничего хорошего не даст. Тогда надо, как обычно, наблюдать его структуру, искать какие-то особенности и зависимости. Случаен ли подбор коэффициентов в подкоренных выражениях? Попробуем сложить подкоренные выражения... . Результат будет интересен. Тогда, учитывая, что эти выражения - натуральные числа, сделаем вывод о том, что... . Дальше будет дело техники.
№33. При каких целых значениях n дроби: б) (2n+7)/(n+1) принимает целое значение?
.

Можно видеть теперь, при каком условии значение выражения станет целым числом.
№34. У натурального числа ровно 6 натуральных делителей. Сумма этих делителей равна 104. Найдите это число.
Как устроено число n, у которого 6 делителей? Если разложить его на простые множители, то сколько их? Когда разложение выглядит так n=pq, p ≠ q, то у него 4 делителя. А если n=pqr при различных сомножителях, то делителями являются 1, p, q, pq, pr, qr, pqr. То есть их больше шести... . Найдите самостоятельно нужное разложение. А потом используйте условие и работайте с полученным равенством.