Докажите что если произведение нескольких множителей делится на простое число p

Основная теорема арифметики

Ее обычно формулируют так:

всякое натуральное число, отличное от 1, единственным образом представляется в виде произведения простых чисел

всякое натуральное число единственным образом представляется в виде произведения степеней разных простых чисел

последнее разложение часто называют каноническим, хотя и не всегда, требуя при этом, чтобы простые множители входили в это разложение в порядке возрастания.

При этом всегда подразумевается, что порядок этих множителей является несущественным, так что два таких представления, отличающиеся только порядком множителей, считаются совпадающими: например, 12=2x2x3=2x3x2=3x2x2 это одно и то же разложение числа 12, и именно такое понимание позволяет говорить о единственности разложения числа на простые множители. Еще одна тонкость в формулировке основной теоремы, быть может, не слишком заметная, но существенная для ее правильного понимания, рассматривается в статье «Крайние случаи в математике».

Основная теорема арифметики в школьном курсе не доказывается, т.е. принимается без доказательства, но ее можно неограниченно использовать. Более того, разрешается считать очевидными некоторые ее следствия, которые при этом также разрешается не доказывать. Так, очевидным можно считать часто используемое утверждение:

Если произведение двух целых чисел делится на простое число р, то хотя бы одно из этих чисел делится на р.

Это утверждение — одношаговое следствие основной теоремы арифметики: если произведение ab делится на с, то в его каноническом разложении есть множитель р, а попал он в это произведение либо от а, либо от b, а стало быть, р содержится в разложении на простые одного из чисел а и b — оно и делится на р.

После этого рассуждения легко понять, почему для числа р, не являющегося простым, аналогичное утверждение неверно: если р составное, то у него по крайней мере есть два простых множителя, один из которых может входить только в разложение а, а другой — только в разложение b. Соответствующий простейший пример очевиден: р=6, а=2, b=3.

Из основной теоремы арифметики следует совершенно необходимое для решения задач утверждение:

если натуральное число а делится на натуральные числа b и с, и числа b и с взаимно просты, то а делится на произведение bс.

В самом деле, в разложении числа а на простые множители имеются все простые множители, входящие в разложение числа b, причем с не меньшими, чем в b, показателями степени, и то же самое касается числа с. Но поскольку числа b и с взаимно просты, т.е. не имеют общих множителей, то в разложении числа а автоматически появляются все множители произведения bс в соответствующих степенях, так что а делится на bс, что и требовалось доказать.

Очень важно помнить, что это утверждение перестает быть истинным, если не предполагать, что b и с взаимно просты: например, 18 делится на 6 и на 9, но не делится на 6×9=54. Можно привести и еще более простой хотя и несколько «вырожденный» пример: 2 делится на 2, но 2 не делится на 2×2=4.

Из основной теоремы арифметики также следует критерий делимости одного числа на другое, основанный на знании канонических разложений этих чисел:

Число а делится на число b тогда и только тогда, когда все простые множители, входящие в разложение числа b, входят и в разложение числа а, причем с показателем степени, не меньшим чем в b.

Источник

Докажите что если произведение нескольких множителей делится на простое число p

Основная теорема арифметики гласит, что любое натуральное число можно разложить на простые множители, и что это разложение единственно: любое другое разложение того же числа состоит ровно из тех же простых множителей, разве что поставленных в другом порядке.

У ОТА (Основной Теоремы Арифметики) есть две части: существование разложения на простые множители, и его единственность. Существование доказать тривиально по индукции, и тут проблем или вариантов нет. Предположим, что мы уже доказали существование для всех чисел меньше n. Если n простое, то оно само себе разложение, доказывать нечего. Иначе n = a*b, где a и b какие-то числа меньше его. По предположению индукции у каждого из них есть разложение; соединяя эти разложения вместе, получаем разложение для n.

Итак, предположим, что ни одно p не равно ни одному q. На этом месте доказательства ОТА делятся на две группы: те, которые доказывают с помощью леммы Евклида, и те, которые доказывают напрямую по индукции.

Лемма Евклида гласит следующее: если простое число p делит произведение a*b (p|a*b), то p делит отдельно a или b (или оба): p|a или p|b. Эта лемма была известна Евклиду и появляется именно в таком виде в 7-й книге его Начал.

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

