近世代數(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)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市不铆，隨后出現(xiàn)的幾起案子讽营，更是在濱河造成了極大的恐慌憔恳，老刑警劉巖齿尽，帶你破解...
沈念sama閱讀 218,755評(píng)論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件哨苛，死亡現(xiàn)場(chǎng)離奇詭異均蜜，居然都是意外死亡但绕，警方通過查閱死者的電腦和手機(jī)却特，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,305評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門扶供，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人裂明，你說我怎么就攤上這事椿浓。” “怎么了闽晦？”我有些...
開封第一講書人閱讀 165,138評(píng)論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵扳碍，是天一觀的道長(zhǎng)。經(jīng)常有香客問我仙蛉，道長(zhǎng)笋敞，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,791評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任荠瘪，我火速辦了婚禮夯巷，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘哀墓。我一直安慰自己趁餐，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,794評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布篮绰。她就那樣靜靜地躺著后雷，像睡著了一般。火紅的嫁衣襯著肌膚如雪阶牍。梳的紋絲不亂的頭發(fā)上喷面，一...
開封第一講書人閱讀 51,631評(píng)論 1贊 305
城市分裂傳說
那天，我揣著相機(jī)與錄音走孽，去河邊找鬼惧辈。笑死，一個(gè)胖子當(dāng)著我的面吹牛磕瓷，可吹牛的內(nèi)容都是我干的盒齿。我是一名探鬼主播念逞，決...
沈念sama閱讀 40,362評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼边翁！你這毒婦竟也來了翎承？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,264評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤符匾，失蹤者是張志新（化名）和其女友劉穎叨咖，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體啊胶，經(jīng)...
沈念sama閱讀 45,724評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡甸各，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,900評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了焰坪。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片趣倾。...
茶點(diǎn)故事閱讀 40,040評(píng)論 1贊 350
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖某饰，靈堂內(nèi)的尸體忽然破棺而出儒恋，到底是詐尸還是另有隱情，我是刑警寧澤黔漂，帶...
沈念sama閱讀 35,742評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布诫尽，位于F島的核電站，受9級(jí)特大地震影響瘟仿，放射性物質(zhì)發(fā)生泄漏箱锐。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,364評(píng)論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一劳较、第九天我趴在偏房一處隱蔽的房頂上張望驹止。院中可真熱鬧，春花似錦观蜗、人聲如沸臊恋。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,944評(píng)論 0贊 22
一樁弒父案墓捻，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽抖仅。三九已至，卻和暖如春砖第，著一層夾襖步出監(jiān)牢的瞬間撤卢，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,060評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來泰國(guó)打工梧兼，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留放吩，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,247評(píng)論 3贊 371
代替公主和親
正文我出身青樓羽杰，卻偏偏與公主長(zhǎng)得像渡紫，于是被迫代替她去往敵國(guó)和親到推。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,979評(píng)論 2贊 355