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

1) Если натуральное число n > 1, то наименьший натуральный делитель его, отличный от 1, — простое число.

Доказательство. Пусть р - наименьший натуральный делитель и, отличный от 1 (п имеет натуральные делители, отличные от 1, например, n). Очевидно, что р - простое число. Иначе оно имело бы такой делитель а, что 1< а < р, но а, будучи делителем р, было бы и делителем п, что противоречит выбору числа р.

2)Если а - целое, р - простое, то а:р или (а,р)=1.

Доказательство. Так как число р имеет только 2 натуральных делителя:

р и 1, то (а,р)= р или (а,р) = 1. В первом случае а⁞р, во втором- а⁞р - взаимно простые числа.

3)(Основное свойство простых чисел.) Если произведение целых чисел ab делится на простое число р, то хотя бы один из сомножителей делится на р.

Доказательство. Пусть аb⁞ р. Если а не делится на р, то (а,р)=1 (свойство2).Тогда по свойству взаимно простых чисел b:р.

Заметим, что свойство может быть распространено на любое конечное число сомножителей.

4. Бесконечность множества простых чисел. Критерий простоты числа. Основное свойство простых чисел

§8. Теорема Евклида

Вопрос о том, конечно ли множество простых чисел, возник давно и был решён ещё Евклидом (древнегреческий математик, 3 век до новой эры). Доказательство Евклида о бесконечности множества простых чисел необычайно остроумно. Евклид строит числа на единицу большие, чем кратные 2,3, и так далее:

2 *3 +1 = 7,

2*3*5+1=31,

2*3*5*7+1=211,

2*3*5*7*11+1=2311,

2*3*5*11*13+1=30031,

…………………..

Получающиеся таким образом числа не могут содержать в качестве сомножителей тех простых чисел, с помощью которых они построены (при делении на эти простые числа получается остаток, равный 1). Таким образом, если бы, например, число 30031 было составным, то можно быть уверенным, что любой его простой делитель отличен от 2, 3, 5, 7,11,13, то есть больше 13. В самом деле, 30031 = 59*509, где 59 и 509 - простые числа. Это и показывает, что процесс получения простых чисел бесконечен.

Теорема (Евклида). Множество простых чисел бесконечно.

Доказательство. Предположим, что множество простых чисел конечно и состоит из чисел 2, 3, 5,..., р, где р - последнее, самое большое просто число. Рассмотрим натуральное число Р = 2*3*5*...* p +1. P >1и следовательно, имеет простой делитель q. Однако q отлично от чисел 2,3, 5,..., р (при делении Р на каждое из этих простых чисел получается остаток 1). Таким образом, q есть новое простое число, большее, чем p. Предположение, что множество простых чисел конечно, привело нас к противоречию, то есть простые числа образуют бесконечное множество.

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

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

Доказательство. Среди п чисел (n + 1)!+2, (n + 1)!+3,…,(n + 1)!+ n + 1, следующих друг за другом, ни одно не является простым, так как первое больше двух и делится на два, второе больше трёх и делится на три и т. д., энное больше n +1 и делится на n +1.

Например: 101!+2,101!+3,…,101!+101 - сто подряд идущих

составных чисел.

Возникает вопрос: как выделить среди натуральных простые числа, составить таблицу простых чисел?

Теорема (критерий простоты). Если число, п> 1 и не имеет простых делителей , то п — простое.

Доказательство. Если бы п было составным, то п = ab, где 1 < а < п, 1<b<п. Оба множителя не могут быть больше , иначе их произведение ab было бы больше n. Следовательно, хотя бы одно из чисел а и b не превышает Если, например, число , то его простой делитель . Таким образом, любое составное число имеет простой делитель, не превышающий , что и доказывает теорему.

Один из наиболее древних способов для составления таблиц простых чисел носит название решето Эратосфена. Пусть надо составить таблицу простых чисел, не превосходящих п. Выписывают все натуральные числа от 2 до n. Из них вычёркивают каждое второе число после простого числа 2 (то есть все чётные числа, большие 2). Первым не зачёркнутым числом остаётся простое число 3. Теперь, вычёркивают каждое третье число после трёх (причём считают и те числа, которые вычеркнуты ранее) и так далее. После вычёркивания всех чисел, кратных простому числу , первое следующее за не зачёркнутое число является простым, иначе оно имело бы простой делитель, не превышающий , но все кратные таким простым числам уже вычеркнуты. Составление таблицы можно считать законченным, как только найдено простое число, большее

Обозначим количество простых чисел, не превосходящих числа через π(х). Так π(l) = 0, π(2) = 1, π(50) = 15.

π(x) при (теорема Евклида). Эйлер получил более сильный результат: ряд чисел, обратных простым, расходится. Мы знаем, что гармонический ряд расходится, а ряд сходится.

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

