Простые и составные числа: примеры, таблица простых чисел, решето Эратосфена

Общее представление о натуральных числах

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

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

Оценить основные навыки озвучивания (чтения) и изображения (написания) натуральных чисел.

Классы натуральных чисел.

Любое натуральное число можно записать 10 арабскими цифрами:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

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

Сравнение натуральных чисел.

Из 2-х натуральных чисел число, которое называется раньше в счете, меньше. Например, число 7 меньше 11 (записывается так: 7 < 11). Когда одно число больше другого, оно записывается так: 386 > 99.

Десятичная запись натурального числа

Запомните, как появляются следующие символы (указываем их через запятую): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Эти символы мы называем числами.

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

Укажем примеры правильной регистрации натуральных чисел: 703, 881, 13, 333, 1023, 7, 500001. Отступы между числами не всегда одинаковы, об этом подробнее будет сказано ниже, когда мы будем изучать числовые классы. Приведенные примеры показывают, что при записи натурального числа необязательно иметь все цифры из приведенного выше ряда. Некоторые или все из них могут повторяться.

Определение 1

Записи вида: 065, 0, 003, 0791 не являются записями натуральных чисел, потому что число 0 стоит слева.

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

Количественный смысл натуральных чисел

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

Начнем с натуральных чисел, записи которых совпадают с записями цифр, то есть: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Представьте себе конкретный объект, например этот: Ψ. Мы можем написать, что видим 1 объект. Натуральное число 1 читается как «один» или «один». Термин «единство» имеет и другое значение: то, что можно рассматривать как единое целое. Если это множество, любой его элемент можно обозначить единицей. Например, из многих мышей любая мышь является одной; любой цветок из набора цветов является единицей.

А теперь представьте: ΨΨ. Мы видим один объект и другой объект, т.е в записи будет — 2 элемента. Натуральное число 2 читается как «два».

Далее аналогично: ΨΨΨ — 3 элемента («три»), ΨΨΨΨ — 4 («четыре»), ΨΨΨΨΨ — 5 («пять»), ΨΨΨΨΨΨ — 6 («шесть»), ΨΨΨΨΨΨΨ — , ΨΨΨΨΨΨΨΨ — 8 («восемь»), ΨΨΨΨΨΨΨΨΨΨ — 9 («девять»).

С данной позиции функция натурального числа состоит в том, чтобы указывать количество элементов.

Определение 1

Если ввод числа совпадает с вводом цифры 0, такое число называется «нулевым». Ноль не является натуральным числом, но считается вместе с другими натуральными числами. Ноль означает отсутствие, т е ноль элементов означает отсутствие.

Читайте также: Правила вычисления производных

Однозначные натуральные числа

Очевидный факт, что когда мы записываем каждое из рассмотренных выше натуральных чисел (1, 2, 3, 4, 5, 6, 7, 8, 9), мы используем один символ — одну цифру.

Определение 2

Однозначное натуральное число — это натуральное число, в котором используется один символ — одна цифра.

Существует девять однозначных натуральных чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9.

Двузначные и трехзначные натуральные числа

Определение 3

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

Например, натуральные числа 71, 64, 11 — это две цифры.

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

Введем такое понятие, как «десять».

Представьте себе набор предметов, состоящий из девяти и еще одного. В этом случае речь может идти об 1 дюжине («одной дюжине») предметов. Если представить себе одну дюжину и еще одну, то речь пойдет о 2 десятках («два десятка»). Если к двум десяткам прибавить еще один десяток, то получится три десятка. И так далее: продолжая прибавлять по одному десятку, получаем четыре десятка, пять десятков, шесть десятков, семь десятков, восемь десятков и, наконец, девять десятков.

Представим себе двузначное число как набор однозначных чисел, одно из которых написано справа, другое слева. Число слева будет обозначать количество десятков в натуральном числе, а число справа — количество единиц. В случае, когда цифра 0 ставится справа, речь идет об отсутствии единиц. Выше приведено количественное значение натуральных двузначных чисел. Всего их 90.

Определение 4

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

Например, 413, 222, 818, 750 — трехзначные натуральные числа.

