C: Елементарна теорія чисел

Last updated
Save as PDF

Page ID: 105496

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Тут ми розглянемо деякі основні числові теоретичні визначення та результати. Здебільшого ми просто викладемо результати. Для більш детального лікування студенту направляють посилання, або наведені в бібліографії. Якщо інше не вказано в цьому додатку, всі малі літери,$a$,$b$$c$, і т.д. будуть цілими числами. Нагадаємо, що ми використовуємо$\mathbb{N}$ для позначення безлічі натуральних чисел (також відомих як натуральні числа) і використовуємо$\mathbb{Z}$ для позначення множини всіх цілих чисел, тобто,\[\nonumber \mathbb{N}= \{ 1,2,3, \dots \}\] і\[\nonumber \mathbb{Z}= \{ \dots, -3,-2,-1,0,1,2,3,\dots \}.\]

Визначення C.1:

Нехай$a,b \in \mathbb{Z}$. Ми говоримо$b$ ділить$a$ і пишемо,$b\ \vert\ a$ якщо є елемент$c \in \mathbb{Z}$ такий, що$a=bc$. Пишемо$b \ \not \vert \ a$ якщо$b$ не ділимо$a$.

Якщо$b \ \vert \ a$ ми також іноді говоримо, що$b$ це фактор$a$ або що$a$ є кратним$b$. Щоб сказати, якщо$b$ ділить$a$ де$b \neq 0$, ми просто ділимо$a$ на$b$ і подивитися, якщо залишок 0 чи ні. У загальному плані ми маємо наступний фундаментальний результат.

Лемма$\PageIndex{1}$ (The Division Algorithm)

Для будь-яких цілих чисел$a$ і$b$ з$b \neq 0$ існують унікальні цілі числа$q$ і$r$ такі, що\[ \nonumber a = bq+r, \qquad 0 \le r < |b|.\]

Визначення C.2:

Число$r$ в наведеній вище Лемма позначається знаком$a \bmod b$.

Наприклад, у нас є

\[ \nonumber 17 \bmod 5 = 2 \qquad \mbox{ since \quad $17 = 3 \cdot 5 + 2$ \ and \ $0 \le 2 < 5$}\]і\[ \nonumber (-17) \bmod 5 = 3 \qquad \mbox{ since \quad $-17 = (-4) \cdot 5 + 3$ \ and \ $0 \le 3 < 5$}.\]

Визначення C.3:

Ціле число$p$ вважається простим, якщо$p \ge 2$ і єдиними додатними факторами$p$ є$p$ і 1.

Визначення C.4:

$b$Дозволяти$a$ і бути цілими числами, принаймні одне з яких є ненульовим. Найбільшим спільним дільником$a$ і$b$ є найбільшим натуральним числом$\gcd(a,b)$, яке ділить обидва$a$ і$b$. Визначаємо$\gcd(0,0)=0$.

Визначення C.5:

Якщо$a$ і$b$ є ненульовими цілими числами, найменше спільне$b$ кратне$a$ і є найменшим натуральним числом$\text{lcm}(a,b)$, тобто кратним обом$a$ і$b$. Якщо$a=0$ або$b=0$, ми визначаємо$\text{lcm}(a,b) = 0$.

Важливе властивість простих чисел надає наступна лема.

Лемма$\PageIndex{2}$

Якщо$p$ просте, а$p | ab$ потім$p | a$ або$p | b$.

Мабуть, найбільш фундаментальним результатом, що стосується цілих чисел, є наступна теорема, яку іноді називають Фундаментальною теоремою арифметики.

Теорема$\PageIndex{3}$

Якщо$n \ge 2$ є цілим числом, то існує унікальний список простих чисел$p_1, p_2, \dots, p_k$, який дотримуються наступних двох умов:

$p_1 \le p_2 \le \cdots \le p_k$,
$n = p_1 p_2 \cdots p_k$

Наприклад, якщо$n=72$ унікальний список простих чисел - 2, 2, 2, 3, 3.

Тепер виправте додатне ціле число$n$. Нагадаємо, що$\mathbb{Z}_n = \{ 0, 1, \dots , n-1 \}$ і що множення і додавання в$\mathbb{Z}_n$ визначаються

$a + b =$залишок, коли звичайна сума$a$ і$b$ ділиться на$n$, і

$a \cdot b =$залишок при звичайному добутку$a$ і$b$ ділиться на$n$.

Щоб полегшити доказ того, що ці дві бінарні операції асоціативні, ми тимчасово позначимо додавання в$\mathbb{Z}_n$ на$\oplus$ і множення в$\mathbb{Z}_n$ на$\odot$. Таким чином ми можемо використовувати$+$ і$\cdot$ для звичайного додавання і множення в$\mathbb{Z}$. Таким чином, ми маємо\[\begin{aligned} a \oplus b &=&(a + b) \bmod n \\ a \odot b &=& (ab) \bmod n\end{aligned}\]

Теорема$\PageIndex{4}$

$n$Дозволяти бути натуральним цілим числом. Визначте$f: \mathbb{Z}\to \mathbb{Z}_n$ за правилом$f(a) = a \bmod n$. Тоді

\[\begin{align} f(a + b) = f(a) \oplus f(b) \label{C1}\end{align}\]

\[\begin{align} f(a \cdot b) = f(a) \odot f(b). \label{C2} \end{align}\]

Доказ Нехай$r_1 = f(a)$ і$r_2 = f(b)$. Це означає, що\[a = nq_1 + r_1, \quad 0 \le r_1 < n\] і\[b = nq_2 + r_2, \quad 0 \le r_2 < n\] звідси\[a+b= nq_1 + r_1 + nq_2 + r_2 = n(q_1+q_2) + r_1+r_2\] зараз\[f(a) \oplus f(b) = r_1 \oplus r_2 = r\] де\[r_1 + r_2 = qn + r, \quad 0 \le r < n\] Звідси\[a+b=n(q_1+q_2+q) + r, \quad 0 \le r < n\] і випливає, що\[f(a+b)=(a+b) \bmod n = r,\] і ми робимо висновок, що\[f(a+b) = r = f(a) \oplus f(b).\] Це доводить (С.1). Доказ (С.2) схожий і залишається зацікавленому читачеві.

Слідство$\PageIndex{5}$

Бінарні операції$\oplus$ і$\odot$ on$\mathbb{Z}_n$ є асоціативними.

Доказ Використовуючи позначення в теоремі, ми маємо for$a,b,c \in \mathbb{Z}_n$:$f(a) = a$,$f(b) = b$ і$f(c) = c$. Звідси\[\begin{aligned} (a \oplus b) \oplus b &=& (f(a) \oplus f(b)) \oplus f(c)\\ &=& f(a+b) \oplus f(b) \\ &=& f( (a+b)+c)\\ &=& f(a + (b+c)) \\ &=& f(a) \oplus f(b+c) \\ &=& f(a) \oplus( f(b) \oplus f(c)) \\ &=& a \oplus (b \oplus c)\end{aligned}\] Це доводить,$\oplus$ що асоціативно на$\mathbb{Z}_n$. Доказ для$\odot$ аналогічний і залишений зацікавленому читачеві.

Визначення C.1:

Лемма\(\PageIndex{1}\) (The Division Algorithm)

Визначення C.2:

Визначення C.3:

Визначення C.4:

Визначення C.5:

Лемма\(\PageIndex{2}\)

Теорема\(\PageIndex{3}\)

Теорема\(\PageIndex{4}\)

Слідство\(\PageIndex{5}\)