Вопросы к гос. экзамену по дисциплине "Математика – Алгебра"
Опр.2 Натуральное число р называется простым, если оно имеет ровно два различных делителей. (1 и само число р), составным, если имеет более двух делителей.
Введенное определение позволит выражать числа натуральные через простые. Это описывается теоремой, которую называют основной теоремой арифметики.
Теорема. 3 Любое n Î N , n > 1 можно единственным образом представить в виде произведения простых чисел с точностью до перестановки сомножителя.
В теореме содержится две теоремы: о существовании разложения и его единственности.
(7) Пусть n Î N , n > 1. Для доказательства исследуем метод математической индукции.
n = 2, 2 – простое число, следовательно n = 2 и есть его разложение.
Предположим, что для любого натурального числа, меньшего n, теорема верна и докажем для n.
Пусть дано натурально n, если оно простое, то это и есть его разложение. Если n составное, тогда n = вс, где в,с Î N и меньше n. По предположению индукции разложение их на простые множители существует, поэтому оно существует и для n. На основании принципа математической индукции, можно утверждать истенность теоремы для любого n Î N , n > 1.
(!) Докажем единственность разложения на простые множетели методом математической индукции.
n = 2, 2 = 2. Разложение единственное.
Допустим, что для любого числа натурального, меньшего n утверждение справедливо и докажем для n. Если n простое число, то это и есть его разложение и оно единственно. Если n составное, то оно допустит разложение на простые числа. Предположим, что таких разложений оказалось два: n = p1p2 ¼ pк = q1q2 … qs (1). Из равенства (1) видно, что “правая часть” делится на p1. А т.к. в “правой части числа простые”, то
существует число qi, которое делится на p1; (p1, qi) = 1. Следовательно, p1 = qi. Пусть qi = q1, разделим обе части равенства (1) на p1, получим, что и “левая часть” и “правая часть” числа натуральные, меньше n, а для них разложение единственное с точночтью до перестановки сомножителя. Поэтому при соответственно мы получаем, что n = p1p2 ¼ pк – разложение n и это разбиение единственное. Что и требовалось доказать.Если среди простых множителей окажутся равные, то их объединяют в степень и получают представление n Î
N
в виде:
, которое называют каноническим разложением натурального числа.
В теории натуральных чисел имеет место теорема, решающая вопрос о количестве простых чисел во множестве N .
Теорема 4. (Евклида) Множество простых чисел в N бесконечно.
Проведем доказательство методо от противного.
Пусть простых чисел конечное число: p1p2 ¼ pк. Рассмотрим N = p1p2 ¼ pк+1. Исследуем полученное число:
1) N > 1 = > оно простое или составное; N ¹ pi, i = 1, к ;
2) N
pi, , i = 1, к =
>
, т.к. при делении на pi получен остаток 1;
N – составное. Если N составное, то ему надлежит делиться на 1, N и еще на какое-нибуть простое число (см. ниже), но это не так, поэтому N не является составным. Полученное противоречие и доказывает теорему.
Теорема 5. Наименьший, отличный от 1 делитель составного числа, является простым числом.
Пусть n Î N имеет делители, отличные от 1. Обозначим тот делитель, который будет наименьшим среди всех делителей. Пусть это натуральное число к, т.е. n = к . m; к, m Î N , к > 1. Исследуем к.
Если к = p – простое число, то теорема верна.
Если к – составное число, то к = к1 m1, тогда n = к1 (m1 m), n
к1, к1 < к, что противоречит выбранному наименьшему значению. Это и доказывает теорему.
Достаточно часто в математике приходитс для числа а Î N выяснять, является оно простым или составным. Для решения подобных задач предложен способ, носящий название “решето Эратосфена…” или способа отсеивания чисел кратных 2,3,…,p,… .
Опишем этот способ.
Если даны числа натурального ряда: 1,2,3,4,5,…,n, то для установления какими они являются: простыми или составными, поступают так: вычеркивают 1,2 и каждое второе, ибо каждое второе начинается от 3, делится на 2, поэтому является составным. Затем повторяем эту процедуру для 3. 3 вычеркивается и каждое третье, ибо 6 – третье по счету за 3, делится на 3. названную процедуру повторяют до простого числа с не превосходящего
. Оставшиеся числа являются простыми.
Такой алгоритм можно использовать и для установления чисел в промежутке от n1 до n2.
Опишем его спецификацию . Если надо установить какие числа в промежутке от n1 до n2 являются простыми, то поступим так:
выясним простое или составное является число n1:
Проверим его делимость на 2,3,5,…p ≤
. Если оно не делится на эти простые числа, то оно простое;
Если оно делится хотя бы на одно из этих чисел, то оно составное.
при выяснении простого числа n, одновременно поступаем так:
2.1 если n1
2, то вычеркивают его и каждый второй (как в первом случае); и переходим к (n1 + 1);
2.2 если n1
2, то к числу добавляем 1 и вычеркиваем n1 + 1 и любое второе за ним;
2.3 если было 2.1, то переходим к (n1 + 1) и проверяется делим его на 3, повторяем процедуру решета Эратосфена переходит к (n1 + 2);
2.4 Если было 2.2, то проверяют делимость на 3;
2.4.1. если n1
3, то проверяю решето Эратосфена и переходят следующему.
не вычеркнутому числу и исследуют его делимое на 5;
2.4.2. если n1 = 3q + r, то в зависимости от r = 1 или r = 2, добавляем 1 или 2 и
n1 + 1, n1 + 2.
И любое третье по счету и т.д.
2.5 Если n1 оказалось простым, то все не вычеркнутые числа тоже простые. Если n1 оказалось составным, а ni – простое, то все стоящие за ni числа остальные простые.