8.5: Застосування в теорії чисел

Індукція (або той факт,\(\mathbb{N}\) що добре впорядкований) може бути використаний для доведення багатьох важливих властивостей натуральних чисел. Ось лише три приклади.

Визначення\(8.5.1\).

\(p\)Елемент\(\mathbb{N}^{+}\) є простим iff\(p > 1\) і\(p\) не ділиться на будь-який елемент,\(\mathbb{N}^{+}\) крім 1 і\(p\).

Пропозиція\(8.5.2\).

Якщо\(n \in \mathbb{N}\) і\(n > 1\),\(n\) то ділиться на просте число.

Доказ

Припустимо, існує якесь натуральне число\(n > 1\), таке, що\(n\) не ділиться на просте число. (Це призведе до протиріччя.) Оскільки\(\mathbb{N}\) це добре впорядкований, можна вважати, що\(n\) це найменша така кількість, так:\[\text { If } 1<k<n \text { (and } k \in \mathbb{N} \text { ), then } k \text { is divisible by a prime number. }\]

Оскільки\(n \mid n\), але (за припущенням)\(n\) не ділиться на будь-яке просте число, ми знаємо, що не\(n\) є простим. За визначенням, це означає існує\(k \in \mathbb{N}\), таке, що\(k \mid n\) і\(1 < k < n\). З мінімальності, ми знаємо\(n\), що\(k\) ділиться на деяке просте число\(p\). Потім\(p \mid k\) і\(k \mid n\), так\(p \mid n\). Це суперечить тому,\(n\) що не ділиться на просте число.

Теорема\(8.5.3\) (Fundamental Theorem of Arithmetic).

Кожне натуральне число (крім 0 і 1) є добутком простих чисел (або само по собі є простим).

Доказ

BY CONPRATION: Припустимо, що існує якесь натуральне число\(n > 1\), таке, що не\(n\) є добутком простих чисел (і не є простим). Оскільки\(\mathbb{N}\) це добре впорядкований, можна вважати, що\(n\) це найменша така кількість, так:\[\text { If } 1<k<n \text { (and } k \in \mathbb{N}), \text { then } k \text { is a product of prime numbers. }\]

Оскільки не\(n\) є простим, він ділиться на деяке натуральне число\(k\), з\(1 < k < n\). Це означає, що ми можемо написати\(n = km\), для деяких\(m \in \mathbb{N}^{+}\). Так як\(m = n / k\) і\(1 < k < n\), ми це бачимо\(1 < m < n\). Тому мінімалізм має на\(n\) увазі, що\(k\) і\(m\) є добутком простих чисел: скажімо\(k=p_{1} p_{2} \cdots p_{r}\) і\(m=q_{1} q_{2} \cdots q_{s}\). Тоді\[n=k m=\left(p_{1} p_{2} \cdots p_{r}\right)\left(q_{1} q_{2} \cdots q_{s}\right)\]

є добутком простих чисел. Це протиріччя.

Зауваження\(8.5.4\).

Насправді кожне натуральне число може бути записано тільки одним способом як добуток простих чисел (аж до перестановки порядку множників), але доводити цей факт ми не будемо.

Визначення\(8.5.5\).

Нехай\(a, b \in \mathbb{N}^{+}\). Ми говоримо\(a\) і\(b\) є відносно простими, якщо вони не мають спільних дільників, крім 1. (Тобто, якщо\(k \in \mathbb{N}^{+}\), і\(k\) є дільником обох\(a\) і\(b\), то\(k = 1\). Іншими словами, «найбільший спільний дільник»\(a\) і\(b\) дорівнює 1.)

Теорема\(8.5.6\).

Нехай\(a, b \in \mathbb{N}^{+}\). Якщо\(a\) і відносно\(b\) прості, то існують\(m, n \in \mathbb{Z}\), такі що\(ma + nb = 1\).

Доказ

Нехай\[S=\{m a+n b \mid m, n \in \mathbb{Z} k=\} \cap \mathbb{N}^{+} .\]