Для понимания количественного значения трехзначных натуральных чисел введем понятие «сотня».

Определение 5

Сто (1 сотня) – это набор, состоящий из десяти десятков. Сто плюс сто равно двести. Добавьте еще сотню и получите 3 сотни. Если постепенно прибавлять сто, то получится: четыреста, пятьсот, шестьсот, семьсот, восемьсот, девятьсот.

Рассмотрим фактическую запись трехзначного числа: входящие в него однозначные натуральные числа записываются друг за другом слева направо. Крайняя правая цифра указывает количество единиц; следующее однозначное число слева — с числом десятков; крайняя левая цифра — это число сотен. Если в записи участвует цифра 0, это указывает на отсутствие единиц и/или десятков.

Итак, трехзначное натуральное число 402 означает: 2 единицы, 0 десятков (нет десятков, не объединяющихся в сотни) и 4 сотни.

По аналогии дается определение четырехзначных, пятизначных и так далее натуральных чисел.

Многозначные натуральные числа

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

Определение 6

Многозначные натуральные числа — это натуральные числа, записанные двумя и более цифрами. Многозначные натуральные числа – это двузначные, трехзначные и так далее числа.

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

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

Например, многозначное число 4 912 305 содержит: 5 единиц, 0 десятков, три сотни, 2 тысячи, 1 десяток тысяч, 9 сотен тысяч и 4 миллиона.

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

Таблица разрядов и классов чисел.

Классы	Выбросы
единица 1 класса	1 единица измерения 2 место десятка 3 ранг сотни
2 класс тыс	1-значные единицы тысяч 2 цифры десятки тысяч 3 место в рейтинге сотни тысяч
3 класс миллион	1 цифра единицы миллион двузначное число десятков миллионов 3 цифры сотни миллионов
4 класс миллиард	1-значные единицы миллиарды двузначное число десятков миллиардов 3 цифры сотни миллиардов

Числа от 5-го класса и выше — большие числа. Единицы 5-го класса — триллионы, 6-го класса — квадриллионы, 7-го класса — квинтиллионы, 8-го класса — секстиллионы, 9-го класса — эпитиллионы. Основные свойства натуральных чисел. Коммутативность сложения a + b = b + a Коммутативность умножения ab=ba Ассоциативность сложения. (а + б) + с = а + (б + с) Ассоциативность умножения. Распределение умножения относительно сложения: Операции над натуральными числами. 1. Результат сложения натуральных чисел: сумма натуральных чисел. Формулы сложения: а + б = б + а (а + б) + с = а + (б + с) а + 0 = 0 + а = а В основном сложение натуральных чисел выполняется в «столбце ». 2. Вычитание натуральных чисел — операция, обратная сложению: разность натуральных чисел. Если б + с = а, то Если а = b, то а — b = а — а = 0 Формулы вычитания: (а + Ь) — с = (а — с) + Ь а — (б + в) = (а — б) — в а + (b — с) = (а + b) — с а — (б — в) = а — б + в Натуральные числа удобно вычитать «столбиком ». 3. Умножение натуральных чисел: произведение натуральных чисел. Формулы умножения: а ∙ б = б ∙ а а ∙ б ∙ с = ​​а ∙ (б ∙ с) (а + б) ∙ с = ​​а ∙ с + б ∙ с (а – б) ∙ с = ​​​​​​а ∙ с – б ∙ с а ∙ 1 = 1 ∙ а = а а ∙ 0 = 0 ∙ а = 0 0 ∙ 0 = 0 1 ∙ 1 = 1 Умножение лучше всего делать в «столбик». 4. Деление натуральных чисел — операция, обратная умножению. Если б ∙ с = ​​а, то Формулы деления: а : 1 = а а : а = 1, а ≠ 0 0 : а = 0, а ≠ 0 (а ∙ б) : с = (а : с) ∙ б (а ∙ б) : с = (б : с) ∙ а (а ∙ б) : с = а : (б ∙ с) Деление лучше всего делать столбиком. Численные выражения и числовые уравнения. Запись, в которой числа соединены символами действия, является числовым выражением. Например, 10∙3+4; (60-2∙5):10. Записи, в которых 2 числовых выражения объединены знаком равенства, являются числовыми равенствами. У равенства есть левая и правая стороны. Порядок выполнения арифметических операций. Сложение и вычитание чисел — операции первой степени, а умножение и деление — операции второй степени. Когда числовое выражение состоит из операций только одной степени, они выполняются последовательно слева направо. Когда выражения состоят только из действий первой и второй степени, сначала выполняются действия второй степени, а затем действия первой степени. Если в выражении есть круглые скобки, действия в круглых скобках выполняются в первую очередь. Например, 36:(10-4)+3∙5= 36:6+15 = 6+15 = 21.

