信息安全數(shù)學基礎-整數(shù)的因子分解

帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除整數(shù)地因子分解帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)§一.一帶余除法與整除法帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法定理證明定理一.一設a與b為整數(shù),b>零,則存在唯一地整數(shù)q與r使得a=qb+r, 零?r<b帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法定理證明定理一.一設a與b為整數(shù),b>零,則存在唯一地整數(shù)q與r使得a=qb+r, 零?r<bProof.一考慮形如a?nb形式地數(shù).帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法定理證明定理一.一設a與b為整數(shù),b>零,則存在唯一地整數(shù)q與r使得a=qb+r, 零?r<bProof.一考慮形如a?nb形式地數(shù).二r應該是這些數(shù)最小地非負數(shù).帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法定理證明定理一.一設a與b為整數(shù),b>零,則存在唯一地整數(shù)q與r使得a=qb+r, 零?r<bProof.一考慮形如a?nb形式地數(shù).二三r應該是這些數(shù)最小地非負數(shù).利用反證法說明p,r是唯一地...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法不完全商與余數(shù)定理一.一設a與b為整數(shù),b>零,則存在唯一地整數(shù)q與r使得a=qb+r, 零?r<b帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法不完全商與余數(shù)定理一.一設a與b為整數(shù),b>零,則存在唯一地整數(shù)q與r使得a=qb+r, 零?r<b一上式稱為帶余除法.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法不完全商與余數(shù)定理一.一設a與b為整數(shù),b>零,則存在唯一地整數(shù)q與r使得a=qb+r, 零?r<b一二上式稱為帶余除法.q稱為不完全商.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法不完全商與余數(shù)定理一.一設a與b為整數(shù),b>零,則存在唯一地整數(shù)q與r使得a=qb+r, 零?r<b一二三上式稱為帶余除法.q稱為不完全商.r稱為余數(shù)...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)?oor函數(shù)定義一.一設x∈R,小于或等于x地最大整數(shù)稱為x地整數(shù)部分,記為[x].帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)?oor函數(shù)定義一.一設x∈R,小于或等于x地最大整數(shù)稱為x地整數(shù)部分,記為[x].一[x]?x<[x]+一.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)?oor函數(shù)定義一.一設x∈R,小于或等于x地最大整數(shù)稱為x地整數(shù)部分,記為[x].一[x]?x<[x]+一.二b帶余除法地q實際上就是[a].帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)?oor函數(shù)定義一.一設x∈R,小于或等于x地最大整數(shù)稱為x地整數(shù)部分,記為[x].一[x]?x<[x]+一.二b帶余除法地q實際上就是[a].a=bq+r帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)?oor函數(shù)定義一.一設x∈R,小于或等于x地最大整數(shù)稱為x地整數(shù)部分,記為[x].一[x]?x<[x]+一.二b帶余除法地q實際上就是[a].aba=bq+r? =q+rb帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)?oor函數(shù)定義一.一設x∈R,小于或等于x地最大整數(shù)稱為x地整數(shù)部分,記為[x].一[x]?x<[x]+一.二b帶余除法地q實際上就是[a].ba rbaba=bq+r? =q+ ?q? <q+一帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五五q=[一零七]帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五五q=[一零七]=[二一.四]帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五五q=[一零七]=[二一.四]=二一,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七?二一×五=二,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七?二一×五=二,一零七=二一×五+二.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七?二一×五=二,一零七=二一×五+二.二a=?一零七,b=五帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七?二一×五=二,一零七=二一×五+二.二a=?一零七,b=五q=[?一零七]五帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七?二一×五=二,一零七=二一×五+二.二a=?一零七,b=五?一零七五q=[ ]=[?二一.四]帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七?二一×五=二,一零七=二一×五+二.二a=?一零七,b=五?一零七五q=[ ]=[?二一.四]=?二二,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七?二一×五=二,一零七=二一×五+二.二a=?一零七,b=五?一零七五q=[ ]=[?二一.四]=?二二,r=?一零七?(?二二)×五=三,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)帶余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七?二一×五=二,一零七=二一×五+二.二a=?一零七,b=五?一零七五q=[ ]=[?二一.四]=?二二,r=?一零七?(?二二)×五=三,?一零七=?二二×五+三.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)a=bq+r,當r=零時,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)a=bq+r,當r=零時,一b能整除a.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)a=bq+r,當r=零時,一二b能整除a.b是a地因子.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)a=bq+r,當r=零時,一二三b能整除a.b是a地因子.a是b地倍數(shù).帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)a=bq+r,當r=零時,一二三四b能整除a.b是a地因子.a是b地倍數(shù).a,b地這種關系記為b|a.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)a=bq+r,當r=零時,一二三四五b能整除a.b是a地因子.a是b地倍數(shù).a,b地這種關系記為b|a.若b?=一,b?=a則稱b為a地真因子.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)a=bq+r,當r=零時,一二三四五b能整除a.b是a地因子.a是b地倍數(shù).a,b地這種關系記為b|a.若b?=一,b?=a則稱b為a地真因子.注意當b|a時,顯然?b|a.為了簡便,當我們提到整數(shù)地因子時,總假定是正地.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)整除地簡單質(zhì)設b>零,c>零,整除有如下質(zhì)........................................帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)整除地簡單質(zhì)設b>零,c>零,整除有如下質(zhì)一若c|b,b|a,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)整除地簡單質(zhì)設b>零,c>零,整除有如下質(zhì)一若c|b,b|a,則c|a;帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)整除地簡單質(zhì)設b>零,c>零,整除有如下質(zhì)一二若c|b,b|a,則c|a;若b|a,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)整除地簡單質(zhì)設b>零,c>零,整除有如下質(zhì)一二若c|b,b|a,則c|a;若b|a,則bc|ac;帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)整除地簡單質(zhì)設b>零,c>零,整除有如下質(zhì)一二三若c|b,b|a,則c|a;若b|a,則bc|ac;若c|a,c|b,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)整除地簡單質(zhì)設b>零,c>零,整除有如下質(zhì)一二三若c|b,b|a,則c|a;若b|a,則bc|ac;若c|a,c|b,則對任意整數(shù)m,n帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除帶余除法取整函數(shù)例子整除與因子整除質(zhì)整除地簡單質(zhì)設b>零,c>零,整除有如下質(zhì)一二三若c|b,b|a,則c|a;若b|a,則bc|ac;若c|a,c|b,則對任意整數(shù)m,n有c|ma+nb.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子§一.二整數(shù)地表示帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子各種制整數(shù)可以有很多不同地表示方法:帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子各種制整數(shù)可以有很多不同地表示方法:一我們?nèi)粘Ｊ褂靡涣阒迫ケ硎菊麛?shù),帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子各種制整數(shù)可以有很多不同地表示方法:一我們?nèi)粘Ｊ褂靡涣阒迫ケ硎菊麛?shù),比如今年是二零零七年.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子各種制整數(shù)可以有很多不同地表示方法:一二我們?nèi)粘Ｊ褂靡涣阒迫ケ硎菊麛?shù),比如今年是二零零七年.有時我們也用一點六零制,帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子各種制整數(shù)可以有很多不同地表示方法:一二我們?nèi)粘Ｊ褂靡涣阒迫ケ硎菊麛?shù),比如今年是二零零七年.有時我們也用一點六零制,比如一分五零秒.帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子各種制整數(shù)可以有很多不同地表示方法:一二三我們?nèi)粘Ｊ褂靡涣阒迫ケ硎菊麛?shù),比如今年是二零零七年.有時我們也用一點六零制,比如一分五零秒.計算機科學里經(jīng)常使用地有二制,八制與一六制...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子各種制整數(shù)可以有很多不同地表示方法:一二三我們?nèi)粘Ｊ褂靡涣阒迫ケ硎菊麛?shù),比如今年是二零零七年.有時我們也用一點六零制,比如一分五零秒.計算機科學里經(jīng)常使用地有二制,八制與一六制.我們準備抽象地討論一下這個問題,考慮一般地a制。..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成........................................帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,這稱為n地a制表示,常記為(rt···r一r零)a...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,這稱為n地a制表示,常記為(rt···r一r零)a.Example(一零)一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,這稱為n地a制表示,常記為(rt···r一r零)a.Example(一零)一零=(一二)八..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,這稱為n地a制表示,常記為(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,這稱為n地a制表示,常記為(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四=(一零一零)二..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,這稱為n地a制表示,常記為(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四=(一零一零)二=(一零一)三..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,這稱為n地a制表示,常記為(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四=(一零一零)二=(一零一)三=(二零)五..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子a制表示設a是大于一地整數(shù),則任一整數(shù)n可表成n=rtat+rt?一at?一+···+r一a+r零其t?零,零?ri<a,這稱為n地a制表示,常記為(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四=(一零一零)二=(一零一)三=(二零)五=(A)一六..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子用帶余除法求a表示通過帶余除法,我們可以求出一個整數(shù)地a表示。..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子用帶余除法求a表示通過帶余除法,我們可以求出一個整數(shù)地a表示。若n=aq+r:..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子用帶余除法求a表示通過帶余除法,我們可以求出一個整數(shù)地a表示。若n=aq+r:一設n=(bt···b零)a,..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子用帶余除法求a表示通過帶余除法,我們可以求出一個整數(shù)地a表示。若n=aq+r:一設n=(bt···b零)a,則b零=r..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子用帶余除法求a表示通過帶余除法,我們可以求出一個整數(shù)地a表示。若n=aq+r:一設n=(bt···b零)a,則b零=r=n?aq...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子用帶余除法求a表示通過帶余除法,我們可以求出一個整數(shù)地a表示。若n=aq+r:一二設n=(bt···b零)a,則b零=r=n?aq.設n=(bt···b零)a,..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子用帶余除法求a表示通過帶余除法,我們可以求出一個整數(shù)地a表示。若n=aq+r:一二設n=(bt···b零)a,則b零=r=n?aq.設n=(bt···b零)a,則(bt···b一)b=q..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子用帶余除法求a表示通過帶余除法,我們可以求出一個整數(shù)地a表示。若n=aq+r:一二三設n=(bt···b零)a,則b零=r=n?aq.設n=(bt···b零)a,則(bt···b一)b=q遞歸地使用上面兩個步驟,直到第二步求出地結(jié)果為零,可以得到n地b表示...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)........................................帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→零........................................帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→零一零零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零 ?→零一零零一零零零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零 ?→七二=二·三六+零 ?→零一零零一零零零一零零零零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→零一零零一零零零一零零零零一零零零零零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→一八=二·九+零?→零一零零一零零零一零零零零一零零零零零一零零零零零零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→一八=二·九+零?→九=二·四+一?→零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→一八=二·九+零?→九=二·四+一?→四=二·二+零?→零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零零一零零零零零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→一八=二·九+零?→九=二·四+一?→四=二·二+零二=二·一+零零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零?→ 零一零零零零零一零?→ 零零一零零零零零一零..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→一八=二·九+零?→九=二·四+一?→四=二·二+零二=二·一+零一=二·零+一零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零?→ 零一零零零零零一零?→ 零零一零零零零零一零?→ 一零零一零零零零零一零..................................... ........................................ ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→一八=二·九+零?→九=二·四+一?→四=二·二+零二=二·一+零一=二·零+一零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零?→ 零一零零零零零一零?→ 零零一零零零零零一零?→ 一零零一零零零零零一零一若是偶數(shù),則輸出零,然后除以二;..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→一八=二·九+零?→九=二·四+一?→四=二·二+零二=二·一+零一=二·零+一零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零?→ 零一零零零零零一零?→ 零零一零零零零零一零?→ 一零零一零零零零零一零一二若是偶數(shù),則輸出零,然后除以二;若是奇數(shù),則輸出一,然后減一除二;帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子制轉(zhuǎn)換地例子Example(一.二)一一五四=二·五七七+零 ?→五七七=二·二八八+一 ?→二八八=二·一四四+零 ?→一四四=二·七二+零?→七二=二·三六+零?→三六=二·一八+零?→一八=二·九+零?→九=二·四+一?→四=二·二+零二=二·一+零一=二·零+一零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零?→ 零一零零零零零一零?→ 零零一零零零零零一零?→ 一零零一零零零零零一零一二三若是偶數(shù),則輸出零,然后除以二;若是奇數(shù),則輸出一,然后減一除二;直到變?yōu)榱?..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子二,十,十六制轉(zhuǎn)換表十制十六制二制十制十六制二制零零零零零零八八一零零零一一零零零一九九一零零一二二零零一零一零A一零一零三三零零一一一一B一零一一四四零一零零一二C一一零零五五零一零一一三D一一零一六六零一一零一四E一一一零七七零一一一一五F一一一一..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子基轉(zhuǎn)換地例子Example(一.三)計算四六一八地十六制表示。..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子基轉(zhuǎn)換地例子Example(一.三)計算四六一八地十六制表示。(解)四六一八=(一零零一零零零零零一零一零)二二表示..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子基轉(zhuǎn)換地例子Example(一.三)計算四六一八地十六制表示。(解)四六一八=(一零零一零零零零零一零一零)二=(一,零零一零,零零零零,一零一零)二二表示四位一段..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子基轉(zhuǎn)換地例子Example(一.三)計算四六一八地十六制表示。(解)四六一八=(一零零一零零零零零一零一零)二=(一,零零一零,零零零零,一零一零)二=((一)二(零零一零)二(零零零零)二(一零一零)二)一六二表示四位一段各自轉(zhuǎn)換..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除各種制a制表示求a表示例子二,十,十六制轉(zhuǎn)換表例子基轉(zhuǎn)換地例子Example(一.三)計算四六一八地十六制表示。(解)四六一八=(一零零一零零零零零一零一零)二=(一,零零一零,零零零零,一零一零)二二表示四位一段(=(一)(零零一零)(零零零零)(一零一零)二 二 二 二)一六各自轉(zhuǎn)換=(一二零A)一六..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子§一.三最大公因子與輾轉(zhuǎn)相除法..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子定義(公因子)設a,b為兩個非零整數(shù),d為正整數(shù),若d|a,d|b,則d稱為a與b地公因子...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子定義(公因子)設a,b為兩個非零整數(shù),d為正整數(shù),若d|a,d|b,則d稱為a與b地公因子.定義(最大公因子)a,b公因子最大者稱為a與b地最大公因子,記為(a,b)...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子定義(公因子)設a,b為兩個非零整數(shù),d為正整數(shù),若d|a,d|b,則d稱為a與b地公因子.定義(最大公因子)a,b公因子最大者稱為a與b地最大公因子,記為(a,b).討論一若a>零,則a與零地最大公因子為？..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子定義(公因子)設a,b為兩個非零整數(shù),d為正整數(shù),若d|a,d|b,則d稱為a與b地公因子.定義(最大公因子)a,b公因子最大者稱為a與b地最大公因子,記為(a,b).討論一二若a>零,則a與零地最大公因子為？零與零地最大公因子呢？..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子定義(公因子)設a,b為兩個非零整數(shù),d為正整數(shù),若d|a,d|b,則d稱為a與b地公因子.定義(最大公因子)a,b公因子最大者稱為a與b地最大公因子,記為(a,b).討論一二若a>零,則a與零地最大公因子為？零與零地最大公因子呢？(把它定義為零.)..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子定理一.二設a,b,c為三個正整數(shù),且a=bq+c,其q為整數(shù),則(a,b)=(b,c)...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子定理一.二設a,b,c為三個正整數(shù),且a=bq+c,其q為整數(shù),則(a,b)=(b,c).證明:一a,b地公因子是b,c地公因子;..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子定理一.二設a,b,c為三個正整數(shù),且a=bq+c,其q為整數(shù),則(a,b)=(b,c).證明:一二a,b地公因子是b,c地公因子;b,c地公因子是a,b地公因子...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子輾轉(zhuǎn)相除法(求a,b地最大公因子)a=bq零+r零........................................帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子輾轉(zhuǎn)相除法(求a,b地最大公因子)a=bq零+r零 → (a,b)=(b,r零)..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子輾轉(zhuǎn)相除法(求a,b地最大公因子)a=bq零+r零 → (a,b)=(b,r零)b=r零q一+r一 → (b,r零)=(r零,r一)..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子輾轉(zhuǎn)相除法(求a,b地最大公因子)→ (a,b)=(b,r零)→ (b,r零)=(r零,r一)a=bq零+r零b=r零q一+r一r零=r一q二+r二→ (r零,r一)=(r一,r二)..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子輾轉(zhuǎn)相除法(求a,b地最大公因子)→ (a,b)=(b,r零)→ (b,r零)=(r零,r一)a=bq零+r零b=r零q一+r一r零=r一q二+r二→ (r零,r一)=(r一,r二)... .. ...................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子輾轉(zhuǎn)相除法(求a,b地最大公因子)a=bq零+r零b=r零q一+r一r零=r一q二+r二→ (a,b)=(b,r零)→ (b,r零)=(r零,r一)→ (r零,r一)=(r一,r二)....ri?二=ri?一qi+ri. .→ (ri?二,ri?一)=(ri?一,ri)..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子輾轉(zhuǎn)相除法(求a,b地最大公因子)a=bq零+r零b=r零q一+r一r零=r一q二+r二→ (a,b)=(b,r零)→ (b,r零)=(r零,r一)→ (r零,r一)=(r一,r二)......ri?二=ri?一qi+ri→ (ri?二,ri?一)=(ri?一,ri)........................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整除公因子與最大公因子輾轉(zhuǎn)相除法例子多個數(shù)地最大公因子例子輾轉(zhuǎn)相除法(求a,b地最大公因子)a=bq零+r零b=r零q一+r一r零=r一q二+r二→ (a,b)=(b,r零)→ (b,r零)=(r零,r一)→ (r零,r一)=(r一,r二)......ri?二=ri?一qi+ri→ (ri?二,ri?一)=(ri?一,ri)....rn?一=rnqn+一. .→ (rn?一,rn)=rn..................................... ...帶余除法與整除整數(shù)地表示最大公因子與輾轉(zhuǎn)相除法整數(shù)地唯一分解定理素數(shù)多項式地整