1. Сначала опишу более элегантное, на мой взгляд. Это доказательство принадлежит Цермело, он опубликовал его в 1934 году, но упомянул тогда же, что нашел его еще примерно в 1912-м.

2. Теперь второе доказательство по индукции.

Доказательство Цермело мне понравилось.

Мне ещё вот что показалось любопытным: у леммы Евклида ведь тоже есть несколько доказательств. Я правильно понимаю, что Евклид доказывал её, опираясь на алгоритм Евклида, а про соотношение Безу он не знал? А меж тем, только доказательство через соотношение Безу обобщается на кольца главных идеалов — сам Евклид дальше своих колец бы не уехал 😉

Я до сих пор пытаюсь разобраться, как именно Евклид доказывает лемму Евклида, и строго ли это доказательство. Может, напишу об этом отдельно. Это сложно понять, потому что под a/b = c/d он понимает что-то довольно сложное и имеющее нетривиальную структуру, но это описывается несколько туманным языком (ad = bc это у него следствие данного равенства, а не определение).

Кажется, он опирается на существование НОД, но не его выражение в виде линейной комбинации (в этом уверен).

ТЕОРЕМА. Пусть a/b дробь с минимальным представлением в том смысле, что для любой c/d так, что a/b = c/d, b Edited at 2013-02-05 19:56 (UTC)

Источник

Докажите что если произведение нескольких множителей делится на простое число p

2. Применение к основной теореме арифметики

Тот факт, что d = (а, b) всегда может быть записано в форме d = ka + lb, позволит нам привести доказательство основной теоремы арифметики, отличное от того, которое было изложено на стр. 47. Сначала в качестве леммы мы докажем следствие, приведенное на стр. 48, а затем уже из него выведем теорему. Таким образом, ход мыслей будет теперь противоположен прежнему.

Лемма. Если произведение ab делится на простое число р, то или а, или b делится на р.

Предположим, что а не делится на р; тогда (а, р) = 1, так как р имеет лишь два делителя: р и 1. В таком случае можно найти такие целые числа k и l, что

Умножая обе части равенства на b, получим:

Так как ab делится на р, то можно написать

и отсюда ясно, что b делится на р. Таким образом, мы установили, что если ab делится на р, но а не делится, то b непременно делится на р; значит, во всяком случае, или а, или b делится на р, раз ab делится на р.

Обобщение на случай произведения трех или большего числа множителей не представляет труда. Например, если abc делится на р, то достаточно дважды применить лемму, чтобы получить заключение, что по меньшей мере один из трех множителей а, b и с делится на р. В самом деле, если р не делит ни а, ни b, ни с, то не делит ab и, следовательно, не делит (ab) с = abc.

Упражнение. Обобщение этого рассуждения на случай произведения из произвольного числа n множителей требует явного или неявного применения принципа математической индукции Воспроизведите все детали соответствующих рассуждений.

Из полученного результата немедленно получается основная теорема арифметики. Предположим, что имеется два разложения целого числа N на простые множители:

Источник

Основная теорема арифметики

Взаимно простые числа

Определение. Натуральные числа а и в называют взаимно простыми, если их наибольший общий делитель равен 1.

Например, НОД (15, 7) = 1 числа 15 и 7 взаимно простые.

Свойства простых и взаимно простых чисел

1. Если натуральное число больше 1, то оно имеет хотя бы один простой делитель.

2. Наименьший простой делитель р составного числа а не превосходит .

Доказательство. а р (по условию) а = рq, если q – простое, то р q (по условию). Умножим обе части неравенства на р, получим: р 2 qр, но qр = а р 2 а р . Это значит, что если число а не делится ни на одно простое число не превосходящего , то у него нет простых множителей, меньших этого числа, то есть это число простое.

Например, чтобы установить число 137 простое или составное, нужно найти .

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

Для того, чтобы натуральное число х делилось на составное число n = вс, где (вс) = 1, необходимо и достаточно, чтобы оно делилось на в и на с.

Действительно, если х n = (вс), то х в х с, так как в и с делители числа (вс).

Обратно, пусть х в х с. Так как (вс) = 1, то по доказанному выше число х (вс).

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

Для того, чтобы натуральное число х делилось на 6, необходимо и достаточно, чтобы оно делилось на 2 и на 3.

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

