查看“︁初等數論/整數的基本性質”︁的源代码

[[数论]] > [[初等数论]] > [[初等數論/整數的基本性質]]

----

數論是奠基於算術之上的，所以在學習數論之前，要先知道以下關於整數的性質：

== 整數集合 ==
整數集合，即所有的整數，像0,1,-1,2,-2,......這一些整數形成的集合，就叫'''整數集合'''，或以<math>\mathbb{Z}</math>表示，[[自然數]]<math>\mathbb{N}</math>為其子集，但奇怪的是，整數集合和正整數集合內部的元素數量竟相等


整數集合的性質符合環的性質，意即其加減乘法皆自封(若對一種定義在X上的運算Y，當a和b皆為X的元素時，aYb亦為X的元素，則稱運算Y自封)，以下將說明整數集合的性質

== 數學歸納法 ==

若有一個命題<math>P(n)</math>，若能證明<math>P(n)</math>對<math>n=1</math>或其他給定的起始正整數<math>k</math>成立，且在假設對一個正整數<math>n=m>1</math>（或前面給定的正整數<math>k</math>），命題<math>P(n)</math>成立時，亦能證明<math>n=m+1</math>時命題<math>P(n)</math>成立，則命題<math>P(n)</math>對所有<math>n\in N</math>或<math>n\in N-\left \{ 1,2,3,...,k-1 \right \}</math>皆成立，除了本法以外，尚有第二種數學歸納法，第二種數學歸納法將在稍後說明

== 加法篇 ==
加法使用符號+，<math>a</math>加<math>b</math>，或稱<math>a</math>和<math>b</math>相加可記為<math>a+b</math>

整數集合的加法（和減法）是封閉的（若<math>S</math>裡面的元素透過一個定義在<math>S</math>上的運算，所得的結果的元素依然存在於<math>S</math>，且對所有<math>S</math>的元素都是如此，那麼這個二元運算就是在<math>S</math>上封閉的），以下為加法（和減法）的性質：

*加法有結合律，即對於任意整數<math>a</math>,<math>b</math>,<math>c</math>有<math>\left ( a+b \right )+c=a+\left ( b+c \right )</math>

*加法有交換律，即對於任意整數<math>a</math>,<math>b</math>有<math>a+b=b+a</math>

*加法有相消律，即對於任意整數<math>a</math>,<math>b</math>,<math>c</math>，若<math>a+c=b+c</math>，則可推出<math>a=b</math>

*減法，若對整數<math>a</math>,<math>b</math>,c有<math>a=b+c</math>，則亦可記做<math>a-b=c</math>，但是減法無交換律

*在整數中有一個元素0，使得對任意整數<math>a</math>有<math>a+0=a</math>且<math>a-0=a</math>

== 乘法篇 ==



乘法使用符號‧，<math>a</math>乘<math>b</math>，或稱<math>a</math>和<math>b</math>相乘可記為<math>a\cdot b</math>，但是若<math>a</math>或<math>b</math>至少有一個為未知數<math>x</math>，則乘號‧可省略（但若<math>a</math>和<math>b</math>皆為已知數，且皆以數字（非英文字母）表示，則乘號「‧」'''不可省略'''）

整數集合的乘法也是封閉的，以下為它的性質：

*乘法有結合律，即對於任意整數<math>a</math>,<math>b</math>,<math>c</math>有<math>a\left ( bc \right )=\left ( ab \right )c</math>

*乘法有交換律，即對於任意整數<math>a</math>,<math>b</math>有<math>ab=ba</math>

*乘法有相消律，即對於任意整數<math>a</math>,<math>b</math>,<math>c</math>，若<math>ab=ac</math>，則可推出<math>b=c</math> (a不能為零)

*在整數中有一元素1，使得對任意整數<math>a</math>有<math>a\times 1=1\times a=a</math>

*任意整數<math>a</math>和0相乘為0

== 大小關係 ==
整數集合是一個有序集合，以下為整數中的序的關係(即一般所說的大小關係)

*若<math>a>b</math>，則必有正整數<math>c</math>，使<math>b+c=a</math>

*若<math>a<b</math>，且<math>b<c</math>，則<math>a<c</math>

*若<math>a<b</math>，且<math>a</math>,<math>b</math>為正整數，則必有正整數<math>n</math>，使得<math>na>b</math>

*若<math>a>b</math>且<math>c>d</math>，則<math>a+c>b+d</math>

*對於任意整數<math>a</math>，有<math>a = a</math>

*對於兩個整數<math> a , b \in \mathbb{Z} </math>，<math>a < b</math>、<math>a > b</math>和<math>a = b</math>有且僅有一個成立

