《算数基本定理》课件.ppt

算数基本定理,,,定理1(算术基本定理) 任一大于1的整数能表示成素数的乘积, 即对于任一整数a＞1,有 a=p_1…p_n, p_1≤…≤p_n,其中p_1,…,p_n是素数, 并且若a=q_1,…,q_m, q_1≤…≤q_m,其中q_1,…,q_m是素数,则m=n,q_i=p_i,i=1,…,n.,,,推论2 任一大于1的整数能惟一地表示成a=p_1^{k_1}…p_s^{k_s}, p_1＜…＜p_s.,注：上式叫做a的标准分解式.,推论3 若a|n,b|n,(a,b)=1,则ab|n.,,,我们知道, 正整数可以按约数的多少分为3类: 第1类: 仅含一个数1, 称为单位; 第2类: 仅含两个约数的数, 是素数; 第3类: 含有大于两个的约数的数, 是合数.,素数是组成自然数的元素或原子.,定理2 素数的个数是无穷的.,,,为了把素数从自然数中筛选出来,古希腊的数学家厄拉多塞(Eratosthenes, 约前276-前195)设计了一种筛法. 例如,为了求出不超过100(或任给的正整数)的所有素数,只要把1和不超过100的正合数都删去即可.,,,,,注: 1)100以内的素数只有25个,即 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97; 2)从这不超过100的25个素数出发,重复上面的做法,就可以找出不超过100^2=10000的全部素数, 这种寻找素数的方法,通常叫做厄拉多塞筛法.,,,例1 求15与27的最大公约数与最小公倍数. 解 因为15=3×5, 27=3^3, 所以 (15,27)=3, [15,27]=3^3×5=135. 更一般地,有,,,,,推论4 设a=p_1^{s_1}…p_k^{s_k}, b=p_1^{t_1},…,p_k^{t_k}, 则a,b的最大公约数为:p_1^{m_1}…p_k^{m_k},这里m_i=min(s_i,t_i),而a,b的最小公倍数为:p_1^{d_1}…p_k^{d_k},这里d_i=max(s_i,t_i),由于m_i+d_i=s_i+t_i,所以 ab=(a,b)[a,b].,例2 证明: 形如4k-1的素数是无限的. 证明思路同定理2.,,,一般地,设k＞0,l＞0,(k,l)=1,则形如kn+l的素数有无限多个,这个定理叫狄利克莱(Dirichlet,1805-1859,德国数学家)定理.,定义1 设p是一个素数,形如2^p-1的数叫做麦什涅数,记做M_p=2^p-1.,,,几个定义,定义2 我们把F_n=2^{2^n}+1, n≥0, 叫做费马数.,谢谢观看,。