Для того, чтобы натуральное число х делилось на 12, необходимо и достаточно, чтобы оно делилось на 3 и на 4.

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

Для того, чтобы число х делилось на 15, необходимо и достаточно, чтобы оно делилось на 3 и на 5.

Основная теорема арифметики

Условимся считать два разложения на простые множители одинаковыми, если они отличаются друг от друга только порядком следования множителей.

Источник

Закономерности в распределении простых чисел

Введение

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

Ещё до нашей эры Евклид сформулировал и доказал первые теоремы о простых числах. С тех пор математики, среди них Гаусс, Ферма, Риман, Эйлер, продолжали исследования и надо отдать им должное заметно продвинулись. Было обнаружено много интересных свойств простых чисел, выдвинуто много предположений, некоторые из которых были доказаны. Однако много гипотез связанных с простыми числами до сих пор остаются необоснованными.

Распределение простых чисел

Первостепенная задача, решение которой автоматически привело бы к решению большинства вопросов связанных с простыми числами заключается в следующем:

Получить рекуррентную формулу для очередного простого числа

Существует родственная ей задача о количестве простых чисел, не превосходящих заданной величины:

Найти функцию p(x), значение которой в точке x равно числу простых чисел на отрезке [1, x]. Где x – любое действительное число не меньшее единицы.

Функция называется функцией распределения простых чисел.

К решению вышеуказанных задач существует множество подходов. Рассмотрим некоторые из них.

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

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

Первое простое число p₁ =2. Значит все последующие простые числа должны не делится на 2, то есть иметь вид 2k+1, где k – натуральное. То есть все простые числа начиная со второго — нечётные.

Второе простое число p₂ = 3. Значит все последующие простые числа должны иметь вид 3m+1, либо 3m+2, где m – целое. Это равносильно утверждению о том, что все простые числа начиная с третьего не делятся на три. Однако при этом числа ещё должны не делится на два, то есть иметь вид 2k+1.

Решая диофантовы уравнения

найдём k и m и получим, что все простые числа начиная с p₃ обязательно представимы в виде , либо в виде , где t – целое.

И правда, какое бы простое число мы ни взяли оно представимо таким образом:

Однако обратное неверно, то есть любое натуральное число вида 6t+1 или 6t+5 не обязательно простое. Например, .

Третье простое число p₃ = 5. И если по аналогии учесть, что любое простое число, начиная с четвёртого не делится на 5, также не делится на p₁ = 2 и на p₂ = 3, то получим, что все простые числа начиная с p₄ обязательно имеют одно из представлений

Затем учтём p₄, p₅ и т.д. Проблема в том, что на каждом шаге нам придётся решать всё большую систему диофантовых уравнений, поэтому такой прямолинейный подход оказывается весьма сложным.

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

Итак, как же найти функцию F(x)? Сначала рассмотрим множество всех натуральных чисел. Какова доля чисел, которые не делятся ни на одно из простых p₁, p₂, …, p_n?

Каждое второе число делится на p₁ = 2. Значит, часть всех чисел делится на p₁.

Каждое третье число делится на 3. Значит, всех чисел делится на p₂. При этом надо учесть, что каждое шестое число делится и на 2 и на 3 одновременно.

Значит, доля чисел не делящихся ни на 2, ни на 3 равна

Если преобразовать выражение, то оно примет вид:

Опять же можно представить выражение в виде

Будем обозначать такое произведение P(n). Кстати, если учесть все простые числа (n→∞), то мы получим обратную величину от так называемого произведения Эйлера.

Почему так происходит? Когда мы получали формулу (1), мы пользовались рассуждениями, что среди всех натуральных чисел доля, делящихся на p_n, равна . Но нельзя сделать такое утверждение о конечном наборе последовательных натуральных чисел. Например, возьмём набор 1,2, 3,4,5,6,7,8,9. Здесь 4 числа из 9 делятся на два. И несложно заметить, что отличается от . То есть, при применении к конечному набору чисел, данный метод даёт результат с некоторой погрешностью.

Это будет мешать далее получать точные формулы. Но если оценить эту погрешность, то можно (например, приняв и используя приведённые выше рассуждения) получить оценку для p_n+1-го простого числа. Однако, получение таких оценок — это тема отдельной работы. И поэтому здесь я не буду на этом останавливаться, а приведу лишь некоторые результаты, полученные математиками.