== 最大自然數原理與最小自然數原理 ==
*最小自然數原理：對於任意自然數的非空子集<math>X</math>，存在一元素<math>n</math>，使得任意的<math>x \in  X</math>，都有<math>n \le x</math>

事實上，對於任意有下界的非空集合<math>S</math>，若<math>S</math>為整數集合Z的一個子集，則在<math>S</math>中必存在一最小的數n，使得任意的<math>x \in  Z</math>，都有<math>n \le x</math>

*最大自然數原理：對於任意有上界的非空子集<math>Y</math>，存在一元素<math>m</math>，使得任意的<math>y \in  Y</math>，都有<math>m \ge y</math>


== 除法篇 ==


除法使用符號<math>\div</math>，若<math>a</math>除以<math>b</math>，或<math>b</math>除<math>a</math>，記做<math>a\div b</math>

*若<math>a</math>可被<math>b</math>整除，則記做<math>b|a</math>，或<math>a=bk</math>

*若不能整除，即會剩餘某數<math>c<a</math>，則記做<math>a=bm+c</math>

*若<math>b</math>不能整除<math>a</math>，但是能找得到一數，使<math>b|a-c</math>，則此<math>a</math>,<math>b</math>,<math>c</math>可記做<math> a\equiv c </math>(<math> \bmod b </math>)，後者亦可稱<math>a</math>除以<math>b</math>同餘於<math> c </math>

== 其他的一些名詞的定義 ==
*因數：若<math>b|a</math>成立，則<math>b</math>是<math>a</math>的因數

*倍數：若<math>b|a</math>，則<math>a</math>是<math>b</math>的倍數

*質數：若一個大於1的正數<math> p </math>的正因數只有1,<math> p </math>，則稱這個數<math> p </math>為質數

== 第二種數學歸納法 ==
雖然比起前面所說的數學歸納法，第二種數學歸納法比較少用，但是第二種數學歸納法仍然為重要的證明方法，茲將之說明如下：
若對一個命題<math> P(n) </math>，在<math> n=1 </math>(或指定的正整數<math> k </math>)時成立，在假設對所有符合<math> n<m </math>的正整數都成立時，能證明<math> P(n) </math>對<math> m </math>亦成立，則<math> P(n) </math>對所有正整數（或正整數集合<math> N-\left \{ 1,2,3,...,k-1 \right \} </math>）都成立

第二種數學歸納法可以用最小自然數原理和反證法證明其為真

== 算術基本定理 ==
<!--
任意大於1的正整數皆可表為不論質數排列方法的'''質數'''的'''乘積'''，且這個表示法是'''唯一'''的，在此不計這些質數的排列順序，意即寫成abc、acb、bac、bca、cab或cba等在排列上的差別不考慮，在此只考慮組合，如果考慮排列上的差別，則15=3‧5=5‧3，那麼算術基本定理就不成立了，意即：

若正整數a>1，則<math>a = p_1p_2p_3......p_k</math>，其中<math>p_1,p_2,p_3,......,p_k</math>皆為質數，且這是這些質數在全部選取，不論排列的「位置」的狀況下能組成一個數的唯一方法
-->

任意大於1的'''正整數'''都能唯一地表示成由指定數量的特定質數的乘積

=== 標準分解式 ===
根據算術基本定理，任意正整數皆可表為唯一的若干个正质数的乘積，且因為這些質數沒有次序上的問題，因此，可將相同的質數寫成該質數的冪方也是沒問題的，意即上面的a可改寫為：
a=<math>p_1^{q_1}p_2^{q_2}p_3^{q_3}......p_n^{q_n}</math>

=== 算術基本定理的證明 ===
先證明幾個引理：

*引理1：每個大於一的數都可以表示成質數的乘積，或本身為質數

引理1證明：用第二種數學歸納來證明，設正整數<math> n=2 </math>時，2為質數，故成立，再假設當<math>2 \le n < m</math>時此引理成立，則當<math> n=m </math>時，若<math> m </math>為質數，則引理成立，若<math> m </math>不為質數時，<math> m </math>為合數，因此<math> m=pq </math>，其中<math>2 \le p , q < m</math>，因而由假設知<math> p </math>和<math> q </math>可表為質數的乘積，因而<math> m </math>亦可表為質數的乘積，因此引理亦對<math> n=m </math>成立，因此由數學歸納法得知，此引理對所有的正整數<math>n \ge 2</math>成立

*引理2：若<math> p|ab </math>，且<math>p</math>是質數，則p|a或p|b至少有一個成立，另一方面，若<math>p</math>是質數，且若<math>p|a_1 a_2 a_3 ...... a_n</math>成立，則<math>p|a_1</math>、<math>p|a_2</math>、<math>p|a_3</math>、......<math>p|a_n</math>至少有一成立

引理2證明：

