Целые числа, сравнения — дискретная математика


Z = {…, -3, -2, -1, 0, 1, 2, 3, …}, N={0,1,2,3,…}, N+ = {1,2,3,…}
Теорема (деления целых чисел): Пусть b∈N+. Пусть всякое a∈Z единственным образом представимо в виде a=b*q+r, 0≤0Теорема: Для всяких целых a≥1, h≥r, при некотором S≥0 существует единственное представление a в виде a=aShS + aS-1hS-1 + … + a1h1 + a0, где 0≤ai≤h-1 (i=0,1,…,S-1), 1≤aS≤h-1.

Замечание: Представление a=aShS + aS-1hS-1 + … + a1h1 + a0 есть представление целого числа a в h- ичной системе счисления.
a=(aS,aS-1, …, a1, a0)

Определение: Натуральное число p≤r простое, если p делится только на 1 и на само себя.

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

Теорема (Основная теорема арифметики): Всякое целое число, большее 1, можно единственным образом представить в виде произведения простых множителей (с точностью до их порядка).

Замечание: по теореме о факторизации a=p1a1*p2a2*…*pkak — каноническая факторизация (p1 < p2<…<pk). Иногда в каноническую факторизацию включают отсутствующий множитель в нулевой степени для всех простых чисел от «2» до «pk».

Факторизация простых чисел считается технически трудно осуществимой. Например, число b -120 десятичных знаков для факторизации потребует миллионы лет компьютерного времени.

Определение: Общий делитель ОД (a,b,…,l) для a,b,…,l делит все эти числа. Наибольший общий делитель НОД (a,b,…,l) есть максимум из всех общих делителей для a,b,…,l.
НОД (0,0,…,0)=0.

Теорема: Если a>1, b>1 и их одиночные факторизации a=p1a1*p2a2*…*pSaS, b=p1a1*p2a2*…*pSaS, где p1,p2,…,ps есть все различные простые делители для a и b, то НОД(a,b)=p1min(a1,b1)*p2min(a2,b2)*…*pSmin(aS,bS).

Замечание: Теорема переносится на несколько чисел.

Теорема: ∀a1,…,an∈Z, ∃ λ1, …, λn∈Z такие, что НОД (a1,…,an)=∑λi*ai.

Замечание: ∀a1, a2∈Z, ∃λ1, λ2∈Z такие, что НОД (a1,a2)=λ1*a1 + λ2a2.

Существует расширенный алгоритм Евклида для вычисления λ1 и λ2.

Определение: Общее кратное ОК (a,b,…,l) чисел a,b,…,l есть всякое число, кратное каждому из чисел a,b,…,l, т.е. число, делящееся на каждое из a,b,…,l. Наименьшее общее кратное НОК (a,b,…,l) есть минимум из всех общих кратных для a,b,…,l.

Теорема: Если a=p1a1*p2a2*…*pSaS и b=p1a1*p2a2*…*pSaS есть канонические факторизации для a и b, где p1,p2,…,ps есть все различные простые делители для a и b, то НОК(a,b) = p1max(a1,b1)*p2max(a2,b2)*…*pSmax(aS,bS).

Замечание: [a1,…,an] = a1,…,an/(a1,…,an).

Определение: Функция Эйлера a и φ(a), которые взаимно просты с a.

Замечание: Целые a и b взаимно просты если НОД(a,b)=1.

Определение: Целые числа a и b сравнимы по mod m (a≡b(mod m)), если (a-b):m.

Теорема: Следующие утверждения эквивалентны:
1) (a≡b(mod m)).
2) (a-b):m.
3) Остатки от деления a и b на m одинаковы, т.е. a и b при делении на дают один и тот же остаток.

Замечание: Отношение сравнения целых чисел есть отношения эквивалентности.

Определение: Класс вычетов по mod m есть множество всех чисел, сравнимых между собой по mod m.

Замечание: Класс Cr = {a = m*q + r: q ∈Z, 0≤z≤m-1}.

Определение: Вычет по mod m есть любое число из класса вычетов по mod m.
Пусть m=5.
…-10,-5,0,5,10,… класс C0
…-9,-4,1,6,11,… класс C1
……
…-6,-1,4,9,14,… класс C4

Полная система вычетов есть любой набор вычетов по одному из каждого класса.
Наименьшая неотрицательная полная система вычетов Zm = {0,1,..,m-1}.

Теорема: Если НОД(a,m) и x пробегает полную систему вычетов для Zm.

Замечание: Можно ввести операции над классами вычетов, связав их с операциями в Zm.
a + b(mod m) = rest(a+b, m)
a * b(mod m) = rest(a*b, m)
где операция rest — остаток. Это модульные операции.


Комментарии запрещены.




Статистика