Простые и составные числа – определения и примеры

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

Определение 1

Простые числа — это целые числа, которые больше единицы и имеют два положительных делителя, то есть само себя и 1.

Определение 2

Составные числа — это целые числа, которые больше единицы и имеют не менее трех положительных делителей.

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

Определение 3

Простые числа — это натуральные числа, которые имеют только две положительные части.

Определение 4

Комплексное число – это натуральное число, имеющее более двух положительных частей.

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

Определение 5

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

Простые числа: 2, 3, 11, 17, 131, 523. Они делятся только сами на себя и на 1. Составные числа: 6, 63, 121, 6697. То есть число 6 можно разложить на 2 и 3, а 63 на 1, 3, 7,9, 21, 63 и 121 на 11, 11, то есть его делителями будут 1, 11, 121. Число 6697 будет разложено на 37 и 181. Обратите внимание, что термины простое число и относительно простые числа — разные понятия.

История простых чисел

Первые упоминания о простых числах относятся к Древнему Египту. В Британском музее хранится папирус, датируемый 2000 годом до нашей эры. А на ней, судя по расшифровке, лежит учебник по арифметике.

В том числе и о делении чисел. Этот предмет называется Папирус Райнда в честь его первого владельца.

В этом документе есть таблица, показывающая числа, которые делятся на разные знаменатели. Причем разделены они таким образом, что становится понятно, что древние египтяне, может быть, и не употребляли термин «прайм», но, по крайней мере, имели о нем представление.

Итак, первые исследования простых чисел относятся к 300 г до н.э. И связаны они с именем известного древнегреческого математика Евклида.

Как и многое другое, он описал простые и составные числа в своем знаменитом труде «Начала».

В частности, Евклид описал такие вещи, как:

1. Основная теорема арифметики;
2. Бесконечное количество прямых номеров;
3. Лемма Евклида.

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

Чтобы было проще пользоваться простыми числами, нужно воспользоваться таблицей:

Таблица для всех существующих натуральных чисел нереальна, так как их бесконечное множество. Когда числа достигают размеров 10000 или 1000000000, следует задуматься об использовании сита Эратосфена.

Придумайте теорему, объясняющую последнее утверждение.

Теорема 1

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

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

Предположим, что а — натуральное число больше 1, а b — наименьший делитель а, не равный 1. Нам нужно доказать, что Ь простое число, используя метод от противного.

Допустим, b — комплексное число. Отсюда получаем, что существует делитель числа b, отличный как от 1, так и от b. Такой делитель обозначается b1. Необходимо, чтобы условие 1<>было>

Из условия, что a делится на b, b делится на b1, видно, что понятие делимости выражается так: a=bq и b=b1 q1, из которых a= b1 (q1 q) , где q и q1 — целые числа. По правилу умножения целых чисел имеем, что произведение целых чисел есть целое число с равенством вида a=b1·(q1·q). Видно, что b1 является делителем числа a. Неравенство 1<>

Теорема 2

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

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

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

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

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

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

Поскольку простых чисел много, таблицы ограничены числами 100, 1000, 10000 и так далее.

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

2	3	5	7	одиннадцать	1. 3	17	19	23
29	31	37	41	43	47	53	59	61
67	71	73	79	83	89	97	101	103
107	109	113	127	131	137	139	149	151
157	163	167	173	179	181	191	193	197
199	211	223	227	229	233	239	241	251
257	263	269	271	277	281	283	293	307
311	313	317	331	337	347	349	353	359
367	373	379	383	389	397	401	409	419
421	431	433	439	443	449	457	461	463
467	479	487	491	499	503	509	521	523
541	547	557	563	569	571	577	587	593
599	601	607	613	617	619	631	641	643
647	653	659	661	673	677	683	691	701
709	719	727	733	739	743	751	757	761
769	773	787	797	809	811	821	823	827
829	839	853	857	859	863	877	881	883
887	907	911	919	929	937	941	947	953
967	971	977	983	991	997

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

