初等数论自考真题及答案解析

1, 16k + 11 = 15k + k + 11, k = 3, 16*3 + 11 = 15*3 + 14 = 45 + 14 = 59, 59 + 15*16*m = 13*4 + 7 + (13+2)*(13+3)m = 13*4 + 7 + 13(5 + 13)m + 6m = 13(18m + 5) + 6(m-1), m = 7, 59 + 15*16*7 = 1739 1739 + 13*15*16n, n = 0,1,2,... 满足要求。 2， 3^(2009) = 3*(3^2)^(1004) = 3*(10-1)^(1004) = 3*[10^(1004) - 1004*10^(1003)+ ... + 1004*1003*10^2/2 - 1004*10 + 1] 3^(2009) = 3*[-1004*10 + 1] (mod100) = 3[1 - 10040] (mod100) = 3[1 - 40] (mod100) = 3*61 (mod100) = 183 (mod100) = 83 (mod100) 3, 正整数a,b互质的充要条件是关于x,y的方程ax + by = 1有整数解。 因此，ax + by = c 有整数解的充要条件是 c为a,b 的最大公约数。 4， Legendre(a/p)=0, if a = 0 (modp); Legendre(a/p)=+1, if a不等于0，且对于某个整数x, x^2 = a (modp) Legendre(a/p)=-1, 若不存在整数x,使得x^2 = a (modp). Legendre(482/503)=Legendre(2/503)*Legendre(241/503) Legendre(2/503) = (-1)^[(503^2 - 1)/8] = (-1)^[502*504/8] = (-1)^[251*126] = 1, Legendre(241/503) = (-1)^[(241-1)*(503-1)/4]*Legendre(503/241) = (-1)^[240*502/4]*Legendre(21/241) = Legendre(3/241)*Legendre(7/241) = (-1)^[(3-1)*(241-1)/4]*Legendre(241/3)*(-1)^[(7-1)*(241-1)/4]*Legendre(241/7) = (-1)^[2*240/4]*Legendre(1/3)*(-1)^[6*240/4]*Legendre(3/7) = Legendre(1/3)*Legendre(3/7) = 1*(-1)^[(3-1)*(7-1)/4]*Legendre(7/3) = (-1)^[2*6/4]*Legendre(1/3) = (-1)*1 = -1. 娘啊，累惨了。。休息一哈。。5,512^50 = (11*45 + 17)^50 = 17^50 (mod45)= 289^25 (mod45) = (45*6 + 19)^25 (mod45) = 19^25(mod45)= 19*361^12(mod45)=19*(8*45+1)^12(mod45) = 19(mod45)6,[2009/3] + [2009/3^2] + [2009/3^3] + [2009/3^4] + [2009/3^5] + [2009/3^6] 【[]表示取整运算哈】= 669 + 223 + 74 + 24 + 8 + 2= 10007,x = 5

尾数为7则(10,n)=1考虑1,11,111,……必有2个模n同余。作差后由于(10,n)=1，除去10的幂，可以得到一个各位全为1的数字是n的倍数。

1. 因为(k,n)=d，则存在整数s, t，使得ks+nt=d. 所以a^(ks)=1(mod m) a^(nt)=1(mod m) a^d=a^(ks+nt)=1(mod m)2. 因为当(b,a)=1当且仅当(a-b, a)=1. 用如同高斯求1+2+......+100相同的方法可知： 和=1/2 *(a-b+b) *φ(a)=1/2 *a*φ(a).3. 需要证ax+b(x取遍m的完全剩余系)是m的完全剩余系。 因为ax+b=ay+b(mod m) 当且仅当a(x-y)=0(mod m) 当且仅当m|a(x-y). 因为(a,m)=1. 所以m|x-y. 即x=y(mod m). 所以所求式子=1/m+2/m+......+(m-1)/m=1/2 *(m-1).4. 接上题： 所求式子=a/m+2a/m+......+(m-1)a/m-1/2 *(m-1). =1/2 *(m-1)(a-1).5. 先看第6题，证明(p-1)!=-1(mod p). 因为p-a=-a(mod p). 所以(p-1)!=(((p-1)/2)!)*(-(p-1)/2)*......*(-2)(-1) =(((p-1)/2)!)^2 * (-1)^((p-1)/2). =-1(mod p). 所以(((p-1)/2)!)^2+(-1)^((p-1)/2)=0(mod p).6. (p, p-1)=1. (p-1)!=0(mod p-1). 下面证(p-1)!=-1(mod p). p=2, 3时成立；p>=5时： 首先对于任意a(2<=a<=p-2)，存在唯一的b(2<=b<=p-2)，使得ab=1(mod p). 对于a、2a、......、(p-1)a这p-1个数中，它们两两mod p不同余。 否则存在i、j（i、j不相等）使得ia=ja(mod p). p|a(i-j). p|i-j. 则i=j，矛盾。 又因为ia mod p不为0， 所以a、2a、......、(p-1)a这p-1个数中，mod p是1~p-1的一个排列， 所以存在唯一的b(1<=b<=p-1)，使得ab=1(mod p). 又因为a与(p-1)a mod p都不为1，所以2<=b<=p-2. 这样，将每个a、b进行配对a1、b1、a2、b2...... 2*3*......*(p-2)=(a1*b1)(a2*b2)......=1(mod p). 所以(p-1)!=1*1*(p-1)=-1(mod p). 综上(p-1)!=p-1(mod p(p-1)). 7. x^y=y^(x-y). 显然x-y>=0. 若x=y，则x^x=x^0=1. 则x=1, y=1. 若x>y，则y2y. 设x=ky，k>2. 则k^y * y^y=y^((k-1)y). ky=y^(k-1). k=y^(k-2). y=k^(1/(k-2)). 根据求导发现函数f(k)=k^(1/(k-2))在k>2递减， 而f(k)->正无穷(k->2), f(3)=3, f(4)=2, f(k)->1(k->正无穷). 所以k=3, 4时对应两组解：x=9, y=3; x=8, y=2. 且k>4时无解。 下面证21, y>1时： 原式mod 4： 1-(-1)^y=2(mod 4). y=1(mod 2). 原式mod 9： 5^x=2(mod 9). x=5(mod 6). 原式mod 7： 因为当x=5(mod 6)时，5^x=3(mod 7). 所以3^y=1(mod 7). 所以y=0(mod 6). 与y是奇数矛盾。 综上只有一组解x=y=1.

