Простые и составные числа. таблица простых чисел

Таблица и примеры

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

Нужно доказать, что делитель не совпадает с членами выражения. Если это не так, произведение k1* k2 *… * kn можно поделить на kn+1. Но на него делится и число k, определяемое суммой k1 * k2 *…* kn+1. Следовательно на kn+1 должно разделиться и второе слагаемое, которое равно одному, а это невыполнимо. То есть всегда может быть новое простое число, не стоящее среди любого количества наперёд заданных простых чисел. Проверка предположения выполнена.

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

Доказательство строится на обратном. Пусть количество простых величин ограничено n штуками. Если имеется значение k, равное k1 * k2 *… * kn+1, оно отлично от каждого из входящих в многочлен. Когда k — простое число, утверждение будет доказано. Должен существовать простой делитель этого числа kn+1.

Как пример, можно привести 3 значения: −99, 17 и −27. Они взаимные, так как любая совокупность простых величин составляет набор взаимности. Например, 2, 3, 11, 19, 151, 293 и 677. А вот такие значения как 12, −72 не являются взаимными, так как у них есть общее делимое 3, и оно отлично от единицы.

Таким образом, чтобы определить взаимность, необходимо попробовать разложить значения на простые множители. Например, пара состоящая из 8 и 15 будет взаимной, хотя сами числа не являются простыми. То же самое, можно сказать, о 8, 15 и 49. В то же время 6, 8 и 9 хоть и взаимные, но они не будут парно простыми.

Зная, какие выражения попарно взаимные, а какие нет, можно определить возможность сокращения дроби. Интересно, что количество зубцов на звёздочках в цепи передачи стремятся делать взаимно простыми. Это помогает обеспечить равномерность износа: каждый зубец будет входить в звенья цепи по очереди.

Число и сумма всех делителей числа

Теорема 1 дает возможность определить, делится число m на n, если эти числа разложены на простые множители.

Если m делится на n, то n является кратным m:

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

Справедливо и обратное. Если каждый простой множитель числа n входит по крайней мере столько же раз в число m, то m делится на n.

Утверждение 3. Пусть a1,a2,a3,… различные простые числа входящие в m так, что

Тогда все делители n числа m можно представить формулой

где i=0,1,…α, j=0,1,…,β, k=0,1,…,γ. Заметим, что αi принимает α+1 значений, βj принимает β+1 значений, γk принимает γ+1 значений, … .

Каждая из чисел n вычисленная формулой (6) является делителем числа m.

Очевидно, при разных значениях i, j, k имеем разные делители числа m. Тогда число всех делителей m равно:

Мы доказали следующую теорему:

Теорема 4. Пусть

каноническое разложение числа m. Тогда число делителей числа m равно:

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

Тогда для произведения вида берем по одному множителю из каждого горизонтального ряда. Используя правила умножения многочленов получим:

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

Следовательно сумма всех делителей числа m равна

Мы доказали следующую теорему:

Теорема 5. Пусть

каноническое разложение числа m. Тогда сумма всех делителей числа m равна выражению (7).

Пример . Возьмем число 280=23·5·7 .

Множество делителей этого числа такова

Число делителей числа 280 равно:

Сумма делителей числа 280 равна:

Общие сведения

В системе счисления и мер используется специальная система знаков, называемая цифрами. Слово «цифра» происходит от латинского cifra. Интересно, что на арабском термин пишется как صفر‎, что в дословном переводе на русский язык обозначает «пустой». С этих символов формируются числа. Чтобы разобраться в отличиях одних от других, нужно запомнить 3 утверждения:

  1. Всего существует 10 цифр — 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
  2. Из десяти символов формируют числа.
  3. Цифры — это знаки, а числа — абстракции, обозначающие количество.

Нужно знать, что существует несколько систем счисления. В России принято использовать арабскую. В церковнославянском и древнегреческом применяли запись буквами. Её до сих пор используют в иврите. В программировании применяется смешанная запись. Так как она шестнадцатеричная, используют комбинации знаков: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Итак, «число» и «цифра» разные понятия по происхождению. Первое используют как единицу счёта. Им выражают количество. Второй же параметр применяют для обозначений значений. Для записи в международном формате принята арабская последовательность от 0 до 9, но в некоторых случаях ставят и римские символы — I, II, III, IV, V, V I, V II, V III, IX, X и так далее.

По своему виду числа бывают:

  • натуральными — простыми целыми, использующимися при счёте;
  • рациональными — конечными дробными отношениями;
  • иррациональными — бесконечными непериодическими дробями;
  • действительными — образующими множество, включающее рациональные и иррациональные значения.