Основная теорема арифметики, изобретенная Евклидом, гласит:

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

Если обозначить исходное число буквой N, а простые числа буквами P1, P2, P3 и т д., то эту теорему можно записать следующим образом:

Н = П1*П2*П3*…*РК

Например, возьмем число 100. Его можно разложить на следующие простые числа:

100 = 5 * 5 * 2 * 2

Или более сложный пример — число 23244:

23244 = 149*13*3*2*2

Его легко разложить на простые числа. Можно сначала разделить на 2 и 3, а в конце автоматически получатся более сложные делители.

Ради интереса придумайте любое число и сами найдите компоненты.

Лемма Евклида

Еще одна теорема, непосредственно связанная с простыми числами. Она говорит;

Если некоторое простое число P делит произведение чисел X и Y без остатка, то оно может делить и X, и Y точно так же.

Звучит немного сложно, но на самом деле все довольно просто. Итак, возьмем к примеру P = 2, X = 6, Y = 9. И тогда получается, что

Х * У = 6 * 9 = 54

В нашем примере P делит это произведение без остатка:

(Х * У) / Р = 54 / 2 = 27

Таким образом, наше P может делиться без остатка либо на X, либо на Y. Это, очевидно, X:

Х/П = 6/2 = 3

Y/P = 9/2 = 4,5 (не подходит)

Решето Эратосфена

При составлении таблицы простых чисел следует учитывать, что такая задача требует последовательной проверки чисел, от 2 до 100. Если делитель отсутствует, то он записывается в таблицу, если составной, то он в таблицу не вносится.

Давайте рассмотрим шаг за шагом.

Если начать с числа 2, то у него всего 2 делителя: 2 и 1, а значит, его можно занести в таблицу. То же самое и с числом 3. Число 4 сложное, его надо разложить на 2 и 2. Число 5 простое, а значит, его можно зафиксировать в таблице. Делайте это до 100.

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

Метод с использованием сита Эратосфена считается наиболее практичным. Давайте посмотрим на таблицы ниже. Для начала записываются числа 2, 3, 4,…, 50.

Теперь вам нужно зачеркнуть все числа, кратные 2. Сделайте последовательное зачеркивание. Получаем таблицу вида:

Затем вычеркиваем все числа, кратные 3. Получаем таблицу вида:

Переходим к вычеркиванию чисел, кратных 5. Получаем:

Вычеркиваем числа, кратные 7, 11. В итоге таблица выглядит так

Перейдем к формулировке теоремы.

Теорема 3

Наименьший положительный делитель числа а, отличный от 1, не больше а, где а — арифметический корень данного числа.

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

В качестве наименьшего делителя составного числа а необходимо указать b.Найдется целое число q, где a=b·q, и мы имеем, что b≤q. Неравенство вида b>q недопустимо, так как условие нарушается. Обе части неравенства b≤q нужно умножить на любое положительное число b, отличное от 1. Получаем, что b·b≤b·q, где b2≤a и b≤a.

Из доказанной теоремы видно, что удаление чисел в таблице приводит к необходимости начинать с числа, равного b2 и удовлетворяющего неравенству b2≤a. То есть, если зачеркнуть числа, кратные 2, процесс начинается с 4, а те, что кратны 3, с 9 и так далее до 100.

составление такой таблицы с использованием теоремы Эратосфена утверждает, что при удалении всех составных чисел останутся простые числа, не превосходящие n.В примере, где n=50, мы имеем n=50. Отсюда получаем, что решето Эратосфена отфильтровывает все составные числа, не превышающие значения корня из 50. Поиск чисел производится путем зачеркивания.

Как быстро и легко определить простые числа