由于(10,n)=1利用Euler公式有10^φ(n)≡1(mod n)即n|(10^φ(n)-1)即φ(n)个9是n的倍数 ，且没有0

题目的意思就是用27与15线性组合，得到6，这是数论的典型题。即：27x+15y=6 9x+5y=2(9,5)=1 |2 必定有解。题目数字小，直接可以观察出来特解。但如果观察不出来，就通过求最大公约数的过程得出一个特解：9=5+45=4+1出现公约数“1”即可反推：公约数1＝5-4＝5*2-9所以有：2＝5*4-9*2即6=15*4-27*2（x,y)=(-2, 4)即得一个特解。通解是（-2+5t, 4-9t）, t是任意整数。

第二题 楼上的，你给分吧， 3^4=81, 那么 3^2008=(3^4)^502= *…*1 , 3^2009 =3^2008 x 3 = *…*3 上上楼的自己都搅混了， 3^20= *…*01, 那么3^2009= *……*01 x 3^9 3^9 = 19683 所以 3^2009= *…*83 应该是83 其实正确的做法是构造10， 3^2009 = 3^2^1004 x 3 = 9^1004 x 3 =(10-1)^1004 x 3 注意1004是偶数，最后一项为-1的偶数次方，那么倒数第二项系数为-1004 展开为 （10^1004 - 1004x10^1003 + …… -1004x10 + 1） x 3 前面的都是“整百数字”， 只看最后两个 M x 100-10040+1 = N x100 - 40 + 1 = (N-1)x 100 +61 61 x 3 = 183 所以到最后，3^2009末尾两位应为 83 第6题 3|2009 3|669 3|221 3|73 3|24 3|8 2 3的指数为669+221+73+24+8+2=997 第五题 40 520 = 11x45+25, 所以 520^50(mod45)= (11*45+25)^50 (mod45) = 25^50(mod45) = 625^25(mod45) 625 = 14*45-5 所以上式= [（14*45-5）^5]^5 (mod45) = (N-625)^5 (mod45) -625 = -14*45+5,即-625=5(mod45)所以上式= 5^5(mod45)=625(mod45)= -5(mod45)= 40 (mod45) 第一题 3120K+1739 K=0，1，2，…… 首先确定,这种数字是每个公倍数段上一“轮回”，第一个数的范围 为 0 至 13*15*16 =3120，最后的结果要加上公倍数3120的K倍。 13分别与0~9乘再加10， 末位为 0，3，6，9，2，5，8，1，4，7； （因为只要末尾所以实际用3来乘再加0） 15分别乘，再加14，末位为 4，9，……（实际用5乘再加4） 16分别乘，再加11，末位为 7，3，9，5，1,……（实际用6乘再加1） 比较以上两组数字，得到该数最后一位为 9， 与13相乘再加10能得到9的，必须有乘数末位为3 现在分别用3，13，23，33，43……233去试算（为什么是233，因为15*16=240，过了这个界限就循环了，在这个范围内找不到的话，就没解了） 看起来挺麻烦的，但是还好只有24个试算值，而且应该不会到最后一个才找到^_^， 结果1739 = 13*133+10 = 15*115+14 = 16*108+11第三题 当a=b=0时,c=0