Основы теории делимости чисел

Делимость целых чисел
Рассмотрим множество целых чисел Z. Операция деления выполняется не для всех пар чисел из Z.
Определение. Число а∈ Z делится на число b∈Z (b≠0), если существует такое число q∈Z, что a=bq.
Замечание. Вместо выражения «а делится на b» очень часто используется фраза «число b делит число а» и при этом применяется запись . a|b
Если а делится на b, то b называется делителем а, само а называется кратным числа b. Число q называется частным от деления а на b.
Число 0 делится на любое b≠0. Если a≠0, то, очевидно, что множество всех делителей а конечно.
Рассмотрим простейшие свойства делимости целых чисел.

1. Если с│b и b│a, то с│а.
2. Если m=a+b, d│a и d│a то d│b.
Замечание. Аналогично доказывается, что если m=a1+a2+…+an-1+an и d делит числа m, a1, a2, … an-1, то d│an .
Определение. Общим делителем чисел a1, a2, … an∈Z называется число d∈Z, являющееся делителем каждого из этих чисел. Общий делитель данных чисел называется их наибольшим общим делителем, если он делится на всякий общий делитель этих чисел.
3. Если a, b, c ∈Z, НОД(a,b)=1 и b|ac, то b│c.
4. Если b∈Z взаимно просто с каждым из a1, a2, … an∈Z , то b взаимно просто с их произведением a1*a2*…*an.

Пример 1. Каждое из чисел 2, 3, …, 7 умножают на каждое из чисел 13, 14, …, 21 и перед каждым из полученных произведений произвольным образом ставят знак плюс или минус, после чего все 54 полученных результата складывают. Какую наименьшую по модулю и какую наибольшую сумму можно получить в итоге?
Решение:
Если все произведения взяты со знаком плюс, то их сумма максимальна и равна
2. Так как сумма оказалась нечетной, то число нечетных слагаемых в ней –нечетно, причем это свойство всей суммы не меняется при смене знака любого ее слагаемого. Поэтому любая из получающихся сумм будет нечетной, а значит, не будет равна 0.
3. Значение 1 сумма принимает, например, при такой расстановке знаков у произведений, которая получится при раскрытии следующих скобок:
Ответ:1 и 4131.

Рассмотрим теперь множество натуральных чисел N.
Число 1 имеет единственный натуральный делитель. Любое n∈N, и n>1 , делится на 1 и n.
Определение. Число n∈N, и n>1, называется простым, если оно не имеет других натуральных делителей, кроме 1 и n.
Определение. Число n∈N называется составным, если оно имеет натуральный делитель, отличный от 1 и n.
Замечание. Из последнего определения следует, что каждое составное число представляется в виде n=a⋅b, где a,b ∈N, 1
Замечание. Число 1 не является ни простым, ни составным.
ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ. Любое число n∈ N, n>1, представляется в виде произведения простых чисел, причем единственным образом, если не учитывать порядок следования сомножителей.

Рассмотрим удобный способ выделения простых чисел в данном отрезке натурального ряда, известный еще греческому ученому Эратосфену (276–194 г.г. до н.э.). Он состоит в отсеивании составных чисел, находящихся в данном отрезке, и носит название «решета Эратосфена».
Напишем одно за другим числа 2, 3,4,…,N. Число 2, являющееся простым, оставляем и зачеркиваем после него все четные числа. Первое следующее за 2 незачеркнутое число есть 3. Оно не делится на 2. Значит, оно не имеет делителей, отличных от 1 и 3, и поэтому является простым. Оставляем 3 и зачеркиваем после него все числа, кратные 3. Продолжая этот процесс, найдем все простые числа, не превосходящие некоторого простого числа pk. При этом будут зачеркнуты все составные числа, кратные 2, 3… pk. Первое незачеркнутое после pk число будет простым числом pk+1, так как оно не делится на 2, 3… pk и поэтому имеет своими делителями только 1 и pk+1. Если найдено pk ≥√N, то все оставшиеся незачеркнутыми числа будут простыми, поскольку все кратные чисел 2, 3… pk уже вычеркнуты.

Пример 2. Найдите все тройки натуральных чисел k, m и n , удовлетворяющие уравнению
Ответ: k=1, n=2, m=3; k=n=3 m=4; k=2, n=1, m=3.

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