И еще одно понятие, которое связано с простыми числами. Он назван в честь другого древнегреческого математика, Эратосфена из Кирены.

Этот человек придумал быстрый и простой способ определения простых чисел. В частности, он сделал таблицу, в которую были внесены значения до 1000.

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

Кстати, пользоваться ситом Эратосфена очень просто. Например, давайте создадим таблицу до 50.

После этого необходимо зачеркнуть числа, кратные 2, 3, 5, 7 и 11. Результат такой:

Остальные числа являются простыми числами. Вы можете сравнить этот ряд с тем, который мы привели в начале статьи. Точно так же можно составить абсолютно любой ряд простых чисел = хоть до тысячи, хоть до миллиона и больше.

Данное число простое или составное?

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

Пример 1

Докажите, что 898989898989898989 — составное число.

Решение

Сумма цифр данного числа равна 9 8+9 9=9 17. Следовательно, число 9 17 делится на 9 по знаку делимости на 9. Отсюда следует, что оно составное.

Такие признаки не способны доказать примитивность числа. Если требуется проверка, следует предпринять другие шаги. Самый правильный способ — считать числа. В процессе можно найти простые и составные числа. То есть числа по значению не должны превышать а.То есть число а надо разложить на простые множители, если это верно, то число а можно считать простым.

Пример 2

Определите составное или простое число 11723.

Решение

Теперь нам нужно найти все делители числа 11723. Нам нужно вычислить 11723.

Отсюда мы видим, что 11723<200, тогда 2002=40 000, а 11 723<40 000. Получаем, что делители числа 11 723 меньше 200.

Для более точной оценки числа 11723 необходимо записать выражение 1082=11664, а 1092=11881, тогда 1082<11723<1092. Отсюда следует, что 11723<109. Видно, что любое число меньше 109 считается делителем данного числа.

Путем разложения получаем, что 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83 , 89, 97, 101, 103, 107 — все простые числа. Весь этот процесс можно изобразить как деление столбца. То есть деление 11723 на 19. Число 19 является одним из множителей, так как мы получаем деление без остатка. Изобразим деление столбиком:

Отсюда следует, что 11723 — составное число, так как помимо самого себя и 1 оно имеет делитель 19.

Ответ: 11723 — составное число.

Как определить, является ли число простым?

Очень простой способ узнать, является ли число простым, — это разделить его на простое число и посмотреть, является ли оно целым числом. Во-первых, попробуйте разделить его на 2 и/или 3. Если вы получили целое число, оно не простое.

Если после первого деления у вас не получилось целое число, попробуйте разделить его на другие простые числа: 5, 7, 11 и так далее (на 9 делить не нужно, потому что это не простое число и оно делится на 3, но с вами уже поделились).

Более структурированный метод — сито Эратосфена.

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

Это натуральные числа, у которых 1 является единственным общим делителем. Например:

• 14 (это 2 х 7) и 15 (это 3 х 5), единственный общий делитель 1; если числа следуют друг за другом (например, 13 и 12 или 10 и 11), они всегда будут взаимно простыми;
• 7 (это 7 х 1) и 11 (это 11 х 1) — два простых числа, а это означает, что единственный общий делитель всегда будет равен единице, простые числа всегда взаимно просты;
• или 30 и 48 не взаимно просты, потому что 6 х 5 = 30 и 6 х 8 = 48 и 6 является наибольшим общим делителем, то есть: НОД (30; 48) = 6.

Пример 1

Докажите, что числа 84 и 275 взаимно просты.

Как мы можем доказать:

Давайте проверим таблицу простых чисел. 84 и 275 не являются простыми, поэтому нельзя сразу сказать, что они взаимно просты.

Рассчитаем НОД. Мы используем алгоритм Евклида, чтобы найти НОД:

275 = 84 * 3 + 23

84 = 23 * 3 + 15

23 = 15 * 1 + 8

15 = 8 * 1 + 7

8 = 7 * 1 + 1

7=7*1

НОД (84, 275) = 1

Мы доказали, что числа 84 и 275 взаимно просты.

Определение взаимно простого числа может быть расширено до трех или более чисел.

Целые числа a 1 , a 2 ,…, ak , где k > 2, называются взаимно простыми, если наибольший общий делитель этих чисел равен единице.

