云书歌谣与事件
A2同时发生. 由于(m1,m2)?1, 故A1与A2是相互独立的. 从而
P(A)?P(A1?A2)?P(A1)P(A2).
但是
P(A)?E???(m)m,
P(A1)?E1??m2?(m1)m??(m1)m1, P(A1)?E2??m1?(m2)m??(m2)m2.
所以
?(m)m??(m1)m1??(m2)m2.
即
?(m)??(m1)?(m2). ▋
1), i?1,2,?,t. 从而由ⅳ）得 pi2tv）由ⅲ）有?(pi?i)?pi?i?1(pi?1)?pi?i(1?1?(n)??(p1?)?(p2?)??(pt?)
?p1?1(1?111)p2?2(1?)?pt?t(1?) p1p2pt?n(1?t111)(1?)?(1?) p1p2pt?n?(1?i?11) (pi为n的全部不同的素因子) pi1?n?(1?) (p为素数) . ▋
pp|n下面我们介绍Euler函数的若干应用. 例1. 6 证明：素数有无穷多个. 证 设素数只有有限个
p1,p2,?,pn.令a?p1p2?pn, 则在1到a的所有正整数中与a互素的
只有一个, 即1. 因此?(a)?1, 但
?(a)??(p1p2?pn)
??(p1)?(p2)??(pn)
11
?(p1?1)(p2?1)?(pn?1)?1,
矛盾. 所以素数有无穷多个. ▋
例1. 7 设?(n)解 设n?1?n, 求n?? 3是n的素因数分解, 且
p1?1p2?2?pt?tp1?p2???pt, 则由?(n)?1n得等式
31p1?1p2?2?pt?t(1?1)?(1?1)?p1?1p2?2?pt?t.
p1pt3即有
因为果t. (2.2.2) 3(p1?1)?p(t?1)?p1p?2ptp1?p2???pt, 且pt|3(p1?1)?(pt?1)及pt为素数知pt?3, 从而t?1或2. 如
?1, 则n?3?1. 由(2.2.2)式得3(3?1)?3, 矛盾. 故t?2. 从而p1?2,p2?3. 此时,
1n?2?13?2且(2.2.2)成立. 即?(n)?n成立. 所以
3n?2?13?2,
其中?1,?2是大于0的整数. ▋
练习1. 6
1. 计算欧拉函数值?(2008). 2. 求下列数论方程的所有正整数解.
1）?(x)??(2x); 2)
?(3x)??(4x);
3. 证明分母不大于n的既约真分数的个数等于?(2)??(3)????(n). 12
§1. 7 同余的定义及性质
定义1. 8设m是一给定的正整数, 则称a与b关于模m同余, 记作a模m不同余, 记作aa与b是两个整数, 如果用m分别去除a与b.若得到的余数相同,
?b(modm),并称为同余式；若得到的余数不相同, 则称a与b关于
??b(modm).
依定义,任何一个偶然与0关于模2同余,任何一个奇数与1关于模2同余, 即有
2n?0(mod2), 2n?1?1(mod2)(n??).
再如365?5(mod12)??7(mod12). 显然对任何一整数a与b均有a?b(mod1).对任意两个不同的素数p与q有：q??p(modq)及
p??q(modp).
关于同余的性我们有如下定理
同余的性质定理1. 5 设m是给定的正整数,a,b,c,a1,b1,c1,a2,b2,c2是整数,则有 i)
a?b(modm),成立的充要条件是m|a?b.
ii) 同余是一个等价关系, 即有
a)
a?a(modm), （反身性）.
?b(modm), 则b?a(modm)（对称性）.
?b(modm)且a?c(modm),则a?c(modm)（传递性）.
b) 若ac) 若aiii) 若a1?b1(modm),a2?b2(modm), 则
a1?a2?b1?b2(modm)及a1a2?bb12(modm).
iv) 若av) 若a?b(modm).d?b(modm),d是m的任一因数, 则a?b(modd).
abm?(mod). ddd是a,b及m的任一公因数,则
vi) 若ac?bc?m?,则a?bmodmodm????.特别当(c,m)?1时,有a?b(modm).
(c,m)???1,2. 则a?b(mod[m1,m2]), 反之亦成立.特别当(m1,m2)?1时,
vii) 若a?b(modmi),i有a?b(modm1) 且a?b(modm2)的充要条件是a?b(modm1m2).
viii) 若
(a,m)?1, 则存在
b使
ab?1(modm)13
.可称
b为
a关于模
m的逆, 记为
b?a?1(modm)或a?1|m.
以上性质的证明均较易,我们证明其中几条为,为方便证明,用符号“?”表示“当且仅当”. 证 i)
a?b(modm)?a与b用m去除有相同的余数?a?b与0用m去除有相
同的余数?m|a?b.
ii)?c) 由i)
a?b(modm)且b?c(modm)?m|a?b且m|b?c
?m|(a?b)?(b?c)?a?c(modm).
iii) 由i) 得
a1?b1(modm)及a2?b2(modm)?m|a1?b1及m|a2?b2
?m|(a1(a2?b2)?(a1?b1)b2)?m|(a1a2?bb12)?a1a2?bb12(modm).
vi) 由i)
ac?bc(modm)?m|c(a?b)
??mmcmc?|(a?b)?|(a?b)（因为?,??1）
(c,m)(c,m)(c,m)(c,m)(c,m)???m??a?b?mod?.
(c,m)??vii) 由i) 知a?b(modm1)且a?b(modm2)?m1|a?b且m2|a?b, 即a?b是m1与
i)
m2的公倍数, 从而[m1,m2]|a?b. 再由m1,m2,???mt的情形.
a?b(mod[m1,m2])此性质可推广至任意有限个模数
viii) 若(a,m)?1,则存在整数b与c使ab?mc?1.于是ab?1?m(?c). 即m|(ab?1). 由
i) 得ab?1(modm) . ▋
以上性质形式简单, 证明容易, 但同余式类似普通等式的特点使其具有广泛的应用价值.下面是若于同余式性质的应用实例.
例1. 8 求2008365的个位数字.
365解 即要求一个0到9之间的数a使2008?a(mod10). 由于
2008365?(2?103?8)365?10k?8365.
所以2008365?8365(mod10).又82?60?4?4(mod10),84?42?6(mod10).因此
8365?84?91?1?(84)91?8?691?8?6?8?8(mod10).
14
故a?8. ▋
例1. 9 设?是正整数,?是?的各数位上的数字之和, 证明???(mod9). 证明 设??an?10n?????a1?10?a0,0?ai?9,an?0. 则??an?????a1?a0.由于
ii,10?1?1(mod9), i为正整数. 所以 10?1(mod9)an?10n?????a1?10?a0?an?1?????a1?1?a0?an?????a1?a0(mod9),
即???(mod9). ▋
例1. 10 设正整数
a?an?1000n?????a1?1000?a0,0?ai?1000.
则7整除a的充要条件是7|?(?1)a.
iii?0n证 因为1000??1(mod7),1000i?(?1)i(mod7), 所以由性质定理得
a?an?(?1)n?????a1?(?1)?a0(mod7).
故
7|a?7|?(?1)iai. ▋
i?0i?11|?(?1)ai及
i?0nn同样，因为1000??1(mod11)及1000??1(mod13).我们可得11|a13|a?13|?(?1)iai.
i?0n例1. 11 证明不定方程x证 设x0、
2?y2?8az2?6对任何给定的整数a无整数解.
y0及z0是该不定方程的一组整数解, 即有
222x0?y0?8az0?6. (1.6.1)
将上式关于2取模得x0模得x0222?y0?0(mod2). 因此x0与y0有相同的奇偶性. 再将(3.1.1)关于4取
222?y0?2(mod4).因此x0与y0同为奇数.于是x0?y0?1(mod8). 将(1.6.1)式关于8取
模便得0?6(mod8)矛盾. 故原不定方程无整数解. ▋
15