Пример 3. Найдите все пары пятизначных чисел х, у, такие что число ху, полученное приписыванием десятичной записи числа у после десятичной записи числа х, делится на ху.
Решение. По условию задачи число ху=105 х+у делится на ху, т. Е. верно равенство 105 х+у=рху (1) , где р-натуральное число.
Перепишем равенство (1) в виде 105 х=(рх-1)у (2).
Так как рх-1 не делится на х, то у делится на х, о есть у=qx, где q- натуральное число, меньшее 10 ( в противном случае у не пятизначное число).
Заменив в равенстве (1) у на qx и разделив полученное равенство на х, имеем 105 +q=pqx. (3)
Так как 105 =(px-1)q, то 105 делится на q. Число 105 имеет делители, меньшие 10: 1, 2, 4, 5, 8. Рассмотрим случаи q=1, q=2, q=4, q=5, q=8.
Если q=1, то равенство (3) имеет вид: рх=100001. Первыми делителями числа 100001 является 1 и 11, но при р=1 и при р≥11 число х не пятизначное.
Если q=2, то у=2х. Перепишем равенство (3) в виде рх=50001. Первыми делителями числа 50001 являются числа 1, 3 и 7.
При р=1 имеем: х=50001, у=100002, число у не пятизначное.
При р=3 имеем: х=16667, у=2*16667=33334.
При р≥7 число х не пятизначное.
Итак, числа х=16667, у =33334 удовлетворяю условиям задачи.

3) Если q=4, то у=4х. Перепишем равенство (3) в виде рх=25001. Первыми делителями 25001 являются 1 и 23.
При р=1 имеем: х=25001, у=100004, число у не пятизначное.
При р≥23 число х не пятизначное.
4) Если q=5, то у=5х. Из равенства (3) следует, что рх=20001.
При р=1 имеем: х=20001, у=100005, число у не пятизначное.
При р>1 число х не пятизначное.
5) Если q=8, то у=8х. Перепишем равенство (3) в виде рх=12501.
При р=1 имеем: х=12501, у=100008, число у не пятизначное.
При р>8 число х не пятизначное.
Итак, в случаях 1), 3) -5) не существует чисел х и у, удовлетворяющих условию задачи. Задача имеет единственное решение: х=16667, у=33334.
Ответ: х=16667, у=33334.

Пример 4. Натуральные числа m и n таковы, что и m3 +n, и m+m3 делится на m2+n2. Найди те m и n.
Решение. Так как каждое из чисел m3 +n, и m+m3 делится на m2+n2, то их разность m-n тоже делится на m2+n2, т. е. справедливо равенство
m-n=x(m2+n2) (1), где х целое число.
Если m>n, то х – натуральное число и справедливы равенство m2>m, n2>n.
m2+n2 >m+n, тогда m2+n2 >m-n и равенство (1) невозможно.
Если m
n-m= =-x(m2+n2) (2), где -х – натуральное число.
Так как для натуральных чисел m и n справедливы равенство m2>m, n2>n.
m2+n2 >m+n, тогда m2+n2 >m-n и равенство (2) невозможно.
Следовательно, m=n. Перепишем условие задачи «m+m3 делится на m2+n2», т. е. на 2m2 в виде
m+m3 =2у m2 . (3)
Где у – натуральное число.
Разделив равенство (3) на натуральное число m, получим равенство
1+m2=2ym,
которое перепишем в виде
(2y-m)m=1. (4)
Для натуральных чисел m и 2y-m равенство (4) верно лишь при условии m=1 и у=1. Мы получили единственное решение задачи: m=n=1.
Ответ: m=n=1.

При решении заданий вышеуказанного типа очень часто возникает следующая формулировка условия: можно ли найти такие целые положительные числа x, y, z которые удовлетворяли бы условию уравнения хn+yn=zn , где показатель n – целое число большее 2?
Французский математик и юрист Пьер Ферма (1601–1665), получивший ряд крупных результатов в области теории чисел, высказал следующее утверждение, которое называют «проблемой Ферма» или «великой теоремой Ферма»: всякое уравнение хn+yn=zn , при n> 2 не имеет решений в области натуральных чисел.
Свое утверждение Ферма написал на полях книги – сочинения Диофанта (3 в. н.э.) – со следующим комментарием: «Я открыл этому поистине чудесное доказательство, которое из-за недостатка места не может поместиться на этих полях». В настоящее время все специалисты твердо уверены в том, что Ферма не обладал доказательством этой теоремы и, сверх того, что элементарными методами ее нельзя доказать.