То есть, если набор целых чисел имеет положительный общий делитель, отличный от единицы, то эти целые числа не взаимно просты.

Подумайте о примерах.

Любой набор простых чисел образует набор взаимно простых чисел, например, 2, 3, 11, 19, 151, 293 и 677 взаимно просты. А четыре числа 12, −9, 900 и −72 не взаимно просты, поскольку имеют положительный общий делитель 3. Числа 17, 85 и 187 также не взаимно просты, поскольку каждое из них делится на 17.

Как определить относительные простые числа:

• найти наибольший общий делитель этих чисел,
• сделать вывод на основе определения взаимно простого.

Пример 2

Являются ли числа 331, 463 и 733 взаимно простыми?

Как мы спорим:

Давайте посмотрим на таблицу простых чисел. Мы видим, что 331, 463 и 733 простые. Следовательно, они имеют единственный положительный общий делитель — единицу. Следовательно, 331, 463 и 733 — относительно простые числа.

Ответ: да.

Пример 3

Докажите, что числа −14, 105, −2 · 107 и −91 не взаимно просты.

Как мы спорим:

Найдите НОД данных чисел и убедитесь, что он не равен единице.

Делители отрицательных целых чисел такие же, как делители соответствующих противоположных чисел. Итак, НОД(-14, 105, 2107, -91) = НОД(14, 105, 2107, 91). Давайте посчитаем:

НОД (14, 105, 2,107, 91) = 7.

Мы обнаружили, что наибольший общий делитель исходных чисел равен семи, поэтому эти числа не взаимно просты. Доказано.

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

Такие числа обладают некоторыми практически важными свойствами. Перечислим их по порядку и докажем.

Определение 3

Если мы разделим целые числа a и b на число, соответствующее их наибольшему общему делителю, мы получим взаимно простые числа. Другими словами, числа a: gcd(a, b) и b: gcd(a, b) взаимно просты.

Мы уже доказали это свойство. Доказательство можно найти в статье о свойствах наибольшего общего делителя. Благодаря этому мы можем определить пары взаимно простых чисел: просто возьмите два целых числа и разделите их на НОД. В результате должны получиться взаимно простые числа.

Определение 4

Необходимым и достаточным условием взаимной простоты чисел a и b является существование целых чисел u0 и v0 таких, что выполняется равенство a·u0+b·v0=1.

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

Начнем с доказательства необходимости этого условия. Допустим, у нас есть два взаимно простых числа, обозначенных буквами a и b, тогда по определению этого понятия их наибольший общий делитель будет равен единице. Из свойств НОД мы знаем, что для целых чисел a и b существует соотношение Безу a u0+b v0=gcd (a, b). Отсюда получаем, что a·u0+b·v0=1. После этого нужно доказать достаточность условия. Пусть верно равенство a u0+b v0=1, в этом случае, если НОД (a, b) делит и a, и b, то он будет делить и сумму a u0+b v0, и единицу соответственно (это может быть аргументируется на основе свойств делимости). А это возможно только в том случае, если gcd (a, b)=1, что доказывает взаимную простоту a и b.

Действительно, если a и b взаимно просты, то согласно предыдущему свойству будет выполнено равенство a·u0+b·v0=1. Умножаем обе части на c и получаем, что a·c·u0+b·c·v0=c. Мы можем разделить первый член ac u0+bc v0 на b, так как это возможно для ac, а второй член тоже делится на b, так как один из множителей равен b. Отсюда заключаем, что вся сумма может делится на b, а так как эта сумма равна c, то c можно разделить на b.

Определение 5

Если два целых числа a и b взаимно просты, то gcd (ac, b)=gcd (c, b).

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

Докажем, что НОД (ac, b) делит НОД (c, b), а затем докажем, что НОД (c, b) делит НОД (ac, b), что докажет справедливость равенства НОД (ac , б) = НОД (в, б).

Так как gcd(ac, b) делит и ac, и b, а gcd(ac, b) делит b, то он будет делить и b c. Следовательно, gcd (ac, b) делит и ac, и bc, следовательно, в силу свойств НОД, он делит НОД (ac, bc), что будет равно c НОД (a, b)=c. Следовательно, gcd(ac, b) делит и b, и c, следовательно, gcd(c, b) также делит).

