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

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

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 .

В самом общем случае, количество возможных делителей произвольного числа бесконечно. Фактически, это все не равные нулю числа. Но если речь идет о натуральных числах, то под делителем числа N подразумевается такое натуральное число, на которое нацело делится число N. Количество таких делителей всегда ограничено, а найти их можно с помощью специальных алгоритмов. Также существуют простые делители числа, которые представляют собой простые числа.

Вам понадобится

• - таблица простых чисел;
• - признаки делимости чисел;
• - калькулятор.

Инструкция

• Чаще всего, нужно разложить число на простые множители. Это числа, которые делят исходное число без остатка, и при этом сами могут делиться без остатка только на само себя и единицу (к таким числам относятся 2, 3, 5, 7, 11, 13, 17 и т.д.). Причем, никакой закономерности в ряду простых чисел не найдено. Возьмите их из специальной таблицы или найдите при помощи алгоритма, который называется «решето Эратосфена».
• Начинайте подбирать простые числа, на которые делится данное число. Частное снова делите на простое число и продолжаете этот процесс до тех пор, пока в качестве частного не останется простое число. Затем просто посчитайте количество простых делителей, прибавьте к нему число 1 (которое учитывает последнее частное). Результатом будет количество простых делителей, которые при умножении дадут искомое число.
• Например, количество простых делителей числа 364 найдите таким образом:364/2=182
  182/2=91
  91/7=13Получите числа 2, 2, 7, 13, которые являются простыми натуральными делителями числа 364. Их количество равно 3 (если считать повторяющиеся делители за один).
• Если же нужно найти общее количество всех возможных натуральных делителей числа, воспользуйтесь его каноническим разложением. Для этого по описанной выше методике разложите число на простые множители. Затем запишите число как произведение таких множителей. Повторяющиеся числа возведите в степени, например, если трижды получали делитель 5, то запишите его как 5³.
• Записывайте произведение от наименьших множителей к наибольшим. Такое произведение и называется каноническим разложением числа. Каждый множитель этого разложения имеет степень, представленную натуральным числом (1, 2, 3, 4 и т.д.). Обозначьте показатели степени при множителях а1, а2, а3, и т.д. Тогда общее количество делителей будет равно произведению (a1 + 1)∙(a2 + 1)∙(a3+1)∙…
• Например, возьмите то же число 364: его каноническое разложение 364=2²∙7∙13. Получите а1=2, а2=1, а3=1, тогда количество натуральных делителей этого числа будет равно (2+1)∙(1+1)∙(1+1)=3∙2∙2=12.

Любое составное число с может быть записано в виде произведения с = 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, 5, 7, 11, 13, 17 и т.д.). Причем, закономерности в ряду не найдено. Возьмите их из специальной таблицы или найдите при помощи алгоритма, который называется «решето Эратосфена».

Числа, имеющие более двух делителей, называются составными. Какие же числа могут быть составными?
Так как числа делятся на 2 нацело, то все четные числа , кроме числа 2, будут составными. Действительно, при делении 2:2 двойка делится саму на себя, то есть имеет только два делителя (1 и 2) и является простым числом.

Посмотрим, есть ли у четного числа еще каки-либо делители . Разделим его сначала на 2. Из коммутативности операции умножения очевидно, что получившееся частное также будет делителем числа . Затем, если получившееся частное будет целым, разделим опять на 2 уже это частное. Тогда получившееся в результате новое частное y = (x:2):2 = x:4 тоже будет делителем исходного числа . Аналогично, и 4 будет делителем исходного числа .

Продолжая эту цепочку, обобщим правило: последовательно делим сначала а потом получившееся частные на 2 до тех пор, пока -либо частное не станет равно нечетному числу. При этом все получившиеся частные будут делителями этого числа . Кроме этого делителями этого числа будут и числа 2^k где k = 1...n, где n - число шагов этой цепочки.Пример: 24:2 = 12, 12:2 = 6, 6:2 = 3 - нечетное число. Следовательно, 12, 6 и 3 - делители числа 24. В этой цепочке 3 шага, следовательно, делителями числа 24 будут также числа 2^1 = 2 (уже известно из четности числа 24), 2^2 = 4 и 2^3 = 8. Таким образом, числа 1, 2, 3, 4, 6, 8, 12 и 24 будут делителями числа 24.

Однако не для всех четных чисел эта может дать все делители числа . Рассмотрим, например, число 42. 42:2 = 21. Однако, как известно, числа 3, 6 и 7 также будут делителями числа 42.
Существуют делимости на числа . Рассмотрим важнейшие из них:
Признак делимости на 3: когда сумма цифр числа делится на 3 без остатка.
Признак делимости на 5: когда последняя цифра числа 5 или 0.
Признак делимости на 7: когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7.
Признак делимости на 9: когда сумма цифр числа делится на 9 без остатка.
Признак делимости на 11: когда сумма цифр, занимающих нечётные места, либо равна сумме цифр, занимающих чётные места, либо от неё на число, делящееся на 11.
Существуют также признаки делимости на 13, 17, 19, 23 и другие числа .