Кажется, что последовательность простых чисел в натуральном ряду не подчиняется никаким законам. Ещё Эйлер писал, что математики тщетно пытаются найти некоторый закон в распределении простых чисел и что есть основание считать, что это тайна, в которую человеческий разум никогда не проникнет. В самом деле, в первой тысяче 169 простых чисел, а в интервалах длиной в 1000 левее и правее 10 миллионов, их соответственно 9 и 2.

Существуют очень большие простые числа-близнецы, записываемые с помощью 303 цифр. Неизвестно, правда, конечно ли это множество.

Среди отдельных классов простых чисел в своё время значительный интерес представляли простые числа вида -1 Простыми они будут только если п -простое. Но и числа вида , где р - простое, не всегда простые. Так при р =11 получается составное число. Простые числа такого вида называют простыми числами Мерсенна по имени французского математика, который в 1644 году составил достаточно большой список простых чисел такого вида. Числа Мерсенна играют важную роль в теория

чисел. Ещё Евклид обнаружил, что если число -простое, то число является совершенным, то есть равным сумме своих собственных делителей. При p =2 получим 6 (6 = 1 + 2 + 3); при р= 3 получим 28 (28 = 1 + 2 + 4 + 7 + 14). Эйлер доказал, что все четные совершенные числа имеют такой вид. Неизвестно, существуют ли нечетные совершенные числа.

Ферма предположил, что числа вида +1, где п = ,- простые. Действительно, при k, равном 0,1, 2, 3, 4, получаются простые числа. Следующее число, при к = 5, было настолько велико, что Ферма не смог определить, простое ли оно. Эйлер доказал, что это число составное. Простые числа такого вида носят название простых чисел Ферма. Они связаны с задачей построения правильных многоугольников с помощью циркуля и линейки. Гаусс доказал, что правильный n-угольник может быть Построен с помощью циркуля и линейки тогда и только тогда, когда

, где α - целое неотрицательное число и все простые числа - простые числа Ферма. (Среди первой тысячи всего 54 простых чисел Ферма.)

Эйлер указал интересный многочлен , который принимает простые значения для всех целых х от 0 до 40, но при x = 41 и х = 42 значения будут составными числами.

Для чисел, растущих закономерно (например, ), было бы нелепо разыскивать число, превосходящее все известные. Поиски же больших простых чисел продолжаются до сих пор, при этом проводятся Громоздкие вычисления.

Например, через 111 лет после найденного Эйлером простого числа с 10 цифрами Первушин нашёл простое число из 19 цифр. В 1876 году Люка доказал, что - простое число (39 цифр), и 75 лет оно оставалось наибольшим известным простым числом. Только в 1951 году после возникновения ЭВМ было найдено ещё большее простое число из 44 цифр. После этого простые числа-рекордсмены сменяли друг друга. Так в 1982 году было найдено простое число -1 из 25962 цифр. В 2001 году было получено простое число Мерсенна с показателем, большим , Число имеет более 4 миллионов цифр (4053946 знаков). Получено 20-летним канадцем М. Камероном в рамках проекта GIMPS. Проект основан в 1996 году Джорджем Уолтменом и посвящён поиску простых чисел Мерсенна. Камерон в течение 45 дней запускал программу GIMPS на своём компьютере. Однако он не достиг бы такого результата, если бы не помощь всех остальных 130000 участников проекта, которые потратили на вычисление этого числа в общей сложности 13000 лет машинного времени.

Отыскание новых простых чисел может принести и денежную награду. Фонд электроники (EFF) учредил награду за отыскание первого простого числа, имеющего более миллиона цифр. Эту награду (50 тысяч долларов) получил в 2000 году участник проекта Н. Хаджратвала из США. Следующие награды -100000,150000 и 250000 долларов за простое число, соответственно, из 10 миллионов, 100 миллионов и миллиарда знаков.

Самое удивительное, что распределение простых чисел подчиняется вполне определённым законам. Главный результат в исследовании распределения простых чисел - это асимптотический закон распределения простых чисел. Функция π(х) асимптотически равна функции , что означает, что =1 при x .

В 1808 году Лежандр опубликовал найденную им эмпирическую формулу для вычисления π(x) для больших х:

.

Другое очень хорошее приближение дал Гаусс: .Такой закон Гаусс заметил ещё в 15 лет, изучая таблицы простых чисел. Он всю жизнь интересовался распределением простых чисел, находил время нахождения новых простых, чисел и проверки закона. Он дошёл до 3000000 простых чисел.

Первым, кто после Евклида добился существенного продвижения в труднейшем вопросе о распределении простых чисел при помощи теоретических исследований, был русский математик П.Л. Чебышев.

В 1848 -1850 годах Чебышев доказал, что для достаточно больших x существуют положительные числа а,b,а< b, что

Он также доказал, что если существует то он равен 1.

Следующий важный шаг сделал немецкий математик Б. Риман в 1859 году. Оп использовал теорию функций комплексного переменного. В его доказательстве был ряд пробелов. И только в 1896 году французский математик Ж. Адамар и бельгийский математик Ш. Валле-Пуссен