Можно также сказать, что поскольку НОД (с, b) делит и с, и b, то он будет делить и с, и а с. Следовательно, НОД (с, b) делит и ас, и b, а значит, также делит НОД (ас, б).

Таким образом, НОД (ac, b) и НОД (c, b) делят друг друга, а значит, равны.

Определение 6

Если числа из последовательности а1, а2,…, ак взаимно просты по отношению к числам из последовательности Ь1, Ь2,…, Ьт (при натуральных значениях к и т), то их произведения а1, а2.. ак и b1 b2 …·bm также взаимно просты, особенно a1=a2=…=ak=a и b1=b2=…=bm=b, тогда ak и bm взаимно просты.

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

Согласно предыдущему свойству можно записать следующие равенства: НОД (a1·a2·…ak, bm) = НОД (a2·…·ak, bm) =…=НОД (ak, bm) =1. Возможность последнего перехода обеспечивается предположением, что ak и bm взаимно просты. Следовательно, НОД (a1 a2 . ak, bm) = 1.

Положим a1 a2 . ak=A и получим, что НОД (b1 b2 . bm, a1 a2 . ak) = НОД (b1 b2 . bm, A)= НОД (b2 …·b·bm, A)=… = НОД(бм, А)=1. Это будет верно из-за последнего равенства из построенной выше цепочки. Таким образом, мы получили равенство gcd (b1 b2 . bm, a1 a2 . ak) = 1, которое можно использовать для доказательства взаимной простоты произведений a1 a2 . ak и b1 b2 . ak bm

Это все свойства взаимно простых чисел, о которых мы хотели бы вам рассказать.

Свойство 1

Числа, полученные делением целых чисел a и b на их наибольший общий делитель, называются взаимно простыми. То есть a : gcd(a, b) и b : gcd(a, b) взаимно просты.

Это свойство взаимно простых чисел помогает находить пары взаимно простых чисел. Для этого достаточно взять два целых числа и разделить их на наибольший общий делитель. В результате получаем взаимно простые числа.

Свойство 2

Необходимым и достаточным условием взаимной простоты чисел a и b является наличие целых чисел u0 и v0 таких, что выполняется равенство au0 + bv0 = 1.

Докажем эту необходимость:

Пусть числа а и b взаимно просты. Тогда по определению взаимно простого НОД (a, b) = 1. А из свойств НОД мы знаем, что для целых чисел a и b верно соотношение Безу au0 + bv0 = gcd (a, b). Следовательно, au0 + bv0 = 1.

Коэффициент Безу представляет собой представление НОД целых чисел в виде их линейной комбинации с целочисленными коэффициентами.

Докажем достаточность:

Пусть верно равенство au0 + bv0 = 1. Поскольку НОД (a, b) делит и a, и b, то НОД (a, b) может делить сумму au0 + bv0 в рамках свойства делимости, а значит, и единицу . А это возможно только при НОД (а, b) = 1. Следовательно, a и b взаимно просты.

Свойство 3

Если числа a и b взаимно просты, а произведение ac делится на b, то c делится на b.

На самом деле, поскольку a и b взаимно просты, из предыдущего свойства следует равенство au0 + bv0 = 1. Если мы умножим обе части этого равенства на c, то получим acu0 + bcv0 = c.

Первый член суммы acu0 + bcv0 делится на b, так как ac делится на b при условии, что второй член этой суммы также делится на b, так как один из множителей равен b вся сумма делится на b, а так как сумма acu0 + bcv0 равна c, то c тоже делится на b.

Свойство 4

Если числа a и b взаимно просты, то gcd(ac, b) = gcd(c, b).

Во-первых, покажем, что НОД (ac, b) делит НОД (c, b), а во-вторых, что НОД (c, b) делит НОД (ac, b), это докажет равенство НОД (ac, b)) = НОД(с, б).

