数论基础（续） 网络安全 NETWORK SECURITY 欧拉函数中n) n是正整数，中()是比n小且与n互素的正整数的个数 ==== 1K1)1=1 {1,2}1=2 中 1K1,3}=2 1K1,2,3,4}1=4 中(6 |K1,5}1=2 中(7) 是2,3,4,56三 中(10)=1K1,3,7,9}1=4 中(11) =,2,34,5,5,78,910l=10 如果p是素数，则中p)=(p-)比如中(2)，(5) 中11) 如果p,9是素数，则中(pg)=中(p中(g)=(p-1(g-) 比如中(10) 1515 数论基础（续） • 欧拉函数ф(n) ▪ n是正整数， ф(n)是比n小且与n 互素的正整数的个数 ф(2) = |{1}| =1 ф(3) = |{1, 2}| =2 ф(4) = |{1, 3}| =2 ф(5) = |{1, 2, 3, 4 }| =4 ф(6) = |{1, 5}| =2 ф(7) = |{1, 2, 3, 4, 5, 6}| =6 ф(10) = |{1, 3, 7, 9}| =4 ф(11) = |{1, 2,3,4,5,6, 7,8, 9,10}| =10 ▪ 如果p是素数，则ф(p)=(p-1), 比如ф(2), ф(5)， ф(11) ▪ 如果p,q 是素数，则ф(pq)=ф(p)ф(q)＝ (p-1)(q-1), 比如, ф(10)