Основы теории делимости чисел
На примере решения задач С6
Делимость целых чисел
Рассмотрим множество целых чисел 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=a 1 +a 2 +…+a n-1 +a n и d делит числа m, a 1, a 2 , … a n-1 , то d│a n .
Определение. Общим делителем чисел a 1, a 2 , … a n ∈Z называется число d∈Z, являющееся делителем каждого из этих чисел. Общий делитель данных чисел называется их наибольшим общим делителем , если он делится на всякий общий делитель этих чисел.
3. Если a, b, c ∈Z, НОД(a,b)=1 и b|ac, то b│c.
- 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 полученных результата складывают. Какую наименьшую по модулю и какую наибольшую сумму можно получить в итоге?
Решение:
- Если все произведения взяты со знаком плюс, то их сумма максимальна и равна
2. Так как сумма оказалась нечетной, то число нечетных слагаемых в ней –нечетно, причем это свойство всей суммы не меняется при смене знака любого ее слагаемого. Поэтому любая из получающихся сумм будет нечетной, а значит, не будет равна 0.
3. Значение 1 сумма принимает, например, при такой расстановке знаков у произведений, которая получится при раскрытии следующих скобок:
Ответ:1 и 4131.
1 , делится на 1 и n. Определение. Число n∈N, и n1, называется простым, если оно не имеет других натуральных делителей, кроме 1 и n. Определение. Число n∈N называется составным, если оно имеет натуральный делитель, отличный от 1 и n. Замечание . Из последнего определения следует, что каждое составное число представляется в виде n=a⋅b, где a,b ∈N, 1Замечание . Число 1 не является ни простым, ни составным. ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ . Любое число n∈ N, n1, представляется в виде произведения простых чисел, причем единственным образом, если не учитывать порядок следования сомножителей. " width="640"
Рассмотрим теперь множество натуральных чисел N.
Число 1 имеет единственный натуральный делитель. Любое n∈N, и n1 , делится на 1 и n.
Определение. Число n∈N, и n1, называется простым, если оно не имеет других натуральных делителей, кроме 1 и n.
Определение. Число n∈N называется составным, если оно имеет натуральный делитель, отличный от 1 и n.
Замечание . Из последнего определения следует, что каждое составное число представляется в виде n=a⋅b, где a,b ∈N, 1
Замечание . Число 1 не является ни простым, ни составным.
ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ . Любое число n∈ N, n1, представляется в виде произведения простых чисел, причем единственным образом, если не учитывать порядок следования сомножителей.
Рассмотрим удобный способ выделения простых чисел в данном отрезке натурального ряда, известный еще греческому ученому Эратосфену (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 k ≥√N, то все оставшиеся незачеркнутыми числа будут простыми, поскольку все кратные чисел 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 и разделив полученное равенство на х, имеем 10 5 +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.
- Если 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 удовлетворяю условиям задачи.
1 число х не пятизначное. 5) Если q=8, то у=8х. Перепишем равенство (3) в виде рх=12501. При р=1 имеем: х=12501, у=100008, число у не пятизначное. При р8 число х не пятизначное. Итак, в случаях 1), 3) -5) не существует чисел х и у, удовлетворяющих условию задачи. Задача имеет единственное решение: х=16667, у=33334. Ответ: х=16667, у=33334. " width="640"
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.
n, то х – натуральное число и справедливы равенство m 2 m, n 2 n. m 2 +n 2 m+n, тогда m 2 +n 2 m-n и равенство (1) невозможно. Если m n-m= =-x(m 2 +n 2 ) (2), где -х – натуральное число. Так как для натуральных чисел m и n справедливы равенство m 2 m, 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. " width="640"
Пример 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), где х целое число.
Если mn, то х – натуральное число и справедливы равенство m 2 m, n 2 n.
m 2 +n 2 m+n, тогда m 2 +n 2 m-n и равенство (1) невозможно.
Если m
n-m= =-x(m 2 +n 2 ) (2), где -х – натуральное число.
Так как для натуральных чисел m и n справедливы равенство m 2 m, 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.
2 не имеет решений в области натуральных чисел. Свое утверждение Ферма написал на полях книги – сочинения Диофанта (3 в. н.э.) – со следующим комментарием: «Я открыл этому поистине чудесное доказательство, которое из-за недостатка места не может поместиться на этих полях». В настоящее время все специалисты твердо уверены в том, что Ферма не обладал доказательством этой теоремы и, сверх того, что элементарными методами ее нельзя доказать. " width="640"
При решении заданий вышеуказанного типа очень часто возникает следующая формулировка условия: можно ли найти такие целые положительные числа x, y, z которые удовлетворяли бы условию уравнения х n +y n =z n , где показатель n – целое число большее 2?
Французский математик и юрист Пьер Ферма (1601–1665), получивший ряд крупных результатов в области теории чисел, высказал следующее утверждение, которое называют «проблемой Ферма» или «великой теоремой Ферма»: всякое уравнение х n +y n =z n , при n 2 не имеет решений в области натуральных чисел.
Свое утверждение Ферма написал на полях книги – сочинения Диофанта (3 в. н.э.) – со следующим комментарием: «Я открыл этому поистине чудесное доказательство, которое из-за недостатка места не может поместиться на этих полях». В настоящее время все специалисты твердо уверены в том, что Ферма не обладал доказательством этой теоремы и, сверх того, что элементарными методами ее нельзя доказать.
Более трехсот лет проблема Ферма привлекала к себе внимание как крупных специалистов, так и (в связи с исключительной простотой своей постановки) многочисленных любителей математики. Она служила беспрецедентным стимулом для развития математики. При попытках ее доказать были разработаны мощные средства, приведшие к созданию обширного раздела математики – теории алгебраических чисел. С помощью сложнейшей теоретико-числовой техники теорема Ферма была проверена для всех n≤4000000, но до конца 1994 года в общем случае оставалась недоказанной. Получить ее полное доказательство удалось лишь с помощью теории эллиптических кривых.
23 июня 1993 года математик из Принстона Эндрю Уайлс, выступая на конференции по теории чисел в Кембридже (Великобритания), сделал сообщение, из которого следовало, что им получено доказательство великой теоремы Ферма. Дальнейшие события развивались драматически. В начале декабря 1993 года, за несколько дней до того, как рукопись работы Уайлса должна была пойти в печать, в его доказательстве были обнаружены пробелы. Исправление их заняло свыше года. И только летом 1995 года текст с доказательством, написанный Уайлсом в сотрудничестве с Тейлором, вышел в свет.
Пример 5. У натурального числа n ровно шесть натуральных делителей. Сумма этих делителей равна 3500. Найдите n.
Решение. Рассмотрим возможные ситуации.
а) предположим, что искомое число имеет один простой делитель кратности к. В этом случае количество делителей числа равно р=к+1 и к=5. Приняв в качестве простого делителя число 3, мы получим число 3 5 =243, сумма делителей которого равна 1+3+9+27+81+243=364
б)при наличии t простых делителей первой кратности, количество делителей числа равно р=2 t , что противоречит условию «ровно 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). Это условие выполняется в случаях:
3. 4(у 2 +у+1)+у(у+1)=3499; 5у 2 +5у+4=3499; у 2 +у-699=0; yВ группе чисел от 2 до 26 отвечают условию у ≡2 (mod 3) простые числа 2, 5, 11, 17, 23. Начав перебор с меньшего из этих чисел, на нем и завершаем поиск. Положив у=2, находим х=499 (простое число). Искомое число равно ху 2 =499*4=1996. Делители этого числа:1, 2, 4, 499, 998, 1996. Проверкой убеждаемся, что сумма этих делителей равна 3500. Ответ: 1996. " width="640"
- х≡1 (mod 3), у ≡2 (mod 3);
- х≡1 (mod 3), у ≡0 (mod 3), т. е. у=3.
Вариант 2) ошибочен, при у=3 получаем дробное значение х. Рассмотрим вариант 1), ограничив зону поиска. Определим из формулы (1) наибольшее возможное значение у, учитывая, что x3.
4(у 2 +у+1)+у(у+1)=3499; 5у 2 +5у+4=3499; у 2 +у-699=0; y
В группе чисел от 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, 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 = 2 3 7.
Принимаем m = 1, n = 2, k = 6 (вариант единственный с точностью до привязки к буквам). Искомые числа (их количество равно числу перестановок из трёх элементов P 3 = 3! = 6) равны: 2 3 2 7 6 ; 2 3 6 7 2 ; 2 2 3 7 6 ; 2 2 3 6 7; 2 6 3 7 2 ; 2 6 3 2 7.
Ответ. 2 3 2 7 6 ; 2 3 6 7 2 ; 2 2 3 7 6 ; 2 2 3 6 7; 2 6 3 7 2 ; 2 6 3 2 7
Пример 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 = 2 2 5 4 = 2500; N 2 = 2 4 5 2 = 400.
Ответ. 2500 и 400.
Пример 9. При каком наибольшем п найдется п семизначных чисел, являющихся последовательными членами одной геометрической прогрессии?
Решение. Очевидно, решая задачу, следует выполнять требование: первое член прогрессии и её знаменатель должны быть по возможности, минимальны. При этом все члены прогрессии — целые числа. Логичный, на первый взгляд, выбор числа 10 6 в качестве первого члена и знаменателя прогрессии 1,1 не приводит к успеху. Цепочка чисел заканчивается на 6-м ходу. Верный подход состоит в том, чтобы в качестве первого члена выбрать максимально возможную степень (естественно, основание степени должно быть минимально), а в качестве знаменателя прогрессии — неправильную дробь, знаменатель которой равен основанию степени первого члена, либо ближайшей степенью его, а числитель – знаменателю плюс 1. Выбираем в качестве первого члена прогрессии число 1048576 = 2 20 , а в качестве знаменателя прогрессии число 5/4. Получаем такую цепочку: 1048576, 1310720, 1638400, 2048000, 2560000, 3200000, 4000000, 5000000, 6250000, 7812500, 9765625 — всего 11 членов.
Ответ. 11.
Метод математической индукции при решении задач С6.
Пусть мы имеем бесконечную последовательность утверждений P 1 , P 2 , ..., P n , ..., занумерованных натуральными числами, причём: — утверждение P 1 истинно; — если некоторое утверждение P k истинно, то следующее утверждение P k+1 тоже истинно.
Тогда принцип математической индукции утверждает, что все утверждения последовательности истинны.
Другими словами принцип математической индукции можно сформулировать так: если в очереди первой стоит женщина, и за каждой женщиной стоит женщина, то все в очереди – женщины.
Способ рассуждений, основанный на принципе математической индукции называется методом математической индукции.
Для решения задач методом математической индукции необходимо:
- сформулировать утверждение задачи в виде последовательности утверждений P 1 , P 2 , ..., P n , ...
- доказать, что утверждение P 1 истинно (этот этап называется базой индукции);
- доказать, что если утверждение P n истинно при некотором n = k, то оно истинно и при n = k + 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.
Пример 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 − 1 + 2 − 1 = 4 * 2 2 k − 1 − 1 = 4 * 2 2 k − 1 − 4 + 3 = 4(2 2 k − 1 − 1) + 3 = 4(3 t + 1) + 3 = 12 t + 7 = 3(4 t + 2) + 1 - не делится нацело на, давая остаток 1.
Выполнив оба пункта, мы доказали утверждение методом математической индукции. Так как при нечентых n левая часть равенства (1) не делится на 3, а правая делится на 3 всегда, то равенство не выполняется.
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 = 0 + 1 = 1. Подставив в изначальное уравнение, получим 2 n = 3 1 + 1, 2 n = 4, n = 2 Ответ: m=1, n=2 " width="640"
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, qp. 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 = 0 + 1 = 1. Подставив в изначальное уравнение, получим
2 n = 3 1 + 1, 2 n = 4, n = 2
Ответ: m=1, n=2
1, что произведение некоторых n последовательных натуральных чисел равно произведению некоторых n+100 последовательных натуральных чисел. Типичная олимпиадная задача, связанная с теорией чисел, причем сложная. В таких задачах, когда непонятно, как ее решать, необходимо попытаться решить самый простой случай. Можно, например, принять n=2, но в данном случае этого делать нельзя. В задаче сказано, что доказать существование такого n, которое бы удовлетворяло условию. Из этого следует, что возможно не для всякого n можно найти такие последовательности и может оказать, что при n=2 задача не имеет решений и тогда мы просто потеряем время. Будем упрощать с другой стороны - будем считать, что последовательность из 100+n чисел начинается с 1. То есть это последовательность 1,2,3...100+n. " width="640"
Пример 11. Докажите, что найдется такое натуральное число n1, что произведение некоторых n последовательных натуральных чисел равно произведению некоторых n+100 последовательных натуральных чисел.
Типичная олимпиадная задача, связанная с теорией чисел, причем сложная. В таких задачах, когда непонятно, как ее решать, необходимо попытаться решить самый простой случай. Можно, например, принять n=2, но в данном случае этого делать нельзя. В задаче сказано, что доказать существование такого n, которое бы удовлетворяло условию. Из этого следует, что возможно не для всякого n можно найти такие последовательности и может оказать, что при n=2 задача не имеет решений и тогда мы просто потеряем время. Будем упрощать с другой стороны - будем считать, что последовательность из 100+n чисел начинается с 1. То есть это последовательность 1,2,3...100+n.
Для дальнейшего решения необходимо понять идею задачи. В данном случае она заключается в следующем: пусть все элементы кроме последнего последовательности из n элементов совпадают с элементами большей последовательности. То есть это последовательность 101, 102, 103... 101+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, а с любого другого числа.