Це легко помітити, що\(a \in S\) (дозволивши\(m = 1\) і\(n = 0\)), так\(S \neq \varnothing\). Тому, оскільки\(\mathbb{N}\) це добре впорядкований, ми можемо дозволити\(d\) бути найменшим елементом\(S\). Тоді\(d \in S\), так що у нас є\(d = m_{0}a+n_{0}b\) для деяких\(m_{0}, n_{0} \in \mathbb{Z}\).

За алгоритмом поділу\((5.1.20)\) ми можемо написати\[a=q d+r \text { with } 0 \leq r<d .\]

Так\[r=a-q d=a-q\left(m_{0} a+n_{0} b\right)=\left(1-q m_{0}\right) a+q n_{0} b=m a+n b ,\]

де\(m = 1 − qm \in \mathbb{Z}\) і\(n = qn \in \mathbb{Z}\). З іншого боку, оскільки\(r < d\), і\(d\) є найменшим елементом\(S\), ми знаємо\(r \notin S\). З визначення\(S\), зробимо висновок, що\(r = 0\). Отже\(d \mid a\).

Повторюючи той самий аргумент з\(a\) і\(b\) міняли (\(m_{0}\)а\(n_{0}\) також міняли), ми бачимо, що\(d \mid b\).

Тому\(d\) є дільником обох\(a\) і\(b\). Оскільки\(a\) і\(b\) є відносно простими, ми робимо висновок, що\(d = 1\). Так як\(d \in S\), це означає\(1 \in S\), що встановлює бажаний висновок.

Вправа\(8.5.7\).

Доведіть зворотне теореми\(8.5.6\).

\(8.5.6\)Теорема має фундаментальне значення в теорії чисел, математичному вивченні властивостей\(\mathbb{N}\) і\(\mathbb{Z}\). Ось кілька його багатьох наслідків:

Вправа\(8.5.8\).

Припустимо\(a, b \in \mathbb{N}^{+}\).

1. Показати\(a\) і\(b\) є відносно простими, якщо існує\(x \in \mathbb{Z}\), такий, що\(x a \equiv 1(\bmod b)\).
2. Показати\(a\) і\(b\) є відносно простими iff для всіх\(y \in \mathbb{Z}\), існує\(x \in \mathbb{Z}\), такий що\(x a \equiv y(\bmod b)\).
3. (Китайська теорема про залишок) Припустимо\(a\) і\(b\) є відносно простими. Для всіх\(y_{1}, y_{2} \in \mathbb{Z}\) показати існує\(x \in \mathbb{Z}\), таке, що\(x \equiv y_{1}(\bmod a)\) і\(x \equiv y_{2}(\bmod b)\).

Судження\(8.5.2\) також має важливі наслідки. Наприклад:

Слідство\(8.5.9\).

Прості числа нескінченно багато.

Доказ

ПРОТИРІЧЧЯ: Припустимо, що існує лише скінченно багато простих чисел. Тоді ми можемо скласти список всіх з них:\[\text { The set of all prime numbers is }\left\{p_{1}, p_{2}, \ldots, p_{n}\right\} .\]

Нехай\[N=p_{1} p_{2} \cdots p_{n} .\]

З пропозиції\(8.5.2\), ми знаємо, що є якийсь простий\(p\), такий, що\(p \mid (N + 1)\).

Так як\(p_{1}, p_{2}, \ldots, p_{n}\) це список всіх простих чисел, ми знаємо\(p = p_{i}\), для деяких\(i\). Тому\(p = p_{i}\) є одним із факторів у продукті, який визначає\(N\), так\(p \mid N\). Тому\(p\) ділить обидва\(N\) і\(N + 1\), так (від\(5.1.9(1)\)) у нас\[p \mid((N+1)-N)=1 .\]

З цього випливає\(p = \pm 1\) (див. Стор. 97), що суперечить тому\(p\), що, будучи простим числом, повинен бути\(> 1\).