数论基础课件.ppt

命题 10 设 是n的素因子分解式。当i≠j时, pi≠pj。 于是 证明 设p为素数，先求φ(pα)。对任意的a, (a, pα)=1, 说明a不是p的倍数。而在1~pα的pα个数中，是p的倍数者共有pα-1(pα=p×pα-1)个，即p, 2p, …, pα-1·p。 故小于pα与pα互素者共有pα-pα-1=pα(1-p-1)个，于是φ(pα)=pα(1-p-1)。 由命题9， 有 命题 11（Euler定理) 设n＞1∧(a, n)=1，则aφ(n)≡1(mod n)。 证明 令x遍历从非负的最小剩余得来的与模互素的剩余组 x=r1, r2, …, rφ(n)，则ax的非负的最小剩余组ρ1, ρ2, …, ρφ(n) 也是这样的组，只是先后顺序有所变动（命题8）。把同余式ari≡ρi(mod n), i=1, 2, …, φ(n)逐项相乘，可得 从等式两边约掉 ， 得到 ac≡1(mod n), c=φ(n) 推论（Fermat定理） 设p为素数且(a, p)=1，则 ap-1≡1(mod p) 式中两边同乘以a，可得更简捷的形式，即ap≡a(mod p)，它对任意的整数a都成立。 1.8 数论中特殊的函数及特殊的数 1.8.1 整数a的因子函数τ(a) 命题 1 设a∈Z+且a有标准因子分解式 若记a的全部因子为τ(a)，则τ(a)=(α1+1)(α2+1)…(αk+1)。 证明 显见a的任一因子b必可写成如下形式： 且每个βi(i=1, 2, …, k)的取值都有0, 1, 2, …，αi这αi+1种可能之一。由于β1, β2, …,βk共有(α1+1)(α2+1)…(αk+1)种不同的取值组合，且每个组合都恰产生a的一个因子，故τ(a)=(α1+1)(α2+1)…(αk+1)。 1.8.2 整数a的因子的和函数σ(a) 命题 2 设a∈Z+，且a有标准因子分解式 αi≥0 (1≤i≤k) 若用σ(a)表示a的全部因子之和，则 证明 对k施用归纳法。当k=1(a=p1α1)时，则 当 设对k-1时有 则对k可得 例1 设τ(a)=(α1+1)(α2+1)…(αk+1)=3，求a。  解 因3为素数，故τ(a)的连乘表达式中只能有一个因式。 所以τ(a)=α1+1=3，即α1=2。又因2是最小素数，所以应在a的标准分解式中取p1=2，从而a=p1α1=22=4，a的3个因子为1，2， 4。当然，9也有3个因子1，3，9，但一般要求的是最小正数。 例 2 若τ(a)=(α1+1)(α2+1)=6，求a。  解 因α1, α2有两组解：α1 =5, α2 =0及α1 =2, α2 =1，它们分别对应a的两种不同分解形式：a=p51或a=p21p2。对后一形 式，可得a=22·3=12， 其5个因子分别为1, 2, 3, 4, 6, 12; 对前一形式， 有a=25=32＞12，因此a=12。 例 3 对τ(a)=60，求a。 解 因τ(a)=60=2·2·3·5，又由大到小α1=4, α2=2, α3=1, α4=1，故a的标准分解式为a=p41·p22·p3·p4，在10 000以内满足条件的数共有3个，即 24·32·5·7=5040, 24·32·5·11=7920, 24·32·5·13=9360 其中以5040为最小。 1.8.3 Mobius（μ）函数 设a∈Z+且a有标准因子分解式： , αi≥0(1≤i≤k)，则 .. 设a, b∈Z+， (a, b)=1，若θ(ab)=θ(a)θ(b)，则称θ为积性函数。对积性函数有 命题 3 设a∈Z+，a的标准分解式为 , 则 本命题说明τ, σ, φ, μ均为积性函数。 积性函数有很重要的用途，即对某个a∈Z+, 能利用其所有素因子幂的函数值求出该积性函数对a的函数值。 1.8.4 梅桑数（Mersenne Numbers） 法国数学家梅桑（M.Mersenne, 1588~1648）猜测，当p为素数时，具有特殊形式Mp=2p-1 的数是素数。确实，当p=2, 3, 5, 7时，Mp是素数，但当p=11时，M11=211-1=23·89=2047却是个合数，这是梅桑在世时就知道的结论。为了纪念梅桑对2n-1(n∈N)形状的数所做的研究，常称其为