Как для четных, так и для нечетных чисел нужно использовать признаки деления на то или иное число. Разделив число, следует определить делители получившегося частного и.т.д. (цепочка аналогична цепочки четных чисел при делении их на 2, описанной выше).

Источники:

• Признаки делимости

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

Инструкция

Чтобы поделить одно число на другое столбиком, запишите вначале делимое, затем делитель. Между ними расположите вертикальную линию. Под делителем проведите горизонтальную линию. Последовательно как бы удаляя у младшие разряды, получите число, которое больше делителя. Последовательно умножая цифры от 0 до 9 на делитель, найдите наибольшее из чисел , меньших полученного на предыдущем этапе. Запишите эту цифру как первый разряд частного. Результат умножения этой цифры на делитель запишите под делимым со сдвигом на один разряд вправо. Произведите вычитание, а с его результатом осуществите те же действия, пока не найдете все разряды частного. Расположение запятой определите, вычтя порядок делителя из порядка делимого.

Если числа не делятся друг на друга, возможны две ситуации. В первой из них одна цифра или сочетание из нескольких цифр будет повторяться бесконечно. Тогда продолжать вычисление бессмысленно - достаточно взять эту цифру или цепочку из цифр в период. Во второй ситуации какой-либо закономерности в частного не удастся. Тогда прекратите деление, добившись желаемой точности результата, а последний округлите.

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

На калькуляторе с обратной польской записью вначале нажмите кнопку сброса, затем введите делимое и нажмите клавишу Enter (вместо этой надписи на ней может быть стрелка, направленная вверх). Число окажется в ячейке стека. Теперь введите делитель и нажмите клавишу со знаком деления. Произойдет деление числа из стека на число, которое отображалось до этого на индикаторе.

Логарифмическую линейку используйте в тех случаях, когда точность требуется небольшая. Уберите из обоих чисел , а затем от каждого из них возьмите по два старших разряда. На шкале A найдите делитель, а затем совместите его с делимым на шкале B. Затем найдите на последней единицу - прямо над ней на шкале A будет расположено частное . Местоположение запятой в нем определите тем же способом, что и столбиком.

Источники:

• Порядок деления столбиком
• частные числа это

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

Нахождение наименьшего общего кратного: основные понятия

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

Кратным числу А называют такое натуральное число, которое без остатка делится на А. Так, числами кратными 5 можно считать 15, 20, 25 и так далее.

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

Общее кратное натуральных чисел - число, которое делится на них без остатка.

Наименьшее общее кратное (НОК) чисел (двух, трех или больше) - это самое маленькое натурально число, которое делится на все эти числа нацело.

Чтобы найти НОК, можно использовать несколько способов.

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

Например, кратные числа 4 можно записать так:

К (4) = {8,12, 16, 20, 24, ...}

К (6) = {12, 18, 24, ...}

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

НОК (4, 6) = 24

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

Вам понадобится

• Для этого вам понадобится листок бумаги или калькулятор.

Инструкция

Разложите каждое сложное число на произведение простых или множителей. Например, 60 и 80, где 60 - равно 2*2*3*5, а 80 - 2*2*2*2*5, проще это можно записать с помощью . В данном случае будет выглядеть как два во второй , умноженное на пять и три, а второй - произведение двух в четвертой и пяти.

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

В завершении просто нужно перемножить получившиеся цифры. В нашем случае все предельно просто: два в , умноженное на пять, равно 20. Таким образом, число 20 можно назвать наибольшим общим делителем для 60 и 80.

Видео по теме

Обратите внимание

Помните, что простым множителем является число, которое имеет только 2 делителя: единица и само это число.

Полезный совет

Кроме данного метода можно также пользоваться алгоритмом Евклида. Полное его описание, представленное в геометрической форме, можно найти в книге Евклида "Начала".

Связанная статья

Нередко можно встретить такие уравнения, в которых неизвестен . Например 350: Х = 50, где 350 - делимое, Х - делитель, а 50 - частное. Для решения этих примеров необходимо произвести определенный набор действий с теми числами, которые известны.

Вам понадобится

• - карандаш или ручка;
• - лист бумаги или тетрадь.

Инструкция

Составьте простое уравнение, где неизвестное, т.е. Х - это количество детей, 5 - это число конфет, полученных каждым ребенком, а 30 - это количество сладостей, которое было куплено. Таким образом вы должны получить : 30: Х = 5. В этом математическом выражении 30 называется делимым, Х - делителем, а получившееся частное равно 5.

Теперь приступайте к решению. Известно: чтобы найти делитель, нужно делимое разделить на частное. Получается:Х = 30: 5;30: 5 = 6;Х = 6.

Сделайте проверку, подставив в уравнение получившееся число. Итак, 30: Х = 5, вы нашли неизвестный делитель, т.е. Х = 6, таким образом: 30: 6 = 5. Выражение верно, а из этого следует, что уравнение решено . Разумеется, при решении примеров, в которых фигурируют простые числа, проверку выполнять необязательно. Но когда уравнения из , трехзначных, четырехзначных и т.д. чисел, обязательно проверяйте себя. Ведь это не отнимает много времени, но дает абсолютную уверенность в полученном результате.

Обратите внимание