О СНОВЫ ТЕОРИИ ДЕЛИМОСТИ ЧИСЕЛ На примере решения задач С6

Д ЕЛИМОСТЬ ЦЕЛЫХ ЧИСЕЛ Рассмотрим множество целых чисел Z. Операция деления выполняется не для всех пар чисел из Z. Определение. Число а Z делится на число b Z (b0), если существует такое число q Z, что a=bq. Замечание. Вместо выражения «а делится на b» очень часто используется фраза «число b делит число а» и при этом применяется запись. a|b Если а делится на b, то b называется делителем а, само а называется кратным числа b. Число q называется частным от деления а на b. Число 0 делится на любое b0. Если a0, то, очевидно, что множество всех делителей а конечно. Рассмотрим простейшие свойства делимости целых чисел.

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

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

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

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

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

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

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

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

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

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

Пример 5. У натурального числа n ровно шесть натуральных делителей. Сумма этих делителей равна Найдите n. Решение. Рассмотрим возможные ситуации. а) предположим, что искомое число имеет один простой делитель кратности к. В этом случае количество делителей числа равно р=к+1 и к=5. Приняв в качестве простого делителя число 3, мы получим число 3 5 =243, сумма делителей которого равна =364

1)х1 (mod 3), у 2 (mod 3); 2) х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

Комментарии. Поясним, откуда берутся формулы для подсчета числа делителей в случаях а), б) и в). а) Если некоторое число имеет один простой делитель m кратности k, то оно делится на каждое из чисел 1, m 1, m 2, …, m k, т. е. это число имеет k + 1 делителей. б) Если некоторое число имеет t простых делителей первой кратности m 1, m 2,..., m t, то оно делится на 1, m 1, m 2,..., m t, m 1 m 2, m 1 m 3,..., m 1 m t, m 1 m 2 m 3,..., m 1 m 2, …, m 1 m 2 m 3 … m t. в) Если простые делители m и n некоторого числа имеют кратности a и b, то это число делится на каждое из чисел, записанных в следующих двух строках 1, m 1, m 2, …, m a, 1, n 1, 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 = Принимаем m = 1, n = 2, k = 6 (вариант единственный с точностью до привязки к буквам). Искомые числа (их количество равно числу перестановок из трёх элементов P 3 = 3! = 6) равны: ; ; ; ; ; Ответ ; ; ; ; ;

Пример 7. Решите уравнение 3 m + 4 n = 5 k в натуральных числах. Решение. Левая часть уравнения при любых натуральных m и n при делении на 3 даёт остаток 1, следовательно, такой же остаток при делении на 3 должен быть и у 5 k, откуда следует, что k чётное. Пусть k = 2 r, r натуральное число. Правая часть уравнения при любом натуральном k при делении на 4 даёт остаток 1, следовательно, такой же остаток при делении на 4 должен быть и у 3 m, откуда следует, что m чётное. Пусть m = 2 s, s натуральное число. Перепишем исходное уравнение в виде 3 2s + 4 n = 5 2 r, или в виде 2 2 n = (5 r – 3 s )(5 r + 3 s ). Тогда 5 r – 3 s = 2 q и 5 r + 3 s = 2 l, где q и l целые неотрицательные числа и q + l = 2 n. Таким образом, 5 r = (2 q + 2 l ):2, 3 s = (2 l – 2 q ):2 = 2 l – 1 – 2 q – 1. Число 3 s нечётное, значит, 2 l – 1 – 2 q – 1 нечётно, поэтому q = 1 и 3 s = 2 l – 1 – 1. Следовательно, число l – 1 чётно, l – 1 = 2 p (иначе левая часть не делится на 3). Тогда 3 s = = (2 p – 1)(2 p + 1) произведение двух множителей, отличающихся на 2 и являющихся степенями тройки. Ясно, что эти множители 1 и 3, тогда p = 1, s = 1, m = 2 s = 2. Далее последовательно получаем: l = 2 p + 1 = 3, 5 r = (2 q + 2 l ):2 = 5, r = 1, k = 2 r =2, q + l = 2 n = 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 (единственное решение без привязки к конкретным множителям). Существуют два числа, удовлетворяющие условию: N 1 = = 2500; N 2 = = 400. Ответ и 400.

Пример 9. При каком наибольшем п найдется п семизначных чисел, являющихся последовательными членами одной геометрической прогрессии? Решение. Очевидно, решая задачу, следует выполнять требование: первое член прогрессии и её знаменатель должны быть по возможности, минимальны. При этом все члены прогрессии целые числа. Логичный, на первый взгляд, выбор числа 10 6 в качестве первого члена и знаменателя прогрессии 1,1 не приводит к успеху. Цепочка чисел заканчивается на 6-м ходу. Верный подход состоит в том, чтобы в качестве первого члена выбрать максимально возможную степень (естественно, основание степени должно быть минимально), а в качестве знаменателя прогрессии неправильную дробь, знаменатель которой равен основанию степени первого члена, либо ближайшей степенью его, а числитель – знаменателю плюс 1. Выбираем в качестве первого члена прогрессии число = 2 20, а в качестве знаменателя прогрессии число 5/4. Получаем такую цепочку: , , , , , , , , , , всего 11 членов. Ответ. 11.

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

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

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

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

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

Для дальнейшего решения необходимо понять идею задачи. В данном случае она заключается в следующем: пусть все элементы кроме последнего последовательности из n элементов совпадают с элементами большей последовательности. То есть это последовательность 101, 102, n. Обозначим произведение общих элементов последовательности за k. Тогда произведение элементов последовательность равны 1*2*3...*99*100*k и k*(101+n). По условию они должны быть равны: 1*2*3...*99*100*k=k*(101+n), значит 101+n=1*2*3...*99*100=100!. n=100!-101. Нужное число найдено, утверждение доказано. Зная доказательство этого частного случая, можно доказать точно так же для более общих случаев, когда последовательность начинается не с 1, а с любого другого числа.