Я одна, но всё же я есть. Я не могу сделать всё, но всё же могу сделать что-то. И я не откажусь сделать то немногое, что могу (c)

Число и сумма натуральных делителей натурального числа
Основная теорема арифметики. Всякое натуральное число п > 1 либо просто, либо может быть представлено, и притом единственным образом - с точностью до порядка следования сомножителей, в виде произведения простых чисел (можно считать, что любое натуральное число, большее 1, можно представить в виде произведения простых чисел, если считать, что это произведение может содержать всего лишь один множитель).
Среди простых сомножителей, присутствующих в разложении `n = p1*p2*...*pk`, могут быть и одинаковые. Например, `24=2*2*2*3`. Их можно объединить, воспользовавшись операцией возведения в степень. Кроме того, простые сомножители можно упорядочить по величине. В результате получается разложение
`n = p_1^(alpha_1)*p_2^(alpha_2)*.......*p_k^(alpha_k)`, где `alpha_1, alpha_2, ......, alpha_k in NN`
(1)
Такое представление числа называется каноническим разложением его на простые сомножители. Например, каноническое представление числа 2 520 имеет вид 2 520 = 2 3 З 2 5 7.
Из канонического разложения числа легко можно вывести следующую лемму: Если n имеет вид (1), то, то все делители этого числа имеют вид:
`d = p_1^(beta_1)*p_2^(beta_2)*......*p_k^(beta^k)`, где `0 <= beta_m <= alpha_m` (`m = 1,2,..., k`)
(2)
В самом деле, очевидно, что всякое d вида (2) делит а. Обратно, пусть d делит а, тогда a=cd, где с - некоторое натуральное число и, следовательно, все простые делители числа d входят в каноническое разложение числа а с показателями, не превышающими соответствующих показателей числа а.
Рассмотрим две функции, заданные на множестве натуральных чисел:
а) τ(n) - число всех натуральных делителей n;
2) σ(n) сумма всех натуральных делителей числа n.
Пусть n имеет каноническое разложение (1). Выведем формулы для числа и суммы его его натуральных делителей.
Теорема 1. Число натуральных делителей числа n
`tau(n) = (alpha_1 + 1)*(alpha_2 + 1)*.....*(alpha_k + 1);`
(3)
Доказательство.

Пример. Число 2 520 = 2 3 З 2 5 7. имеет (3+1)(2+1)(1+1)(1+1) = 48 делителей.
Теорема 2. Пусть n имеет каноническое разложение (1). Тогда сумма натуральных делителей числа n равна
`sigma(n) = (1 + p_1 + p_1^2 + ..... + p_1^(alpha_1))*(1 + p_2 + p_2^2 + ..... + p_2^(alpha_2))* ..............* (1 + p_k + p_k^2 + .....+ p_k^(alpha_k));`
(4)
Доказательство.

Пример. Найти сумму всех делителей числа 90.
90=2 З 2 5. Тогда σ(90)=[(2 2 -1)/(2-1)] [З 3 -1)/(3-1)] [(5 2 -1)/(5-1)]=234
Формула (4) может помочь найти все делители числа.Так, например, чтобы найти все делители числа 90, раскроем скобки в следующем произведении (не производя операцию сложения): (1+2)(1+3+З 2)(1+5)=(1+1*3+1*З 2 +1*2+2*3+2*З 2)(1+5) = 1+3+З 2 +2+2*3+2*З 2 + 5+3*5+З 2 *5+2*5+2*3*5+2*З 2 *5 = 1+3+9+2+6+18+5+15+45+10+30+90 - слагаемыми являются делители числа 90.
Решим несколько задач на тему "Число и сумма натуральных делителей натурального числа"
Задание 1. Найдите натуральное число, зная, что оно имеет только два простых делителя, что число всех делителей равно 6, а сумма всех делителей - 28.

Задания из сборника TTZ - ЕГЭ 2010. Математика. Типовые тестовые задания
Задание 2. TTZ.С6.2 Найдите все натуральные числа, которые делятся на 42 и имеют ровно 42 различных натуральных делителя (включая единицу и само число).

Задание 3. TTZ.С6.9 Найдите все натуральные числа, последняя десятичная цифра которых 0 и которые имеют ровно 15 различных натуральных делителей(включая единицу и само число).

Задание 4. SPI.С6.9. У натурального числа n ровно 6 делителей. Сумма этих делителей равна 3500. Найти n.
Решение VEk :