независимо друг от друга доказали существование предела

А в 1948-1949 годах венгерский математик П. Эрдёш и датский математик А. Сельберг доказали этот закон почти элементарно, используя из анализа лишь понятие предела.

Проблема распределения простых чисел в натуральном ряду получает дальнейшее развитие в вопросе распределения простых чисел в арифметических прогрессиях и других числовых последовательностях. В 1837 году немецкий математик Лежен Дирихле доказал, что в арифметической прогрессии чисел вида кх+l, где к и l - целые взаимно простые числа, а х = 0,1, 2,,.., содержится бесконечное множество простых чисел.

Для отдельных частных случаев теорема Дирихле доказывается просто. Докажем, например, что существует бесконечно много простых чисел вида 4 n + 3.

Из равенства (4 m + l)(4 n +1)=16 тп + 4 m + 4 n +1 видно, что произведение двух чисел, каждое из которых при делении на 4 даёт в остатке 1, имеет тот же остаток 1 при делении на 4.

Предположим, что существует только конечное множество простых чисел вида 4n+3. Тогда возьмём число М, равное произведению всех таких простых чисел, и рассмотрим число 4 М -1. По сделанному выше замечанию число 4 М -1 не может раскладываться в произведение лишь простых множителей вида 4 п +1, то есть имеет хотя бы один простой делитель p вида 4 п + 3. (Заметим, что простые нечётные числа при делении не могут иметь других остатков, кроме 1 и 3, а число 4 М -1)⁞ p имеет только нечётные простые делители.) Так как (4 М -1)⁞р и М⁞р, то 1⁞ p. Предположение, что существует только конечное число простых чисел 4 п + 3, привело нас к противоречию; значит множество таких простых чисел бесконечно.

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

5. Основная теорема арифметики и следствия из нее.

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

Доказательство. Будем доказывать методом математической индукции. Для п-2 и для простого числа утверждение верно. Единственность представления следует из определения простого числа. Пусть утверждение верно для всех натуральных чисел, больших 1, но меныших п. Докажем справедливость его для числа п. Если п - простое, то утверждение доказано. Если же п - составное, то его можно представить в виде п = ab, где 1< а <п, 1 < b < п. По индуктивному предположению каждое из чисел а и b либо является простым, либо представимо в виде произведения простых чисел. Следовательно, п=ab тоже разлагается в произведение простых чисел.

Докажем единственность представления. Пусть n= простые числа. Тогда = . Так как то (по свойству простых чисел 3) хотя бы один из сомножителей делится на Пусть, например, Так как оба числа простые, то После сокращения равенства на получим: Обозначим произведение = . Так как 1< <n, то по индуктивному предположению s=r, а числа отличаются от чисел порядком. Поэтому при соответствующей нумерации этих чисел = Единственность доказана.

Итак, всякое составное число п может быть представлено в виде произведения простых чисел. Среди этих простых множителей могут встречаться одинаковые. Пусть, например, встречается раз, встречается раз,..., встречается раз; тогда разложение числа п на простые множители можно записать следующим образом: n=

Такое представление числа называют каноническим («канон» по латыни - правило, образец).

Примеры. 60 = * 3 * 5; 81 = ; 666 = 2 * * 37.

Рассмотрим некоторые следствия из основной теоремы.

Следствие 1. Пусть n= каноническое разложение натурального числа п. Все делители п исчерпываются числами вида

n= где 0 (l)

Доказательство. Действительно, с одной стороны, всякое число d такого вида делит п. С другой стороны, всякое число, которое делит n, имеет указанный вид, так как по свойствам делимости оно не может иметь других простых сомножителей, кроме , а их показатели не могут противоречить условиям (l).

Заметим, что натуральные числа а и b всегда можно записать в виде a = , b = .

Здесь предполагается, что могут принимать и нулевые значения. Это позволит писать в обоих разложениях одни и те же простые числа , а именно простые числа, которые входят в разложение хотя бы одного из чисел а и b. Если числа а и b записаны в указанном виде, то справедливы следующие два утверждения.

Следствие 2. (a, b) = , [ a,b ]=

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

Следствие 3. [ a,b ] *(a,b)=a*b.

Действительно, [ a,b ] *(a,b) = , где

Но одно из этих слагаемых равно , а другое - . Следовательно, .

6. Сравнения и их свойства.

§ 1. Сравнения и их основные свойства.

Определение. Целые числа а и b называются сравнимыми по модулю m, если разность а - b делится на m. Обозначение: а b(modm).

Примеры. 5 = -l(mod 6), так как 5-(-1) делится на 6; 1717 37 (mod 10), так как 1717-37 делится на 10; 18 0 (mod 6), так как 18-0 делится на 6.

Теорема 1. Следующие утверждения эквивалентны:

(1) а b(modm), (2) существует t Z, что а=b+ mt (а отличается от b на число, кратное m), (3) а и b при делении на m дают одинаковые остатки (т.е. а и b равноостаточные).