Более трехсот лет проблема Ферма привлекала к себе внимание как крупных специалистов, так и (в связи с исключительной простотой своей постановки) многочисленных любителей математики. Она служила беспрецедентным стимулом для развития математики. При попытках ее доказать были разработаны мощные средства, приведшие к созданию обширного раздела математики – теории алгебраических чисел. С помощью сложнейшей теоретико-числовой техники теорема Ферма была проверена для всех n≤4000000, но до конца 1994 года в общем случае оставалась недоказанной. Получить ее полное доказательство удалось лишь с помощью теории эллиптических кривых.
23 июня 1993 года математик из Принстона Эндрю Уайлс, выступая на конференции по теории чисел в Кембридже (Великобритания), сделал сообщение, из которого следовало, что им получено доказательство великой теоремы Ферма. Дальнейшие события развивались драматически. В начале декабря 1993 года, за несколько дней до того, как рукопись работы Уайлса должна была пойти в печать, в его доказательстве были обнаружены пробелы. Исправление их заняло свыше года. И только летом 1995 года текст с доказательством, написанный Уайлсом в сотрудничестве с Тейлором, вышел в свет.

Пример 5. У натурального числа n ровно шесть натуральных делителей. Сумма этих делителей равна 3500. Найдите n.
Решение. Рассмотрим возможные ситуации.
а) предположим, что искомое число имеет один простой делитель кратности к. В этом случае количество делителей числа равно р=к+1 и к=5. Приняв в качестве простого делителя число 3, мы получим число 35=243, сумма делителей которого равна 1+3+9+27+81+243=364<3500, в случае простого делителя 5 сумма делителей превысит указанную величину. Предположение ошибочно. Для к=2 сумма делителей окажется и подавно меньше заданной, для к=5 – и подавно больше.
б)при наличии t простых делителей первой кратности, количество делителей числа равно р=2t, что противоречит условию «ровно 6 натуральных делителей».
в)пусть искомое число содержит два простых делителя (по количеству простых делителей числа 6) кратностей a и b.Количество делителей числа равно р=(а+1)(b+1)=6. Отсюда, a=1, b=2 – единственное решение. Обозначим простые делители искомого числа х и у. По условию 1+х+у+ху+у2+ху2=3500, откуда получим, что
х(у2+у+1)+у(у+1)=3499. (1)
3499≡1(mod 3) ( т. е. целое число 3499 сравнимо с целым число 1 по модулю натурального числа 3). Соответственно, х(у2+у+1)+у(у+1)≡1 (mod 3). Это условие выполняется в случаях:

х≡1 (mod 3), у ≡2 (mod 3);
х≡1 (mod 3), у ≡0 (mod 3), т. е. у=3.
Вариант 2) ошибочен, при у=3 получаем дробное значение х. Рассмотрим вариант 1), ограничив зону поиска. Определим из формулы (1) наибольшее возможное значение у, учитывая, что x>3.
4(у2+у+1)+у(у+1)=3499; 5у2+5у+4=3499; у2+у-699=0; y<26.
В группе чисел от 2 до 26 отвечают условию у ≡2 (mod 3) простые числа 2, 5, 11, 17, 23. Начав перебор с меньшего из этих чисел, на нем и завершаем поиск.
Положив у=2, находим х=499 (простое число). Искомое число равно ху2=499*4=1996. Делители этого числа:1, 2, 4, 499, 998, 1996. Проверкой убеждаемся, что сумма этих делителей равна 3500.
Ответ: 1996.

Комментарии. Поясним, откуда берутся формулы для подсчета числа делителей в случаях а), б) и в).
а) Если некоторое число имеет один простой делитель m кратности k, то оно делится на каждое из чисел 1, m1, m2, … , m k, т. е. это число имеет k + 1 делителей.
б) Если некоторое число имеет t простых делителей первой кратности m1, m2, ..., mt, то оно делится на
1, m1, m2, ..., mt,
m1m2, m1m3, ..., m1mt,
m1m2m3, ..., m1m2, …,
m1m2m3…mt.
в) Если простые делители m и n некоторого числа имеют кратности a и b, то это число делится на каждое из чисел, записанных в следующих двух строках
1, m1, m2, … , m a,
1, n1, n 2, … , n b,
а также на все возможные произведения чисел, взятых по одному из каждой строки. Так как в первой строке a + 1 число, а во второй — b + 1 число, то всего делителей p = (a + 1)(b + 1).

