《高中竞赛数学辅导：数论重要定理.pdf》由会员分享，可在线阅读，更多相关《高中竞赛数学辅导：数论重要定理.pdf（9页珍藏版）》请在三一文库上搜索。
1、NO.* 1N0.* 数论 一 、欧拉定理 设1m的整数，,1,1 m a mamodm则. 例 1 设 1000 52 6x，求x的末三位数 . 解由二项式定理， 10001000 2499500 10002998349963998233 100010001000 52 652 6 2 552 352 352 32 3CCC 是一个正整数 . 记 1000 1 52 6x，因为 1 052 61,01,x所以从而 11 xx. 而 1 xx是一个正整数，则 1 1,xx所以 11 11.xxx 于是 又因为 500 10003 1 2 52 2 51000xxmod， 33 10002 5
2、， 500 100025003 2 52 52 122mod， 又 所以 3 528ymod， 2 5 528ymod， 528ymod， 则 28 min ymod， 所以 则 因为 所以 NO.* 2N0.* 100100 21125 , 31125modmod ， 于是，有 1500500 21125 ,31125modmod， 500 3 2 2 32125mod， 又因为 1501500 2308mod， 500 33 2 2 552y， 所以 3 5208ymod， 即 528ymod， 所以 68 min ymod， 于是，有 86yk. 所以 所以 1 1250751 1110
3、00xxxmod. 故x的末三位数是001. 二、费马小定理 （1）p为素数，且,1,a p则 1 1 p amodp； （2）p为素数，则 p aa modp. 例 2 , , ,a b c d为整数，证明 44 240/ b dc d aa. 证明 4 24023 5， NO.* 3N0.* 由于 所以 4444 03 b dc ddbc aaaaamod. 即 44 3/ () b dcd aa. 由于奇数的 4次方被 16除余 1，偶数的 4 次方被 16 除余 0，故有 4444 016 b dc ddbc aaaaamod. 即 444 2 / () b dc d aa. 又由于
4、则 4444 05 b dc ddbc aaaaamod， 即 44 5 /() b dc d aa. 又2,3,5两两互素，故 44 240/ b dc d aa. 例 3 设整数 199919991999 , ,0,a b cabcdabc满足记 ，求证 d不是素数 . 证明由于 1999 aa与 同奇偶，则 所以 199919991999 02dabcabcmod， 即 2 / d. 又 3 8933 3a aaaaa mod， 同理 则 199919991999 03dabcabcmod. 即3 / d. NO.* 4N0.* 从而d不是素数 . 例 4 设21 n pnn是给定的素数
5、，证明：数列中有无穷多项 被p整除. 证明当2p时，结论显然成立 . 当 1 221,21 p ppmodp时，由于，所以，所以对任 意的 1 ,21 pm mZmodp有，即 1 21 m p modp. 特别地，取 1,mkpkZ. 则 11 2111 kpp kppmodp. 令11 ,nkpp则2 n n modp，即/ 2 n pn. 三、威尔逊定理 设p是素数，则 1 !1pmodp. 证明考虑多项式 1p xmodp. 由费马小定理，当1,2,1ap时，有 所以 1 1 p ax是多项式的根 .则1,2,1xxxp均为 1 1 p x的因式. 则设 1 1121 p xxxxpQ
6、 x=. 得1Q x，则 1 1121 p xxxxp=. 取xp代入，得 所以 1 !1pmodp. 例 5 1 !1ppmodp是素数，则. 证明： 若21p为奇素数， NO.* 5N0.* 则 2 !1021 p pmodp. 证明： 2 !1021 p pmodp 2!121pmodp. 而21p为奇素数，有2!121pmodp. 四、中国剩余定理 设 12 , k m mmk是 个两两互素的正整数，则同余方程组 有整数解 . 令 12 . k Mmmm 则同余方程组在模M下的解是唯一的 . 令, ii i M MM m 取使得 1 iii M Mmodm ， 则解为 111222kk
7、k xM M bM M bM M bmodM . 例 6 证明：对任意给定的正整数,nn均有 个连续正整数，其中每一个都 有大于1的平方因子. 分析： 则 2 1 2 2 2 1 2 n xmodp xmodp xn modp . 证明： 设 12 , n p ppn为 个互不相同的素数，由中国剩余定理 存在正整数解，设S为一个正整数解，则12SSSn， ，满足要求 . 例 7 任给正整数n，存在n个连续正整数，使得其中每一个数都不 是幂数 . NO.* 6N0.* 证明设 12 , n p ppn为 个互不相同的素数，由中国剩余定理， 同余方程组 存在正整数解 0000 ,12SSSSn则，
8、 ，满足要求 . 例8 给定正整数n，设fn是使 1 f n k k能被n整除的最小正整数 . 证明： 当且仅当n为 2 的幂时，有21fnn. 分析： 1 1 2 m k m m k ，因为 1 /, 2 m m n当21mn时， 1 m k kn/ ，所以21fnn. 则问题归结为： 证明： （1）当2m n时， 21 1 21 2 2 n k nn k . 当 1 1 21. 2 r k r r rnk时， 1 12 ,1212 2121 mm rrnrrn即， 11 2/1 ,2/ mm rr. 11 2/,/. 22 m r rr r n即 综上，知21fnn. （2）分析：2121
9、,fnnrn使 1 /, r k n k 即 1 / 2 r r n. （证明） 2 m n当时，令21. m na a为大于 的奇数此时需证 1 2/1 m a r r， 即证存在 1 2/ ,/1 m r ar即可. 构造同余方程组 1 02 1 m xmod xmoda （1） NO.* 7N0.* 由中国剩余定理知，同余方程组（1）有正整数解12rrn，则 1 2/ ,/1 m r ar. 从而有 1 2/1 m a r r，即 1 2/ 2 m r r a， 1 / 2 r r n. 考虑r的取值范围： 若2 ,020,rnrmodnrmoda则这与 1xmoda相矛盾，故2rn.
10、若 1 21,1212 m rnrmodnrmod则，这与 1 02 m xmod相矛盾 , 故21rn. 从而有12221rnn，于是得证21,rn使 1 / 2 r r n. 五、阶及应用 定理 1 设1, ,1nn aa n为整数，且，则必有一个r 1 r amodn. 证明： 011 , n aaa均与 n互质，所以有 0,0,1,1 i amodnin. 由抽屉原则，,01,i jijn满足使得 ji aamodn， 1 j i amodn， 令,11,1 r rjirnamodn则有. 定义 1： 设,1,1 m a namodnma则满足的最小正整数叫做 an对模 的阶. 注：若
11、anr对模 的阶为 ，则 NO.* 8N0.* 1 r amodn . 当11 i iramodn时，. 定理 2 设,1,1 m a nanramodn对模 的阶为若，则/.rm 证明：令 11 0mqrrrr，则 1111 q qrrrrrmqrr aaaaaaamodn. 而1 m amodn ，所以 1 1 r amodn .而anr对模 的阶为 的定 ,义 知 1 0r . 从而,/.mqrrm即 推论：若anr对模 的阶为 ，则 /rn. 特例：当n为素数 p时，/1rp. 例9 设1,/ 21,3 /. n nnn证明： 证明：显然n为奇数 . 假设3.pnp为 的最小素因数，下
12、证 / 21 n n， 210 n modn ，21 n modn ， 22 21,21 nn modnmodp. 设2/ 2 .prrn对模 的阶为 ，则 又由小费马定理知， 1 21 p modp， /1rp. 由，知，/ 2 ,1rn p. 2 /, n NO.* 9N0.* 2 2/2 ,1 ,2/ 2 ,1n pn p . 又若奇数/ 2 ,1 ,/,/1.qn pq n qp则 pn为 的最小奇素约数， 1q. 2 ,12.n p 由/ 2 ,1rn p，即/ 2,1rr及知2r. 由2pr对模 的阶为 ，知21 r modp，即 2 21 modp，从而 而pn为 的最小素因数，则/ ,3/p nn即.