Часто при вычислениях используют округление. Это запись, при которой указывают примерное значение. Округляют значение путём убирания десятичных частей или уменьшением их разрядности. Например, 5,17 ~ 5; 4,5213 ~ 4,5. Благодаря этой операции вычисление упрощается, хотя при этом теряется точность ответа.

Таблица простых чисел

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

Возникает логичный вопрос: «Почему мы заполнили таблицу простых чисел только до 1 000, разве нельзя составить таблицу всех существующих простых чисел»?

Ответим сначала на первую часть этого вопроса. Для большинства задач, при решении которых придется использовать простые числа, нам будет вполне достаточно простых чисел в пределах тысячи. В остальных случаях, скорее всего, придется прибегать к каким-либо специальным приемам решения. Хотя, несомненно, мы можем составить таблицу простых чисел до сколь угодно большого конечного целого положительного числа, будь то 10 000 или 1 000 000 000, в следующем пункте мы поговорим о методах составления таблиц простых чисел, в частности, разберем способ, получивший название .

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

Теорема.

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

Доказательство.

Пусть a – натуральное число, большее единицы, и b – наименьший положительный и отличный от единицы делитель числа a. Докажем, что b – простое число методом от противного.

Предположим, что b – составное число. Тогда существует делитель числа b (обозначим его b1), который отличен как от 1, так и от b. Если также учесть, что абсолютная величина делителя не превосходит абсолютной величины делимого (это мы знаем из свойств делимости), то должно выполняться условие 11.

Так как число a делится на b по условию, и мы сказали, что b делится на b1, то понятие делимости позволяет говорить о существовании таких целых чисел q и q1, что a=b·q и b=b1·q1, откуда a= b1·(q1·q). Из правил умножения целых чисел следует, что произведение двух целых чисел есть целое число, тогда равенство a=b1·(q1·q) указывает на то, что b1 является делителем числа a. Учитывая полученные выше неравенства 11, мы получаем противоречие условию, что b – наименьший положительный и отличный от единицы делитель числа a.

Теперь мы можем доказать, что простых чисел бесконечно много.

Теорема.

Простых чисел бесконечно много.

Доказательство.

Предположим, что это не так. То есть, предположим, что простых чисел всего n штук, и эти простые числа есть p1, p2, …, pn. Покажем, что мы всегда можем найти простое число, отличное от указанных.

Рассмотрим число, p равное p1·p2·…·pn+1. Понятно, что это число отлично от каждого из простых чисел p1, p2, …, pn. Если число p — простое, то теорема доказана. Если же это число составное, то в силу предыдущей теоремы существует простой делитель этого числа (обозначим его pn+1). Покажем, что этот делитель не совпадает ни с одним из чисел p1, p2, …, pn.

Если бы это было не так, то по свойствам делимости произведение p1·p2·…·pn делилось бы на pn+1. Но на pn+1 делится и число p, равное сумме p1·p2·…·pn+1. Отсюда следует, что на pn+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.

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

Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100, 1 000, 10 000 и т.д.

Наибольший общий делитель (НОД), свойства.

  • Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
  • Следствие 1: множество общих делителей m и n совпадает с множеством делителей НОД(m, n).
  • Следствие 2: множество общих кратных m и n совпадает с множеством кратных НОК(m, n).
  • Если m делится на n, то НОД(m, n) = n. В частности, НОД(n, n) = n.
  •  — общий множитель можно выносить за знак НОД.
  • Если , то после деления на  числа становятся взаимно простыми, то есть, .

Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД.

Мультипликативность: если  взаимно просты, то:

Наибольший общий делитель чисел m и n может быть определён как наименьший положительный элемент множества всех их линейных комбинаций:

и поэтому  представим в виде линейной комбинации чисел m и n:

.

Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД (a1, a2, … , an).

Свойства и определение

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

Понятие взаимности простых чисел справедливо как для пары выражений, так и большего их числа. Два натуральных числа, стоящие один за одним, всегда будут взаимными. Например, 13 и 14 — простая пара, такая же как 23 и 24.

Это легко можно доказать, используя то, что 2 натуральных значения a и b делятся на одно и то же натуральное число, превышающее единицу, если их разница будет делиться на это выражение. Так как a и b — 2 соседних значения, для удобства можно принять что a

Из определения о взаимных значениях следует, что любые простые величины всегда окажутся взаимными. Ведь делителями любого простого выражения являются лишь оно само и 1. Кстати, такие значения обозначают так: (a, b) = 1.