Одна из оценок для простого числа с номером n:

оценка верна для всех n, начиная с 6.

А вот формула для функции распределения простых чисел:

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

Гипотеза Римана до сих пор не доказана и не опровергнута. Она, как мы могли видеть, тесно связана с простыми числами и, вообще, имеет огромное значение для теории чисел. Из-за своей важной роли в математике, гипотеза Римана была объявлена одной из семи задач тысячелетия.

Проблемы Ландау

Насчёт простых чисел выдвинуто очень много интересных гипотез. Среди них видное место занимают гипотезы Ландау (проблемы Ландау). Формулируются они так:

1. Гипотеза Гольдбаха

Можно ли любое целое чётное число, большее 2, записать в виде суммы двух простых?

2. Гипотеза о числах-близнецах

Бесконечно ли число простых p таких, что p + 2 тоже простое?

3. Гипотеза Лежандра

Всегда ли существует по меньшей мере одно простое число, лежащее между двумя последовательными полными квадратами?

4. Гипотеза о почти квадратных простых числах

Существует ли бесконечно много простых чисел p вида .

Проблемы Ландау ни доказаны, ни опровергнуты по состоянию на 2020 год. Далее кратко расскажу про каждую из них.

1. Гипотеза Гольдбаха

Существуют две гипотезы Гольдбаха: слабая (тернарная) и сильная (бинарная).

Слабая гипотеза Гольдбаха: Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел.

Эту гипотезу доказал Харольд Гельфготт в 2013 году используя так называемые большие дуги. Финальная часть доказательства заняла 133 страницы.

Сильная гипотеза Гольдбаха: Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

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

Заметьте, что в сильной гипотезе речь идёт только о чётных числах. Давайте покажем, что нечётное число не обязано быть представимо в виде суммы двух простых чисел. Просто приведём пример. Число 11 не представимо в виде суммы двух простых. Вроде бы несложно.

Но переформулируем проблему так: существует ли такое число, что любое нечётное, большее этого числа, представимо в виде суммы двух простых чисел? Давайте проверим. Пусть существует некоторое нечётное натуральное число N, такое, что любое нечётное число представимо в виде суммы двух простых чисел.

Возьмём произвольное нечётное . По предположению существуют такие простые p₁ и p₂, что . Если сумма двух натуральных чисел нечётна, то это значит, что одно из слагаемых чётно, а другое нет. Пусть для определённости p₁ – чётное. Единственное чётное простое число — это 2. Значит, . То есть, K-2 (предыдущее перед K нечётное число) является простым. Поскольку всё вышесказанное верно для любого нечётного большего N, то получается, что все нечётные числа, начиная с N-2, являются простыми. Это неверно. Если бы это было так, то при n→ ∞. Однако, как говорилось выше при n→ ∞.

Итак, не существует такого числа, начиная с которого все нечётные числа могут быть представлены в виде суммы двух простых.

А что же насчёт чётных? Гипотеза не была опровергнута, не было найдено ни одного контрпримера. Но это не значит, что их не существует. Доказать же гипотезу полностью пока никому не удалось.

2. Гипотеза о числах-близнецах

Бесконечно ли число простых чисел близнецов?

Для начала сформулируем определение. Два простых числа называются близнецами если отличаются друг от друга на 2.

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

3. Гипотеза Лежандра

Всегда ли существует, по меньшей мере, одно простое число, лежащее между двумя последовательными полными квадратами?

Аналогичная гипотеза доказана для кубов, начиная с некоторого n. То есть, существует, по меньшей мере, одно простое число, лежащее между и для достаточно большого n. Для квадратов же, гипотеза Лежандра пока не доказана.

4. Почти квадратные простые числа

Заключение

Как мы видим, в этой области теории чисел существует очень много пробелов, а также недоказанных гипотез. Отдельно хочется сказать про численную проверку утверждений. Например, ни для одной из гипотез Ландау не был найден контрпример, даже с использованием значительных вычислительных мощностей в течение большого времени. Однако, в истории математики 20-го и 21-го века были случаи, когда контрпример, опровергающий гипотезу, был настолько огромным числом, что его не удавалось найти с помощью вычислительных машин.

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

Источник