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

Теорема 1.15. Всякое целое число

У

n >1 однозначно раскладывается в

произведение простых множителей:

Т

n = p1 p2 K ps .

(1.3)

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

непосредственно. Пусть n >1 и предположим, что утверждение теоремы верно

для всех натуральных чисел, меньших n. Согласно теореме 1.5 число n либо яв-

ляется простым (тогда теорема доказана), либо делится на некоторое простое

число p. Тогда n = pm для натурального m

Б

< n . По предположению индукции

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

доказано существование разложения всякого натурального Нчисла в произведе-

ние простых множителей.

Единственность разложения доказывается методом от противного. Пред-

и

положим, что натуральное число n имеет два различных разложения в произве-

дение простых множителей:

р

й

n =

p1

p2 K

ps =

q1 q2 K qt .

(1.4)

Предположим,

что

t ≤ s . В силу леммы 1.1 левая часть этого равенства

делится на

q1 .

Если

общий

то

согласно лемме 1.2

произведение

НОД(p1, q1 )=1,

от

p2 p3 K ps делится на q1 . Рассуждая и далее аналогичным образом, найдем

некоторый множитель

pk , делящийся на q1 , то есть найдем pk

= q1. Сократим

равенство

(1.4)

на

э

множитель. Аналогично

рассуждаем

с

q2 q3 K qt . В конце концов, придем к соотношению

p p

K p

=1,

(1.5)

1

Но

2

s−t

где pi ,1 ≤ i ≤ s −t –

ине сократившиеся простые множители левой части равен-

ства (1.4).

единицазне может делиться ни на одно из простых чисел. Следо-

вательно, s = t , и на самом деле равенство (1.5) имеет вид 1 =1. Это и означает

единственность разложения в произведение простых множителей с точностью

до порядка следования этих множителей. Теорема доказана.

Р

Если в равенстве

n = p p

2

K p

s

собрать одинаковые множители,

то

п

1

получим сл дующее каноническое разложение целого числа:

еr1

r2

rt

.

n =

p1

p2

K pt

ложим

эти

числа

на

простые

множители:

126 = 2 32 7; 330 = 2 3 5 11.

НОД(a,b)= 2 3 = 6, НОК(a,b)= 2 32 57 11 = 6930 .

б)

a = 525, b = 385; 525 = 3 52 7; 385 = 5 7 11; НОД(a,b)= 5 7 = 35 ;

НОК(a,b)= 3 52 7 11 = 5775 .

Следует отметить, что теорема 1.15 – это теорема существования. Она не

У

дает метода факторизации натурального числа в произведение простых сомно-

жителей. Поиск эффективного метода

факторизации целых

чисел

оказался

Т

сложной алгоритмической проблемой, причем более сложной, чем распознава-

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

ется полиномиальным относительно n. Безуспешные и настойчивые поиски та-

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

имеет

экспоненциальную

сложность.

Данное

обстоятельство, в частности,

обеспечивает стойкость криптосистемы RSA.

Б

1.6. Сравнения

Н

Теорема 1.16. Пусть m – натуральное число, m >1. Для любых целых чи-

и

сел a и b следующие условия равносильны:

1) a и b имеют одинаковые остатки от деления на m;

2)

a −b делится на m, то есть a −b = mqйдля подходящего целого q;

3)

a = b +mq для некоторого целого q.

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

по

пров дится

схеме: 1) 2) 3) 1) . Из условия 1

следует условие 2: если

т

+ r , то a −b

= m(q

− q

),

что озна-

a

= mq + r, b = mq

2

1

р2

1

чает делимость a −b на m. Из усл вия 2 a

−b = mq следует a = b +mq . Дока-

жем,

что из

Если

то из равенства

a = b

+mq получаем:

3) 1) .

b = ms +r ,

з

a = ms + r + mq = m(s + q)+ r , .е. a и b имеют одинаковые остатки от деления на

m. Теорема

ана.

дока

Целые числа a и b называются сравнимыми по модулю

Определение 1.6.

m, если они уд влетв ряют одному из условий теоремы 1.16. Этот факт обо-

п

≡ b(mod m) или a ≡ b(m). Данное соотношение между це-

значают ф рмул й a

целого

лыми числами называют сравнением по модулю m.

Р

Прим р 1.6. −4 ≡ 2(mod 3)≡ 5(mod 3)≡ 8(mod 3)≡14(mod 3).

Основные свойства сравнений.

Свойство 1. Пусть a ≡ b(mod m). Тогда (a ±c)= (b ±c)(mod m) для всяко-

го

c, то есть к обеим частям сравнения можно добавить (или вычесть

из обеих частей) одно и то же число.

