第三章
1.
解 依次计算同余式
22 4,24 16,28 256,216=65536 154,
232 1542=23716 1 (mod 641)。
因此
2.
解 有71 3,72 1,74 1 (mod 10),
因此,若 77 r (mod 4),
则
现在77 (1)7 1 3 (mod 4),所以由上式得到
即n的个位数是3。
3.注:一般地,若求 对模m的同余,可分以下步骤进行:
(ⅰ) 求出整数k,使a*k 1 (mod m);
(ⅱ) 求出正整数r,r < k,使得b*c r (mod k);
(ⅲ) a *r (mod m)。
4. 例3 求(25733 46)26被50除的余数。
解(25733 46)26 (733 4)26 = [7(72)16 4]26
[7( 1)16 4]26 = (7 4)26
326 = 3(35)5 3(7)5 = 37(72)2
21 29 (mod 50),即所求的余数是29。
5.
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
2x2-5y2=7没有整数解.
6. 例1 设m > 0是偶数,{a1, a2, , am}与{b1, b2, , bm}都是模m的完全剩余系,证明:
{a1 b1, a2 b2, , am bm}不是模m的完全剩余系。
7. 例2 设A = {x1, x2, , xm}是模m的一个完全剩余系,以
{x}表示x的小数部分,证明:若(a, m) = 1,则
8.
9. 例3 设{x1, x2, …, x(m)}是模m的简化剩余系,则
(x1x2…x(m))*2 1 (mod m)。
解记P = x1x2…x(m),则(P, m) = 1。又记yi =
1 i (m),
则{y1, y2, …, y(m)}也是模m的简化剩余系,因此
(mod m),再由Euler定理,推出 P*2 P*(m) 1 (mod m)
** 同余式可以像等式一样进行代换。
第二章 1. 利用辗转相除法求解
2. 例3 设a,b,c是整数,(a, b) = 1,则在直线
ax by = c上,任何一个长度大于的线段上至少有一个点的坐标都是整数。
解 由定理1,直线ax by = c上的坐标都是整数的
(xt, yt)的坐标是
, tZ,
其中(x0, y0)是直线ax by = c上的坐标都是整数的点,由定理2,这样的点是存在的。
对于任意的tZ,记Pt是以(xt, yt)为坐标的点,则Pt 1与Pt 之间的距离
这说明,两个“相邻的”坐标是整数的点的距离是
,从而得出所求之结论。
3. 例2 将 写成三个分数之和,它们的分母分别是2,3和5。
解:设
则 15x 10y 6z = 19。
依次解方程5t 6z = 19,15x 10y = 5t,得到 uZ,
, u, vZ。
取u = 0,v = 0,得到x = 1,y = 1,z = 4,因此
4. 若(x, y, z)是方程(1)的满足条件(2)的解,
则下面的结论成立:
(ⅰ) x与y有不同的奇偶性;
(ⅱ) x与y中有且仅有一个数被3整除;
(ⅲ) x,y,z中有且仅有一个数被5整除。
证明 (ⅰ) 若2x,2y,则2z,这与(x, y, z) = 1矛盾。
所以x与y中至少有一个奇数。如果x与y都是奇数,则
x2 =4m+1,,y2 =4n+ 1,x2 y2 =4(m+n)+2,
而 z2=4N或4N+1,
所以x,y,z不可能是方程(1)的解。
因此,x与y有不同的奇偶性。
第四章
1.
2. 10x 22 (mod 36)
等价于解不定方程10x -36y=22 求整数x,再按模36分类:
x 13 (mod 36) x 31 (mod 36)
3. 1296x 1125 (mod 1935)
解(1296,1935)=9,9|1125,故同余式有9个解
化简为 144 x 125 (mod 215)
4.从另一角度考虑 ax b (mod m) (2)
(1)当(a, m)=1时,(2)恰有一个解:
(2)当(a, m)=d ≠ 1时,(2) 有解时有d个解,且d|b
5. 10x 22 (mod 36)
两种解法:
x 13 (mod 36)
x 31 (mod 36)
6. 1296x 1125 (mod 1935)
解(1296,1935)=9,9|1125,故同余式有9个解
化简为 144 x 125 (mod 215),故
7. 解同余方程组
解 将(1)的前一式乘以2,后一式乘以3再相减得到
19y 4 (mod 7),
5y 4 (mod 7),
y 2 (mod 7)。
再代入(1)的前一式得到
3x 10 1 (mod 7),
x 4 (mod 7)。
即同余方程组(1)的解是x 4,y 2 (mod 7)
8. 七数余一,八数余一,九 数余三,问此数?
9.
10.( Wilson定理) ( p 1)! +1 0 (mod p)
即模p的一个简化剩余系中全体数之积对模p与-1同余。
证明 (1) 由Fermat定理,数1, 2, , p 1是同余式
x p 1 1 (mod p) 的解,因此,利用定理2即有。
(2) 在(1)中取x =p即可。
注:Wilson定理其实是充要条件,即
p是素数当且仅当( p 1)! +1 0 (mod p)
定理4(Lagrange) 同余方程(1)的解数 n,即最多有n个解
证明 假设同余式(1)解数多于n,则至少有n + 1个不同的解,
设x xi (mod p),1 i n 1为(1)的n+1个不同的解,则
由定理2,有
f(x) an(x x1)(x xn) (mod p),因此
0 f(xn + 1) an(xn + 1 x1)(xn + 1 xn) (mod p)。
由于p an,xn + 1 xi (mod p),1 i n,所以上式不能成立。这个矛盾说明同余方程(1)不能有n 1个解。证毕。
注:(1)此定理仅对质数模同余式成立.如x 3 x 0 (mod 6)有6个解
(2)若同余式(1)解数大于n,则p整除所有系数
(3)由定理1,4知:(1)的次数>p时,(1)的解数
0换成b<0也对,此时r的范围换成0≤r<-b即可;
(3)合起来即:设a与b是两个整数,b 0,则存在唯一的两个整数q和r,使得
a = bq r,0 r < |b|。
4.由于每个非零整数的约数的个数是有限的,所以一组不全为零的整数的最大公约数是存在的,并且是正整数。
若a1, a2, , ak两两互素,则可以推出(a1, a2, , ak) = 1,反之则不然,例如
(2, 6, 15) = 1,但(2, 6) = 2
5.推论 设a是大于1的整数,且
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
分解式为
则:
定理2 任何大于1的整数a都至少有一个质因数
证明 若a是质数,则定理是显然的。
若a不是质数,那么它有两个以上的正的非平凡因数,设它们是d1, d2, , dk 。不妨设d1是其中最小的。若d1不是质数,则存在1 1是最小的质因数,所以d1*2 a。
性质 设x与y是实数,则
(ⅰ) x =[x]+{x} , 若0 x < 1,则[x] = 0;
(ⅱ) x y [x] [y];
(ⅲ)[x] ≤ x < [x] +1, x-1 <[x] ≤ x ,0≤ {x} <1;
(ⅳ)若m是整数,则[m x] = m [x];
(ⅴ)[x ] [y] [x +y] , {x} {y} ≥{x +y}
(ⅵ) [x] =
{x} =
(ⅶ)(带余数除法)若a,b是两个整数,b>0,则
(ⅷ)若a,b是任意两个正整数,则不大于a而为b的倍数
的正整数个数是
6.设n是正整数,1 k n 1,则
若n是素数,则n
1 k n 1
7. 例1 设a1, a2, , an是整数,且
a1 a2 an = 0,a1a2an = n,则4n。
解 如果2不整除n,则n, a1, a2, , an都是奇数。于是a1 a2 an是奇数个奇数之和,不可能等于零,这与题设矛盾,所以2n,即在a1, a2, , an中至少有一个偶数。如果只有一个偶数,不妨设为a1,那么2不整除ai(2 i n)。此时有等式
a2 an = a1,
在上式中,左端是(n 1)个奇数之和,右端是偶数,这是不可能的,因此,在a1, a2, , an中至少有两个偶数,即4n。
例2 设a0, a1, , anZ,f(x) = anxn a1x a0 ,已知f(0)与f(1)
都不是3的倍数,证明:若方程f(x) = 0有整数解,则
3f(1) = a0 a1 a2 (1)nan
解 对任何整数x,都有 x = 3q r,r = 0,1或2,qZ。
(ⅰ) 若r = 0,即x = 3q,qZ,则
f(x) = f(3q) = an(3q)n a1(3q) a0 = 3Q1 a0 = 3Q1 f(0),
其中Q1Z,由于f(0)不是3的倍数,所以f(x) 0;
(ⅱ) 若r = 1,即x = 3q 1,qZ,则
f(x) = f(3q 1) = an(3q 1)n a1(3q 1) a0
= 3Q2 an a1 a0 = 3Q2 f(1),
其中Q2Z。由于f(1)不是3的倍数,所以f(x) 0。
因此 若f(x) = 0有整数解x,则必有 x = 3q 2 = 3q 1,q Z,
于是 0 = f(x) = f(3q 1) = an(3q 1)n a1(3q 1) a0
= 3Q3 a0 a1 a2 ( 1)nan = 3Q3+f(1),
其中Q3Z。所以3f(1) = a0 a1 a2 (1)*nan 。
例3 设a,b是整数,且 9a2 ab b2 (1)
则3(a, b).
解 由式(1)得到
9(a b)2 3ab 3(a b)2 3ab
3(a b)2 3a b (2)
9(a b)2
再由式(1)得到
93ab 3ab
因此,3a或3b。
若3a,由式(2)得到3b;若3b,由(2)式也得到3a。因此,总有3a且3b。则 3(a, b)。
例4 若a > 1,a n 1是素数,则a = 2,并且n是素数。
解 若a > 2,则由
an 1 = (a 1)(an 1 an 2 1)
可知a n 1是合数。所以a = 2。
若n是合数,则n = xy,x > 1,y > 1,于是由
2xy 1 = (2x 1)(2x(y 1) 2x(y 2) 1)
以及2x 1 > 1可知2n 1是合数,所以2n 1是素数时,n必是素数。
注:若n是素数,则称2n 1是Mersenne数。
练习
1、求325与214的最大公因数
2、求1008与1134的最小公倍数
3、边长为1厘米的正方体2100个,堆成一个实心的长
方体,它的高是10厘米,长和宽都大于高,求长和宽
4、已知十个正整数之和为1001,这十个正整数的最大公因数为d,
5、将2,4,6,8,12,16,24,48分成两组,每组四 个数,使它们的积相等
6、求40!的标准分解式
7、计算
8、解方程