НОД (ac, b) делит и ac, и b, а так как НОД (ac, b) делит b, то он также делит и bc. То есть НОД(ac,b) делит и ac, и bc, следовательно, в силу свойств наибольшего общего делителя, делит и НОД(ac,bc), который по свойствам НОД равен c * gcd (a , b) = c. Таким образом, gcd (ac, b) делит и b, и c, следовательно, gcd (c, b) также делит).

С другой стороны, gcd (c, b) делит и c, и b, а поскольку он делит c, то делит и ac. Следовательно, gcd(c, b) делит и ac, и b, следовательно, gcd(ac, b) также делит).

Итак, мы показали, что НОД (ac, b) и НОД (c, b) делят друг друга, а значит, они равны.

Свойство 5

Если числа из последовательности a1, a2, …, ak взаимно просты с каждым из чисел b1, b2, …, bm (где k и m — некоторые натуральные числа), то произведения равны a1 * a2 *…*ak и b1 *b2 * …*bm взаимно простое число. В частности, если a1 = a2 =…= ak = a и b1 = b2 =…= bm = b, то ak и bm взаимно просты.

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

Gcd (a1 *a2 *…*ak , bm) = gcd (a2 *…*ak , bm) =…= gcd (ak , bm) = 1, где возможен последний переход, так как ak и bm взаимно просты по условию.

Таким образом, НОД (a1 *a2 *…*ak, bm) = 1.

Теперь, обозначая a1 *a2 *…*ak = A, мы имеем gcd (b1 *b2 *…*bm , a1 *a2 *…*ak) = gcd
(b1 *b2 *…*bm, A) = НОД (b 2 *…*bm, A) =… = НОД (bm, A) = 1.

Итак, мы получили равенство gcd (b1 *b2 *…*bm , a1 *a2 *…*ak) = 1, что доказывает, что произведения a1 *a2 *…*ak и b1 *b2 *…*bm взаимно просты.

Понятие попарно простых чисел

Как только мы узнаем, что такое взаимно простые числа, мы можем сформулировать определение четных простых чисел.

Определение 7

Четные простые числа — это последовательность целых чисел a1, a2,…, ak, где каждое число взаимно просто по отношению к другим.

Примером последовательности четных простых чисел может быть 14, 9, 17 и -25. Здесь все пары (14 и 9, 14 и 17, 14 и -25, 9 и 17, 9 и -25, 17 и -25) взаимно просты. Обратите внимание, что взаимно простое условие является обязательным для четных простых чисел, но взаимно простые числа не будут четными простыми числами во всех случаях. Например, в последовательности 8, 16, 5 и 15 числа не такие, так как 8 и 16 не будут взаимно простыми.

Также следует остановиться на понятии множества из определенного числа простых чисел. Они всегда будут и взаимно, и попарно простыми. Примером может служить последовательность 71, 443, 857, 991. Когда речь идет о простых числах, термины взаимная и попарная простота будут совпадать.

Число Мерсенна

Простое число Мерсенна — это простое число в форме:

До 1536 года многие считали, что все числа этого типа простые, пока математик Ульрих Ригер не доказал, что 2 (^11) — 1 = 2047 составное (23 х 89). Затем появились другие составные числа (p = 23, 29, 31, 37 и т д.).

Например, для p = 23 это 2 (^23) — 1 = 8 388 607; И 47 х 178481 = 8 388 607, так что это составное число.

Почему 1 не является простым числом?

Русские математики Боревич и Шафаревич в своей знаменитой работе «Теория чисел» (1964) определяют простое число как p (элемент кольца D), который не равен ни 0, ни 1. А p можно назвать простым числом, если оно не может быть факторизовано ab (т е p = ab), и ни одно из них не является единицей в D. Поскольку 1 не может быть представлено ни в одной из форм, 1 не считается ни простым, ни составным числом.

Почему 4 не является простым числом?

Простое число — это натуральное число больше 1, которое без остатка делится на 1 и само на себя. Поскольку 4 делится на 1, 2 и 4, число, которое делится на 2, не является простым числом.

Самое большое простое число

21 декабря 2018 года Великий поиск простых чисел Мерсенна в Интернете (проект, направленный на открытие новых простых чисел Мерсенна) обнаружил новое самое большое известное простое число:

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