Задания для самостоятельной работы
SR1 . Найти все числа, имеющие ровно 2 простых делителя, всего 8 делителей, сумма которых равна 60.
SR2. Найти натуральные числа, которые делятся на 3 и на 4 и имеют ровно 21 натуральный делитель.
SR3. Найти наименьшее натуральное число, имеющее ровно 18 натуральных делителей.
SR4. Найти наименьшее число, кратное 5, имеющее 18 натуральных делителей.
SR5. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 15 делителей. Сколько делителей имеет куб этого числа?
SR6. Некоторое натуральное число имеет два простых делителя. Его квадрат имеет всего 81 делитель. Сколько делителей имеет куб этого числа?
SR7. Найти число вида m = 2 x 3 y 5 z , зная, что половина его имеет на 30 делителей меньше, треть -на 35 и пятая часть - на 42 делителя меньше, чем само число.

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

Навигация по странице.

Все делители числа, их нахождение

Дальнейшее изложение подразумевает хорошее владение информацией статьи делители и кратные числа . Мы будем говорить лишь о поиске всех делителей (). Этого вполне достаточно, так как одно из свойств делимости утверждает, что множество делителей целого отрицательного числа −a совпадает со множеством делителей a (которое будет положительным). Напомним также, что число 0 имеет бесконечно много делителей, и нахождение всех делителей нуля не представляет интереса.

положительными делителями простого числа a являются лишь единица и само это число. Следовательно, любое простое число a имеет четыре делителя, среди которых два положительных и два отрицательных: 1 , −1 , a и −a . Например, число 11 – простое, оно имеет всего четыре делителя 1 , −1 , 11 и −11 . Еще пример. Число 367 тоже простое, все его делители – это числа 1 , −1 , 367 и −367 .

Интереснее проходит поиск всех делителей составных чисел. Теоретическая основа этого процесса заключается в следующей теореме.

Теорема.

Пусть известно каноническое разложение числа на простые множители , которое имеет вид , тогда все положительные (натуральные) делители числа a – это числа вида d=p 1 t 1 ·p 2 t 2 ·…·p n t n , где t 1 =0, 1, …, s 1 , t 2 =0, 1, …, s 2 , …, t n =0, 1, …, s n .

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

С одной стороны, по определению делимости число a делится на любое такое число d , так как существует такое целое число q=p 1 (s 1 −t 1) ·p 2 (s 2 −t 2) ·…·p n (s n −t n) , что a=d·q .

С другой стороны, всякое число d , которое делит a , имеет указанный вид, так как в силу свойств делимости оно не может иметь других простых множителей, кроме p 1 , p 2 , …, p n , а показатели этих множителей не могут превышать s 1 , s 2 , …, s n соответственно.

Из рассмотренной теоремы следует алгоритм нахождения всех положительных делителей данного числа . Чтобы найти все делители числа a нужно:

• получить его каноническое разложение на простые множители вида a=p 1 s 1 ·p 2 s 2 ·…·p n s n ;
• вычислить все значения выражения p 1 t 1 ·p 2 t 2 ·…·p n t n , в которых числа t 1 , t 2 , …, t n принимают независимо друг от друга каждое из значений t 1 =0, 1, …, s 1 , t 2 =0, 1, …, s 2 , …, t n =0, 1, …, s n .

Обычно наибольшую трудность представляет именно процесс перебора всех возможных комбинаций значений чисел t 1 , t 2 , …, t n . Сейчас мы последовательно рассмотрим решения нескольких примеров нахождения всех делителей чисел, откуда будут понятны все тонкости этого процесса.

Пример.

Найдите все делители числа 8 .

Решение.

Получить разложение на простые множители числа 8 не составляет труда: 8=2·2·2 . В канонической форме это разложение выглядит так: 8=2 3 . То есть, в нашем случае a=8 , p 1 =2 , s 1 =3 .

Тогда все делители числа 8 представляют собой значения выражения p 1 t 1 =2 t 1 , в котором t 1 принимает значения 0 , 1 , 2 и 3 (3 – последнее значение, так как s 1 =3 ). Итак, при t 1 =0 имеем 2 t 1 =2 0 =1 , при t 1 =1 имеем 2 t 1 =2 1 =2 , при t 1 =2 имеем 2 t 1 =2 2 =4 , наконец, при t 1 =3 имеем 2 t 1 =2 3 =8 .

Весь процесс нахождения делителей удобно проводить, заполняя таблицу следующего вида:

Таким образом, 1 , 2 , 4 и 8 – это все положительные делители числа 8 . Отрицательными делителями числа 8 являются −1 , −2 , −4 и −8 .

Ответ:

±1 , ±2 , ±4 , ±8 – все делители числа 8 .

Рассмотрим более сложный пример нахождения всех делителей числа a , в нем разложение числа уже будет содержать два простых множителя.

Пример.

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

Решение.

Сначала разложим на простые множители число 567 :

Каноническое разложение числа 567 на простые множители имеет вид 567=3 4 ·7 . Теперь для нахождения всех натуральных делителей числа 567 заставим t 1 и t 2 пробегать независимо друг от друга значения 0 , 1 , 2 , 3 , 4 и 0 , 1 соответственно, при этом будем вычислять значения выражения 3 t 1 ·7 t 2 . Все эти действия удобно поводить, заполняя следующую таблицу:

Ответ:

1 , 3 , 7 , 9 , 21 , 27 , 63 , 81 , 189 и 567 – все натуральные делители числа 567 .

Еще немного усложним пример.

Пример.

Найдите все положительные делители числа 3 900 .

Решение.

Разложив число 3 900 на простые множители, получим его каноническое разложение 3 900=2 2 ·3·5 2 ·13 . Все положительные делители найдем, вычисляя значения выражения 2 t 1 ·3 t 2 ·5 t 3 ·13 t 4 при t 1 =0, 1, 2 , t 2 =0, 1 , t 3 =0, 1, 2 , t 4 =0, 1 .

Ответ:

1 , 2 , 3 , 4 , 5 , 6 , 10 , 12 , 13 , 15 , 20 , 25 , 26 , 30 , 39 , 50 , 52 , 60 , 65 , 75 , 78 , 100 , 130 , 150 , 156 , 195 , 260 , 300 , 325 , 390 , 650 , 780 , 975 , 1 300 , 1 950 , 3 900 - все положительные делители числа 117 000 .

Число делителей числа

Число положительных делителей данного числа a , каноническое разложение которого имеет вид a=p 1 s 1 ·p 2 s 2 ·…·p n s n , равно значению выражения (s 1 +1)·(s 2 +1)·…·(s n +1) . Величина записанного выражения дает количество всех возможных наборов переменных t 1 , t 2 , …, t n , где t 1 =0, 1, …, s 1 , t 2 =0, 1, …, s 2 , …, t n =0, 1, …, s n .

Приведем пример. Вычислим число натуральных делителей числа 3 900 из последнего примера, рассмотренного в предыдущем пункте. Мы выяснили, что 3 900=2 2 ·3·5 2 ·13 , тогда s 1 =2 , s 2 =1 , s 3 =2 , s 4 =1 . Осталось вычислить значение выражения (s 1 +1)·(s 2 +1)·(s 3 +1)·(s 4 +1) при данных значениях s 1 , s 2 , s 3 и s 4 , которое и даст нам искомое число натуральных делителей. Получаем (2+1)·(1+1)·(2+1)·(1+1)=3·2·3·2=36 . Следовательно, число 3 900 имеет 36 натуральных делителей. Если мы пересчитаем все делители числа 3 900 , полученные в предыдущем примере, то убедимся, что их количество действительно равно 36 . Число всех делителей (и положительных и отрицательных) числа 3 900 равно 36·2=72 , так как число 3 900 имеет 36 положительных делителей, и, следовательно, 36 отрицательных, противоположных каждому из положительных делителей.

Пример.

Найдите число делителей числа 84 .

Решение.

Разложим 84 на простые множители:

Таким образом, каноническое разложение имеет вид 84=2 2 ·3·7 . Тогда число положительных делителей равно (2+1)·(1+1)·(1+1)=12 . Следовательно, число всех делителей равно 2·12=24 .

Ответ:

Число 84 имеет 24 делителя.

В самом общем случае, количество возможных делителей произвольного числа бесконечно. Фактически, это все не равные нулю числа. Но если речь идет о натуральных числах, то под делителем числа 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.

Как решить задачу, если нет идеи? Нет универсального способа, позволяющего решать любые задачи. Но есть методика, дающая возможность продвинуться и в трудных ситуациях, тем более, в лёгких заданиях, которые предлагаются в тестах ЦТ. Эту методику описывает великий мастер эвристики Д. Пойа. Абутуриенту полезно с ней.
А ниже приводятся эвристические указания к решению задач первой темы курса для абитуриента. Разумеется, ими не следует пользоваться, если не сделано попыток решения более трудных для вас заданий.
Задачи.
№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. То есть их больше шести... . Найдите самостоятельно нужное разложение. А потом используйте условие и работайте с полученным равенством.

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

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

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 .