Пример 6. Найдите все натуральные числа, которые делятся на 42 и имеют ровно 42 различных натуральных делителя (включая единицу и само число).
Решение. Искомые числа делятся на 42 и имеют, по крайней мере, простые делители 2, 3 и 7. Обозначив кратности этих делителей (без привязки к ним) m, n и k, найдём эти кратности из уравнения для количества делителей числа:
N = (m + 1)(n + 1)(k + 1) = 42 = 2⋅3⋅7.
Принимаем m = 1, n = 2, k = 6 (вариант единственный с точностью до привязки к буквам). Искомые числа (их количество равно числу перестановок из трёх элементов P3 = 3! = 6) равны: 2⋅32⋅76; 2⋅36⋅72; 22⋅3⋅76; 22⋅36⋅7; 26⋅3⋅72; 26⋅32⋅7.
Ответ. 2⋅32⋅76; 2⋅36⋅72; 22⋅3⋅76; 22⋅36⋅7; 26⋅3⋅72; 26⋅32⋅7

Пример 7. Решите уравнение 3m + 4n = 5k в натуральных числах.
Решение. Левая часть уравнения при любых натуральных m и n при делении на 3 даёт остаток 1, следовательно, такой же остаток при делении на 3 должен быть и у 5k, откуда следует, что k — чётное. Пусть k = 2r, r — натуральное число.
Правая часть уравнения при любом натуральном k при делении на 4 даёт остаток 1, следовательно, такой же остаток при делении на 4 должен быть и у 3m, откуда следует, что m — чётное. Пусть m = 2s, s — натуральное число.
Перепишем исходное уравнение в виде 32s + 4n = 52r, или в виде 22n = (5r – 3s)(5r + 3s). Тогда
5r – 3s = 2q и 5r + 3s = 2l, где q и l — целые неотрицательные числа и q + l = 2n. Таким образом,
5r = (2q + 2l):2, 3s = (2l – 2q):2 = 2l – 1 – 2q – 1.
Число 3s — нечётное, значит, 2l – 1 – 2q – 1 нечётно, поэтому q = 1 и 3s = 2l – 1 – 1. Следовательно, число l – 1 чётно, l – 1 = 2p (иначе левая часть не делится на 3). Тогда 3s =
= (2p – 1)(2p + 1) — произведение двух множителей, отличающихся на 2 и являющихся степенями тройки. Ясно, что эти множители 1 и 3, тогда p = 1, s = 1, m = 2s = 2. Далее последовательно получаем: l = 2p + 1 = 3, 5r = (2q + 2l):2 = 5, r = 1, k = 2r =2, q + l = 2n = 4. Итак, m = n = k = 2.
Ответ. m = 2, n = 2, k = 2.

Пример 8. Найдите все натуральные числа, последняя десятичная цифра которых 0 и которые имеют ровно 15 различных натуральных делителей (включая единицу и само число).
Решение. Здесь невозможно ограничиться одним простым делителем кратности k = 15 — 1, поскольку по условию должны быть, по меньшей мере, два простых делителя — 2 и 5. Если ограничиться выбором только этих двух делителей, их кратности в искомых числах дает формула p = (m + 1)(n + 1), где p — количество делителей числа, равное 15, m и n — кратности простых делителей. (m + 1)(n + 1) = 15; m = 2, n = 4 (единственное решение без привязки к конкретным множителям). Существуют два числа, удовлетворяющие условию: N1 = 22⋅54 = 2500;
N2 = 24⋅52 = 400.
Ответ. 2500 и 400.

Пример 9. При каком наибольшем п найдется п семизначных чисел, являющихся последовательными членами одной геометрической прогрессии?
Решение. Очевидно, решая задачу, следует выполнять требование: первое член прогрессии и её знаменатель должны быть по возможности, минимальны. При этом все члены прогрессии — целые числа. Логичный, на первый взгляд, выбор числа 106 в качестве первого члена и знаменателя прогрессии 1,1 не приводит к успеху. Цепочка чисел заканчивается на 6-м ходу. Верный подход состоит в том, чтобы в качестве первого члена выбрать максимально возможную степень (естественно, основание степени должно быть минимально), а в качестве знаменателя прогрессии — неправильную дробь, знаменатель которой равен основанию степени первого члена, либо ближайшей степенью его, а числитель – знаменателю плюс 1. Выбираем в качестве первого члена прогрессии число 1048576 = 220, а в качестве знаменателя прогрессии число 5/4. Получаем такую цепочку: 1048576, 1310720, 1638400, 2048000, 2560000, 3200000, 4000000, 5000000, 6250000, 7812500, 9765625 — всего 11 членов.
Ответ. 11.

Метод математической индукции при решении задач С6.
Пусть мы имеем бесконечную последовательность утверждений P1, P2, ..., Pn, ..., занумерованных натуральными числами, причём: — утверждение P1 истинно; — если некоторое утверждение Pk истинно, то следующее утверждение Pk+1 тоже истинно.
Тогда принцип математической индукции утверждает, что все утверждения последовательности истинны.
Другими словами принцип математической индукции можно сформулировать так: если в очереди первой стоит женщина, и за каждой женщиной стоит женщина, то все в очереди – женщины.
Способ рассуждений, основанный на принципе математической индукции называется методом математической индукции.

