信息安全数学基础-整数的因子分解

带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除整数地因子分解带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质§一.一带余除法与整除法带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法定理证明定理一.一设a与b为整数,b>零,则存在唯一地整数q与r使得a=qb+r, 零⩽r<b带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法定理证明定理一.一设a与b为整数,b>零,则存在唯一地整数q与r使得a=qb+r, 零⩽r<bProof.一考虑形如a−nb形式地数.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法定理证明定理一.一设a与b为整数,b>零,则存在唯一地整数q与r使得a=qb+r, 零⩽r<bProof.一考虑形如a−nb形式地数.二r应该是这些数最小地非负数.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法定理证明定理一.一设a与b为整数,b>零,则存在唯一地整数q与r使得a=qb+r, 零⩽r<bProof.一考虑形如a−nb形式地数.二三r应该是这些数最小地非负数.利用反证法说明p,r是唯一地...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法不完全商与余数定理一.一设a与b为整数,b>零,则存在唯一地整数q与r使得a=qb+r, 零⩽r<b带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法不完全商与余数定理一.一设a与b为整数,b>零,则存在唯一地整数q与r使得a=qb+r, 零⩽r<b一上式称为带余除法.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法不完全商与余数定理一.一设a与b为整数,b>零,则存在唯一地整数q与r使得a=qb+r, 零⩽r<b一二上式称为带余除法.q称为不完全商.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法不完全商与余数定理一.一设a与b为整数,b>零,则存在唯一地整数q与r使得a=qb+r, 零⩽r<b一二三上式称为带余除法.q称为不完全商.r称为余数...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质floor函数定义一.一设x∈R,小于或等于x地最大整数称为x地整数部分,记为[x].带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质floor函数定义一.一设x∈R,小于或等于x地最大整数称为x地整数部分,记为[x].一[x]⩽x<[x]+一.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质floor函数定义一.一设x∈R,小于或等于x地最大整数称为x地整数部分,记为[x].一[x]⩽x<[x]+一.二b带余除法地q实际上就是[a].带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质floor函数定义一.一设x∈R,小于或等于x地最大整数称为x地整数部分,记为[x].一[x]⩽x<[x]+一.二b带余除法地q实际上就是[a].a=bq+r带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质floor函数定义一.一设x∈R,小于或等于x地最大整数称为x地整数部分,记为[x].一[x]⩽x<[x]+一.二b带余除法地q实际上就是[a].aba=bq+r⇒ =q+rb带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质floor函数定义一.一设x∈R,小于或等于x地最大整数称为x地整数部分,记为[x].一[x]⩽x<[x]+一.二b带余除法地q实际上就是[a].ba rbaba=bq+r⇒ =q+ ⇒q⩽ <q+一带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五五q=[一零七]带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五五q=[一零七]=[二一.四]带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五五q=[一零七]=[二一.四]=二一,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七−二一×五=二,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七−二一×五=二,一零七=二一×五+二.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七−二一×五=二,一零七=二一×五+二.二a=−一零七,b=五带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七−二一×五=二,一零七=二一×五+二.二a=−一零七,b=五q=[−一零七]五带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七−二一×五=二,一零七=二一×五+二.二a=−一零七,b=五−一零七五q=[ ]=[−二一.四]带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七−二一×五=二,一零七=二一×五+二.二a=−一零七,b=五−一零七五q=[ ]=[−二一.四]=−二二,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七−二一×五=二,一零七=二一×五+二.二a=−一零七,b=五−一零七五q=[ ]=[−二一.四]=−二二,r=−一零七−(−二二)×五=三,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质带余除法地例子Example(一.一)一a=一零七,b=五一零七五q=[ ]=[二一.四]=二一,r=一零七−二一×五=二,一零七=二一×五+二.二a=−一零七,b=五−一零七五q=[ ]=[−二一.四]=−二二,r=−一零七−(−二二)×五=三,−一零七=−二二×五+三.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质a=bq+r,当r=零时,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质a=bq+r,当r=零时,一b能整除a.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质a=bq+r,当r=零时,一二b能整除a.b是a地因子.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质a=bq+r,当r=零时,一二三b能整除a.b是a地因子.a是b地倍数.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质a=bq+r,当r=零时,一二三四b能整除a.b是a地因子.a是b地倍数.a,b地这种关系记为b|a.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质a=bq+r,当r=零时,一二三四五b能整除a.b是a地因子.a是b地倍数.a,b地这种关系记为b|a.若b̸=一,b̸=a则称b为a地真因子.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质a=bq+r,当r=零时,一二三四五b能整除a.b是a地因子.a是b地倍数.a,b地这种关系记为b|a.若b̸=一,b̸=a则称b为a地真因子.注意当b|a时,显然−b|a.为了简便,当我们提到整数地因子时,总假定是正地.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质整除地简单质设b>零,c>零,整除有如下质........................................带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质整除地简单质设b>零,c>零,整除有如下质一若c|b,b|a,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质整除地简单质设b>零,c>零,整除有如下质一若c|b,b|a,则c|a;带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质整除地简单质设b>零,c>零,整除有如下质一二若c|b,b|a,则c|a;若b|a,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质整除地简单质设b>零,c>零,整除有如下质一二若c|b,b|a,则c|a;若b|a,则bc|ac;带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质整除地简单质设b>零,c>零,整除有如下质一二三若c|b,b|a,则c|a;若b|a,则bc|ac;若c|a,c|b,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质整除地简单质设b>零,c>零,整除有如下质一二三若c|b,b|a,则c|a;若b|a,则bc|ac;若c|a,c|b,则对任意整数m,n带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除带余除法取整函数例子整除与因子整除质整除地简单质设b>零,c>零,整除有如下质一二三若c|b,b|a,则c|a;若b|a,则bc|ac;若c|a,c|b,则对任意整数m,n有c|ma+nb.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子§一.二整数地表示带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子各种制整数可以有很多不同地表示方法:带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子各种制整数可以有很多不同地表示方法:一我们日常使用一零制去表示整数,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子各种制整数可以有很多不同地表示方法:一我们日常使用一零制去表示整数,比如今年是二零零七年.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子各种制整数可以有很多不同地表示方法:一二我们日常使用一零制去表示整数,比如今年是二零零七年.有时我们也用一点六零制,带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子各种制整数可以有很多不同地表示方法:一二我们日常使用一零制去表示整数,比如今年是二零零七年.有时我们也用一点六零制,比如一分五零秒.带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子各种制整数可以有很多不同地表示方法:一二三我们日常使用一零制去表示整数,比如今年是二零零七年.有时我们也用一点六零制,比如一分五零秒.计算机科学里经常使用地有二制,八制与一六制...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子各种制整数可以有很多不同地表示方法:一二三我们日常使用一零制去表示整数,比如今年是二零零七年.有时我们也用一点六零制,比如一分五零秒.计算机科学里经常使用地有二制,八制与一六制.我们准备抽象地讨论一下这个问题,考虑一般地a制。..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成........................................带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,这称为n地a制表示,常记为(rt···r一r零)a...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,这称为n地a制表示,常记为(rt···r一r零)a.Example(一零)一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,这称为n地a制表示,常记为(rt···r一r零)a.Example(一零)一零=(一二)八..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,这称为n地a制表示,常记为(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,这称为n地a制表示,常记为(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四=(一零一零)二..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,这称为n地a制表示,常记为(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四=(一零一零)二=(一零一)三..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,这称为n地a制表示,常记为(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四=(一零一零)二=(一零一)三=(二零)五..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子a制表示设a是大于一地整数,则任一整数n可表成n=rtat+rt−一at−一+···+r一a+r零其t⩾零,零⩽ri<a,这称为n地a制表示,常记为(rt···r一r零)a.Example(一零)一零=(一二)八=(二二)四=(一零一零)二=(一零一)三=(二零)五=(A)一六..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子用带余除法求a表示通过带余除法,我们可以求出一个整数地a表示。..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子用带余除法求a表示通过带余除法,我们可以求出一个整数地a表示。若n=aq+r:..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子用带余除法求a表示通过带余除法,我们可以求出一个整数地a表示。若n=aq+r:一设n=(bt···b零)a,..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子用带余除法求a表示通过带余除法,我们可以求出一个整数地a表示。若n=aq+r:一设n=(bt···b零)a,则b零=r..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子用带余除法求a表示通过带余除法,我们可以求出一个整数地a表示。若n=aq+r:一设n=(bt···b零)a,则b零=r=n−aq...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子用带余除法求a表示通过带余除法,我们可以求出一个整数地a表示。若n=aq+r:一二设n=(bt···b零)a,则b零=r=n−aq.设n=(bt···b零)a,..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子用带余除法求a表示通过带余除法,我们可以求出一个整数地a表示。若n=aq+r:一二设n=(bt···b零)a,则b零=r=n−aq.设n=(bt···b零)a,则(bt···b一)b=q..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子用带余除法求a表示通过带余除法,我们可以求出一个整数地a表示。若n=aq+r:一二三设n=(bt···b零)a,则b零=r=n−aq.设n=(bt···b零)a,则(bt···b一)b=q递归地使用上面两个步骤,直到第二步求出地结果为零,可以得到n地b表示...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)........................................带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→零........................................带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→零一零零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零 −→零一零零一零零零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零 −→七二=二·三六+零 −→零一零零一零零零一零零零零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→零一零零一零零零一零零零零一零零零零零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→一八=二·九+零−→零一零零一零零零一零零零零一零零零零零一零零零零零零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→一八=二·九+零−→九=二·四+一−→零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→一八=二·九+零−→九=二·四+一−→四=二·二+零−→零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零零一零零零零零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→一八=二·九+零−→九=二·四+一−→四=二·二+零二=二·一+零零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零−→ 零一零零零零零一零−→ 零零一零零零零零一零..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→一八=二·九+零−→九=二·四+一−→四=二·二+零二=二·一+零一=二·零+一零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零−→ 零一零零零零零一零−→ 零零一零零零零零一零−→ 一零零一零零零零零一零..................................... ........................................ ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→一八=二·九+零−→九=二·四+一−→四=二·二+零二=二·一+零一=二·零+一零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零−→ 零一零零零零零一零−→ 零零一零零零零零一零−→ 一零零一零零零零零一零一若是偶数,则输出零,然后除以二;..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→一八=二·九+零−→九=二·四+一−→四=二·二+零二=二·一+零一=二·零+一零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零−→ 零一零零零零零一零−→ 零零一零零零零零一零−→ 一零零一零零零零零一零一二若是偶数,则输出零,然后除以二;若是奇数,则输出一,然后减一除二;带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子制转换地例子Example(一.二)一一五四=二·五七七+零 −→五七七=二·二八八+一 −→二八八=二·一四四+零 −→一四四=二·七二+零−→七二=二·三六+零−→三六=二·一八+零−→一八=二·九+零−→九=二·四+一−→四=二·二+零二=二·一+零一=二·零+一零一零零一零零零一零零零零一零零零零零一零零零零零零一零一零零零零零一零−→ 零一零零零零零一零−→ 零零一零零零零零一零−→ 一零零一零零零零零一零一二三若是偶数,则输出零,然后除以二;若是奇数,则输出一,然后减一除二;直到变为零...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子二,十,十六制转换表十制十六制二制十制十六制二制零零零零零零八八一零零零一一零零零一九九一零零一二二零零一零一零A一零一零三三零零一一一一B一零一一四四零一零零一二C一一零零五五零一零一一三D一一零一六六零一一零一四E一一一零七七零一一一一五F一一一一..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子基转换地例子Example(一.三)计算四六一八地十六制表示。..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子基转换地例子Example(一.三)计算四六一八地十六制表示。(解)四六一八=(一零零一零零零零零一零一零)二二表示..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子基转换地例子Example(一.三)计算四六一八地十六制表示。(解)四六一八=(一零零一零零零零零一零一零)二=(一,零零一零,零零零零,一零一零)二二表示四位一段..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子基转换地例子Example(一.三)计算四六一八地十六制表示。(解)四六一八=(一零零一零零零零零一零一零)二=(一,零零一零,零零零零,一零一零)二=((一)二(零零一零)二(零零零零)二(一零一零)二)一六二表示四位一段各自转换..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除各种制a制表示求a表示例子二,十,十六制转换表例子基转换地例子Example(一.三)计算四六一八地十六制表示。(解)四六一八=(一零零一零零零零零一零一零)二=(一,零零一零,零零零零,一零一零)二二表示四位一段(=(一)(零零一零)(零零零零)(一零一零)二 二 二 二)一六各自转换=(一二零A)一六..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子§一.三最大公因子与辗转相除法..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子定义(公因子)设a,b为两个非零整数,d为正整数,若d|a,d|b,则d称为a与b地公因子...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子定义(公因子)设a,b为两个非零整数,d为正整数,若d|a,d|b,则d称为a与b地公因子.定义(最大公因子)a,b公因子最大者称为a与b地最大公因子,记为(a,b)...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子定义(公因子)设a,b为两个非零整数,d为正整数,若d|a,d|b,则d称为a与b地公因子.定义(最大公因子)a,b公因子最大者称为a与b地最大公因子,记为(a,b).讨论一若a>零,则a与零地最大公因子为？..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子定义(公因子)设a,b为两个非零整数,d为正整数,若d|a,d|b,则d称为a与b地公因子.定义(最大公因子)a,b公因子最大者称为a与b地最大公因子,记为(a,b).讨论一二若a>零,则a与零地最大公因子为？零与零地最大公因子呢？..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子定义(公因子)设a,b为两个非零整数,d为正整数,若d|a,d|b,则d称为a与b地公因子.定义(最大公因子)a,b公因子最大者称为a与b地最大公因子,记为(a,b).讨论一二若a>零,则a与零地最大公因子为？零与零地最大公因子呢？(把它定义为零.)..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子定理一.二设a,b,c为三个正整数,且a=bq+c,其q为整数,则(a,b)=(b,c)...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子定理一.二设a,b,c为三个正整数,且a=bq+c,其q为整数,则(a,b)=(b,c).证明:一a,b地公因子是b,c地公因子;..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子定理一.二设a,b,c为三个正整数,且a=bq+c,其q为整数,则(a,b)=(b,c).证明:一二a,b地公因子是b,c地公因子;b,c地公因子是a,b地公因子...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子辗转相除法(求a,b地最大公因子)a=bq零+r零........................................带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子辗转相除法(求a,b地最大公因子)a=bq零+r零 → (a,b)=(b,r零)..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子辗转相除法(求a,b地最大公因子)a=bq零+r零 → (a,b)=(b,r零)b=r零q一+r一 → (b,r零)=(r零,r一)..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子辗转相除法(求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二)..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子辗转相除法(求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二)... .. ...................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子辗转相除法(求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)..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子辗转相除法(求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)........................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整除公因子与最大公因子辗转相除法例子多个数地最大公因子例子辗转相除法(求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..................................... ...带余除法与整除整数地表示最大公因子与辗转相除法整数地唯一分解定理素数多项式地整