*由引理2引出的引理3：若<math>p,q_1,q_2,......,q_k</math>皆為質數，且<math>p|q_1  q_2 ...... q_k</math>則至少有一個<math>q_j , 1 \le j \le k</math>使<math>p|q_j</math>

引理3證明：

算術基本定理證明：存在性由引理1可得知，現在來證唯一性：設有一數n，它的分解式為<math>n = p_1p_2p_3......p_s</math>，其中<math>p_1,p_2,p_3,......,p_s</math>皆為質數，再設n存在另一個分解式<math>n = q_1q_2q_3......q_r</math>，設<math>r > s</math>，且<math>q_1,q_2,q_3,......,q_r</math>亦皆為質數，而且<math>p_1 \le p_2 \le p_3 \le ...... \le p_s</math>及<math>q_1 \le q_2 \le q_3 \le ...... \le q_s</math>，則很明顯地有<math>n = p_1p_2p_3......p_s = q_1q_2q_3......q_r</math>，由引理3知，必有一些<math>p_i</math>和<math>q_j</math>相等，且可推知這個關係是唯一的，因此現在將和<math>p_1</math>相等的數設為<math>{q_1}'</math>，其他的也照做，意即<math>p_1 = {q_1}</math>、<math>p_2 = {q_2}'</math>、‧‧‧、<math>p_s = {q_s}'</math>，而剩下來的則記為<math>{q_{s+1}}' , {q_{s+2}}' , {q_{s+3}}' , ...... , {q_r}'</math>，則由此及<math>n = p_1p_2p_3......p_s = {q_1}' {q_2}' {q_3}' ...... {q_r}'</math>可推出<math>1 = {q_{s+1}}' {q_{s+2}}' {q_{s+3}}' ...... {q_r}'</math>意即此兩個分解式之中所有的質數相等，與原假設矛盾，故n的分解式為唯一的

== 最大公因數與最小公倍數 ==


=== 最大公因數 ===

假若對兩個整數<math>a,b</math>，有一整數<math>n</math>，使<math>n|a</math>且<math>n|b</math>，則稱<math>n</math>為<math>a</math>和<math>b</math>的'''公因數'''，若在<math>a</math>和<math>b</math>的公因數所形成的集合中，<math>n</math>是為其中最大的數字，則稱這個<math>n</math>為<math>a</math>和<math>b</math>的'''最大公因數'''，或記做<math>(a,b)=n</math>，若<math>(a,b)=1</math>，則稱<math>a</math>和<math>b</math>互質

=== 最小公倍數 ===

若有整數<math>m,a,b</math>，使得<math>a|m</math>且<math>b|m</math>，則稱<math>m</math>為<math>a</math>和<math>b</math>的'''公倍數'''，若在<math>a</math>和<math>b</math>所有的正公倍數所形成的集合中，<math>m</math>是其中最小的數字，則稱<math>m</math>為<math>a</math>和<math>b</math>的'''最小公倍數'''，或記做<math>[a,b]=m</math>，且若<math>(a,b)=1</math>，則<math>[a,b]=ab</math>


=== 最大公因數和最小公倍數的性質 ===
*最大公因數：
**<math>(a,b)=(|a|,b)=(a,|b|)=(|a|,|b|)</math>
**若<math>(a,b)=c</math>則<math>(a,b+ka)=c</math>，且在此<math>a,b,k</math>為任意整數，<math>c</math>為任意正整數
**若<math>(a,b)=c</math>則<math>(a,b,ka)=c</math>，且在此<math>a,b,k</math>為任意整數，<math>c</math>為任意正整數

=== 輾轉相除法 ===
對於兩個數<math>a</math>和<math>b_1</math>，有以下算法：

我们可以<math>d</math>表示<math>a, b</math>的公约数则<math>d|a</math>并且<math>d|b_1</math><br>
所以<math>a=k_1*d</math>并且<math>b_1=k_2*d</math>  <math>a-b=(k1-k2)*d</math>，<br>
也就是说当<math>a <> b_1</math>时，<math>a</math>和<math>b_1</math>的最大公约数和<math>a - b_1</math>和<math>b_1</math>相等。于是我们有：

<math>a = q_1b_1+b_2</math>

<math>b_1=q_2b_2+b_3</math>

......

<math>b_n=q_{n+1}b_{n+1}</math>

其中(<math>a</math>,<math>b_1</math>)=(<math>b_1</math>,<math>b_2</math>)=......=(<math>b_n</math>,<math>b_{n+1}</math>)

== 習題 ==
{{Expand|time=2018-02-11T04:38:07+00:00}}
=== 第一部份─基礎題 ===

=== 第二部份─進階題 ===

{{Stub}}

[[Category:初等数论]]