近世代數(shù)理論基礎(chǔ)4：整除·歐式除法

整除·歐式除法

整除

定義：設(shè)a,b\in Z,若\exists q\in Z使a=bq,則稱b整除a,或a可被b整除,記作b|a,此時(shí)b為a的因數(shù),a為b的倍數(shù),若上述q不存在,則稱b不能整除a,或a不能被b整除,記作b\nmid a

整除的性質(zhì)

定理：

1.b|a,c|b\Rightarrow c|a

2.m|a,m|b\Rightarrow m|(a\pm b)

3.m|a_1,m|a_2,\cdots,m|a_n\Rightarrow \forall q_1,q_2,\cdots,q_n\in Z,有m|(q_1a_1+q_2a_2+\cdots+q_na_n)

證明：

\because m|a_i

\therefore \exists r_i\in Z使a_i=r_im,i=1,2,\cdots,n

\therefore q_1a_1+q_2a_2+\cdots+q_na_n=(q_1r_1+q_2r_2+\cdots+q_nr_n)m

又q_1r_1+q_2r_2+\cdots+q_nr_n\in Z

\therefore m|(q_1a_1+q_2a_2+\cdots+q_na_n)\qquad\mathcal{Q.E.D}

帶余除法

定理：若a,b\in Z,b\gt 0,則\exists ! q,r\in Z使a=bq+r,0\le r\lt b

(注：q稱為b除a所得的不完全商,r稱為b除a所得的余數(shù))

證明：

考慮整數(shù)序列\(zhòng)cdots,-3b,-2b,-b,0,b,2b,3b,\cdots

則a必在上述序列的某相鄰兩項(xiàng)之間

即\exists q\in Z使qb\le a\lt (q+1)b

令r=a-qb,則a=qb+r,0\le r\lt b且r\in Z

設(shè)q_1,r_1\in Z也滿足a=q_1b+r_1,0\le r_1\lt b

則q_1b+r_1=a=qb+r

\therefore b(q-q_1)=r_1-r

\therefore b|q-q_1|=|r_1-r|\lt b

\therefore q_1=q

\therefore r_1=r\qquad\mathcal{Q.E.D}

公因數(shù)

定義：設(shè)a,b\in Z,若d|a且d|b,則稱d為a與b的一個(gè)公因數(shù),a與b的公因數(shù)中最大者稱為a與b的最大公因數(shù),并記為gcd(a,b)或(a,b),若(a,b)=1則稱a與b互素

例：

\forall a\in Z,有(a,1)=1

若a\neq 0,則(0,a)=|a|

定理

定理：設(shè)a,b,c\in Z,且不全為零, 若a=bq+c,其中q\in Z,則(a,b)=(b,c)

證明：

設(shè)d為a與b的任一公因數(shù)

則d|a,d|b

\therefore d|(a-bq)

即d|c

\therefore d也為b與c的公因數(shù)

同理可知b與c的任一公因數(shù)也為a與b的公因數(shù)

即a,b與b,c有完全相同的公因數(shù)

\therefore 他們有相同的最大公因數(shù)

即(a,b)=(b,c)

歐氏除法(輾轉(zhuǎn)相除法)

計(jì)算任意兩個(gè)整數(shù)a與b的最大公因數(shù)的方法：

設(shè)a,b\in N,由帶余除法,有

a=bq_1+r_1,0\lt r_1\lt b

b=r_1q_2+r_2,0\lt r_2\lt r_1

r_1=r_2q_3+r_3,0\lt r_3\lt r_2

\cdots

r_{n-2}=r_{n-1}q_n+r_n,0\lt r_n\lt r_{n-1}

r_{n-1}=r_nq_{n+1}+r_{n+1},r_{n+1}=0

\because b\gt r_1\gt r_2\gt \cdots\gt r_n\gt r_{n+1}\gt \cdots

\therefore \exists n使r_{n+1}=0

\therefore r_{n}=(0,r_n)=(r_{n+1},r_n)=(r_n,r_{n-1})=\cdots=(r_1,b)=(a,b)

定理

定理：設(shè)a,b\in Z,且不全為零,則\exists s,t\in Z使as+bt=(a,b)

證明：

令r_{-1}=a,r_0=b,則

r_{-1}=1\cdot a+0\cdot b

r_0=0\cdot a+1\cdot b

r_1=1\cdot a+(-q_1)\cdot b

令r_i=P_i\cdot a+Q_i\cdot b

由r_{n-2}=r_{n-1}q_n+r_n可知

r_n=r_{n-2}-q_nr_{n-1}

=(P_{n-2}\cdot a+Q_{n-2}\cdot b)-q_n(P_{n-1}\cdot a+Q_{n-1}\cdot b)

=(P_{n-2}-q_nP_{n-1})\cdot a+(Q_{n-2}-q_nQ_{n-1})\cdot b

=P_n\cdot a+Q_n\cdot b

當(dāng)k\ge 1時(shí),有如下遞推關(guān)系

\begin{cases}P_k=P_{k-2}-q_kP_{k-1}\\ Q_k=Q_{k-2}-q_kQ_{k-1}\end{cases}

\begin{cases}P_{-1}=1\\Q_{-1}=0\end{cases}

\begin{cases}P_0=0\\Q_0=1\end{cases}\qquad\mathcal{Q.E.D}

定理

定理：設(shè)a_1,a_2,\cdots,a_n\in Z且不全為零,d為a_1,a_2,\cdots,a_n的最大公因數(shù)0

令d_2=(a_1,a_2),d_3=(d_2,a_3),d_4=(d_3,a_4),\cdots,d_n=(d_{n-1},a_n)

則d=d_n

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容