Для примера докажем по индукции следующее равенство (которое, конечно, допускает и другие доказательства):
1 + 2 + 3 + ... + n = n(n + 1)/2.
База. При n = 1 равенство превращается в тождество 1 = 1·(1 + 1)/2. Шаг. Пусть равенство выполнено при n = k: 1 + 2 + 3 + ... + k = k(k + 1)/2. Прибавим к обеим частям этого равенства k + 1. В левой части мы получим сумму 1 + 2+ 3 + ... + k + (k + 1), а в правой - k(k+1)/2+(k+1)=(k(k+1)+2(k+1))/2=((k+2)(k+1))/2. Итак, 1 + 2 + 3 + ... + k + (k + 1) = (k + 1)(k + 2)/2, а это и есть требуемое равенство при n = k + 1.
Для решения задач методом математической индукции необходимо:
сформулировать утверждение задачи в виде последовательности утверждений P1, P2, ..., Pn, ...
доказать, что утверждение P1 истинно (этот этап называется базой индукции);
доказать, что если утверждение Pn истинно при некотором n = k, то оно истинно и при n = k + 1 (этот этап называется шагом индукции).

Пример 10. Решить уравнение 2n = 3m + 1, n и m – натуральные.
Решение: Перепишем уравнение в виде 2n − 1 = 3m (1). Рассмотрим два случая - когда n-нечетное и когда n-четное.
1) n-нечетное, т.е. n=2k-1. Докажем, что 22k -1 − 1 не делится нацело на 3, давая остаток 1, при натуральных k методом математической индукции. Для доказательства методом математической индукции необходимо выполнить два пункта - доказать утверждение при наименьшем k, и доказать, что есть утверждение выполняется для какого-либо k, то оно выполняется и для k+1.
Первый пункт выполняется элементарно: пусть k=1, тогда
- не делится нацело на три, давая остаток 1.
Второй пункт: пусть 22k − 1 − 1 не делится на 3, давая остаток 1. Это означает, что 22k − 1 − 1 = 3t + 1.
Тогда 22(k + 1) − 1 − 1 = 22k − 1 + 2 − 1 = 4 * 22k − 1 − 1 = 4 * 22k − 1 − 4 + 3 = 4(22k − 1 − 1) + 3 = 4(3t + 1) + 3 = 12t + 7 = 3(4t + 2) + 1 - не делится нацело на, давая остаток 1.
Выполнив оба пункта, мы доказали утверждение методом математической индукции. Так как при нечентых n левая часть равенства (1) не делится на 3, а правая делится на 3 всегда, то равенство не выполняется.

2) n-четное, т.е. n=2k. Тогда применив формулу разности квадратов к левой части получим равенство (2k − 1)(2k + 1) = 3m. Так как правая часть равенства - целая степень числа 3, то левая тоже должна быть целой степенью 3. Значит,
2k − 1 = 3p,2k + 1 = 3q, где p+q=m, q>p. 3q − 3p = 2k + 1 − (2k − 1) = 2. Вынесем за скобки 3p. Получаем
3p(3q − p − 1) = 2.
как все числа целые, то такое возможно если один из множителей равен 1, а второй 2. Первый множитель не может равняться 2, т.к. является степенью 3. Получаем, что
3p = 1, p = 0.
Тогда
(3q − p − 1) = 2, 3q − p = 3, q − p = 1, q = 1, m = p + q = 0 + 1 = 1. Подставив в изначальное уравнение, получим
2n = 31 + 1, 2n = 4, n = 2
Ответ: m=1, n=2

Пример 11. Докажите, что найдется такое натуральное число n>1, что произведение некоторых n последовательных натуральных чисел равно произведению некоторых n+100 последовательных натуральных чисел.
Типичная олимпиадная задача, связанная с теорией чисел, причем сложная. В таких задачах, когда непонятно, как ее решать, необходимо попытаться решить самый простой случай. Можно, например, принять n=2, но в данном случае этого делать нельзя. В задаче сказано, что доказать существование такого n, которое бы удовлетворяло условию. Из этого следует, что возможно не для всякого n можно найти такие последовательности и может оказать, что при n=2 задача не имеет решений и тогда мы просто потеряем время. Будем упрощать с другой стороны - будем считать, что последовательность из 100+n чисел начинается с 1. То есть это последовательность 1,2,3...100+n.