Из признаков и свойств можно выделить:

  1. Меньшее из возможных общих кратных пары взаимно простых выражений равняется их результату перемножения. Например, (3, 8) = 1. То есть они взаимные. Их наименьшее кратное равно 24. Действительно, если попробовать методом перебора подобрать меньшее значение, найти его будет невозможно.
  2. Если числа a и b простые, и существует число c, которое кратно им двоим, оно будет делиться без остатка на результат умножения a * b. Например, (3, 10) = 1, число 60 кратно как трём, так и десяти, а также кратно 30 (3 x 10).
  3. Когда числа a и b простые, и имеется такая величина, как b (c b), выражение a * c также будет: b (ac b). Например, (2, 17) = 1, а * c = 34. 34 кратно b, то есть 17. Тогда: a * c = 2 * 34 = 68. Проверить результат легко. Нужно его просто разделить на кратную величину: 68 ÷ 17 = 4. Так как в ответе целое, 68 кратно 17.

Таблица простых чисел

Простые числа до
К-во столбцов в таблице

Утверждение 1. Если p — простое число и a любое целое число, то либо a делится на p, либо p и a

Действительно. Если p простое число, то оно делится только на себя и на 1, если a не делится на p, то наибольший общий делитель a и p равен 1. Тогда p и a взаимно простые числа .

Утверждение 2. Если произведение нескольких чисел чисел a1, a2, a3, … делится на простое число p, то по крайней мере одно из чисел a1, a2, a3, … делится на p.

Действительно. Если бы ни одно из чисел не делилось на p, то числа a1, a2, a3, … были бы взаимно простые числа по отношению p. Но из следствия 3 ( ) следует, что их произведение a1, a2, a3, … также взаимно простое по отношению к p, что противоречит условию утверждения. Следовательно по крайней мере один из чисел делится на p.

Теорема 1. Любое составное число всегда может быть представлено и притом единственным способом в виде произведения конечного числа простых чисел.

Доказательство. Пусть k составное число, и пусть a1 один из его делителей отличное от 1 и самого себя. Если a1 составное, то имеет кроме 1 и a1 и другой делитель a2. Если a2 число составное, то имеет кроме 1 и a2 и другой делитель a3. Рассуждая таким образом и учитывая, что числа a1, a2, a3, … убывают и этот ряд содержит конечное число членов, мы дойдем какого-то простого числа p1. Тогда k можно представить в виде

Если k1 число простое, то k уже представлен в виде произведения простых чисел, в противном случае существует такое простое число p2, что

Тогда

Если k2 число составное, то мы продолжаем процедуру до тех пор, пока k не будет представлено в виде произведения простых чисел:

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

Допустим существует два разложения числа k:

где pi (i=1,2,…), qj (j=1,2,…) простые числа. Из (1) следует, что

Так как k=p1p2p3… делится на простое число q1, то по крайней мере один из множителей, например p1 делится на q1. Но p1 простое число и делится только на 1 и на себя. Следовательно p1=q1 (т.к. q1≠1)

Тогда из (2) можно исключить p1 и q1:

Аналогичным способом можно доказать, что число q1 должно быть равно одному из простых чисел p2, p3, … например p2, тогда

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

Разложение составного числа k можно записать в следующем виде

где p1, p2, … различные простые числа, α, β, γ… целые положительные числа.

Разложение (3) называется каноническим разложением числа.

Простые числа в ряду натуральных чисел встречаются неравномерно. В одних частях ряда их больше, в других — меньше. Чем дальше мы продвигаемся по числовому ряду, тем реже встречаются простые числа. Возникает вопрос, существует ли самое большое простое число? Древнегреческий математик Евклид доказал, что простых чисел бесконечно много. Ниже мы представим это доказательство.

Теорема 2. Количество простых чисел бесконечно много.

Доказательство. Предположим, что существует конечное число простых чисел, и пусть наибольшее простое число равно p. Рассмотрим все числа больше p. По предположению утверждения эти числа должны быть составными и должны делится по крайней мере на один из простых чисел. Выберем число, являющиеся произведением всех этих простых чисел плюс 1:

Число z больше p так как 2p уже больше p. p не делится ни на одно из этих простых чисел, т.к. при делении на каждое из них дает остаток 1. Таким образом мы приходим к противоречию. Следовательно существует бесчисленное множество простых чисел.

Данная теорема является частным случаем более общей теоремы:

Теорема 3. Пусть задана арифметическая прогрессия

где d разность арифметической прогрессии, m первый член, и пусть d и m взаимно простые числа. Тогда арифметическая прогрессия (5) содержит бесконечное множество простых чисел.

Нетрудно заметить, что при m=1 и d=1 мы получим теорему 2.

Ссылка на основную публикацию