Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Простые и составные числа

Читайте также:
  1. I. Простые времена
  2. I. Простые времена
  3. Б) Составные части реформы
  4. Библия и числа
  5. Выбор числа и мощности главных понизительных трансформаторов
  6. Выбор числа изоляторов.
  7. Глава 11. ТЕЛЕФОННЫЙ ДИАЛОГ И ПРОСТЫЕ ЭРИКСОНИАНСКИЕ ТЕХНИКИ

Теория чисел

ПРОСТЫЕ ЧИСЛА. ДЕЛИТЕЛИ ЧИСЕЛ

Простые и составные числа

Давайте вспомним, что когда число c = a * b является произведением двух чисел a и b, то мы называем а и b множителями или делителями числа с.

Каждое число имеет тривиальное разложение на множители с = 1 * с = с * 1.

Соответственно мы называем числа 1 и с тривиальными делителями числа с.

Любое число с > 1, у которого существует нетривиальное разложение на множители, называется составным.

Если число с имеет только тривиальное разложение на множители, то оно называется простым.

Среди первых 100 чисел простыми являются следующие 25 чисел:

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.

Все остальные числа, кроме 1, являются составными. Мы можем сформулировать следующее утверждение:

Теорема Любое целое число с> 1 является, либо простым, либо имеет простой множитель.

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

Теперь мы подошли к нашей первой важной задаче в теории чисел: как определить, является ли произвольное число простым или нет, и в случае, если оно составное, то как найти какой-либо его нетривиальный делитель?

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

ab > √ с •с,

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

Пример 1. Если с =1973, то находим, что √ с = 44…. Так как ни одно из простых чисел до 43 не делит с, то это число является простым.

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

Другим очень простым методом является применение таблиц простых чисел, т. е. использование простых чисел уже найденных другими. За последние 200 лет было составлено и издано много таблиц простых чисел. Наиболее обширной из них является таблица Д. X. Лемера, содержащая все простые числа до 10 000 000. Наша таблица содержит все простые числа до 1000.

Таблица:

Простые числа среди первой тысячи чисел

 

Упражнение 1. Заметим, что числа от 90 до 96 включительно являются семью последовательными составными числами; найдите четырнадцать последовательных составных чисел.


Дата добавления: 2015-08-05; просмотров: 243 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Стратегические импликации Стратегических Единиц Бизнеса| Основная теорема о разложении на множители

mybiblioteka.su - 2015-2024 год. (0.005 сек.)