Доказательство. a ≡ b(mod m) тогда и только тогда, когда a −b = mq для

подходящего целого q.

Следовательно,

(a + c)−(b + c)= mq , то есть

(a +c) и

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

третьему

условию

теоремы

1.16

a = b +mq; c = d +mw для

подходящих

целых

q

и

w.

Тогда

ac = bd + m(qd +bw + mqw). Согласно тому же третьему условию,

это означает,

что ac ≡ bd(mod m).

Свойство 4. Сравнения можно почленно возводить в натуральную сте-

пень: если a ≡ b(mod m), то an ≡ bn (mod m).

У

Доказательство непосредственно следует из доказанного свойства 3.

Свойство 5. Если в сравнении a ≡ b(mod m) числа a, b, m имеют общий

множитель

d,

то

на

него

сравнение

можно

Т

сократить:

(a / d )

≡ (b / d )(mod(m / d )).

Н

Доказательство. Пусть a = da1, b = db1, m = dm1 . Согласно третьему усло-

вию теоремы 1.16

a = b +mq , то есть da1 = db1 + dm1q . Сократив данное равен-

Б

ство на d, получим равенство a1 = b1 + m1q , означающее сравнимость целых a1

и b1 по модулю m1 .

йть на общий множитель, взаим-

Свойство 6. Сравнение можно

но простой с модулем: если

a = da1, b = db1, НОД(d, m)=1, то из сравнения

da ≡ db (mod m)=1 следует сравним стьиa b по модулю m: a

≡ b

(mod m).

1

1

1

1

1

1

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

р му усл вию теоремы 1.16

da −db

= mv

для

подходящего целого v. След ва

сократ

1

1

, произведение mv делится на d. Посколь-

ку НОД(d, m)

=1, то согласно лемме 1.2 целое v делится на d: v = dv . Следова-

тельно, a1 = b1 + mv1, то ес ь

ельно

1

a1 ≡ b1(mod m), что и требовалось доказать.

вт

Свойства 1–6 относятся к арифметическим свойствам сравнений. Срав-

нимость целых чисел по данному модулю m определяет бинарное отношение

Rmod m

и

на мн жестве целых чисел: два целых числа находятся в отношении

з

когда они сравнимы друг с другом по модулю m.

Rmod m , т гда и т лько тогда,

р веряются следующие свойства названного бинарного отношения.

о

Свойство 7.

Рефлексивность: a ≡ a(mod m) для любого целого a и всякого

натурального m >1.

п

Симметричность: если a ≡ b(mod m), то b ≡ a(mod m).

Свойство 8.

Свойство 9. Транзитивность:

если

a ≡ b(mod m), b ≡ c(mod m),

то

Легко

Р

ми от деления на m эти классы будем обозначать через

Таким

0,1,2,K, m −1.

образом,

={mq +i

q Z} для каждого целого i = 0,1,2,K, m −1.

Любой

класс i

У

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

mq +i класс

mq +i

. Поскольку остаток – на латыни residu – переводится на

= i

Т

русский как вычет, то множество всех классов по данному модулю сравнимых

друг с другом чисел называют множеством классов вычетов по модулю и обо-

значают через Z / mZ . В силу сказанного

Z / mZ = {

K,

m −1} – множество

0,1,2,

из m элементов.

Н

такой

Определим операции сложения на Z / mZ . Полагаем суммой k

l

Б

единственный класс z из Z / mZ , в который попадают все суммы k1 +l1 и

k2 + l2 для k1

, k2 k

, l1,l2 l

, а произведен

ем kl

– тот класс из Z / mZ , в кото-

й

рый попадают произведения k l

для k k , l l .

Поскольку сложение и

в Z / mZ однозначно определяются

и

умножением представителей класс в, то свойства операций сложения и умно-

жения целых чисел справедливы и врZ / mZ :

1)

k

l = l k ; lk = kl – к ммутативность;

умножение

2)

k (l r )= (k l ) r; k (lr )= (kl )r – ассоциативность;

3)

нейтральный

;

существует элемент: k

0

= k

; k

1

= k

4)

для

Z / mZ

такой, что

k

существует единственный класс l

и

k l = 0

, им является l = m −k ;

5)

(k

)

r

з= (kr ) (l

r

) – дистрибутивность.

l

Далее

ерации сложения и умножения в этом кольце будем обозначать

стандартными символами «+» и «–».

всякого

Таким образом, Z / mZ является коммутативным кольцом с единицей.

Опр

Z / mZ называется обратимым, если най-

деление 1.7. Элемент k

д тся такой класс l Z / mZ , что k

l =

1

. Тогда класс l

называют обратным

е

к классу k .

об-

Из ассоциативности умножения в кольце Z / mZ вытекает, что если k

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