高中數(shù)學(xué)競賽——數(shù)論

1、1高中數(shù)學(xué)競賽高中數(shù)學(xué)競賽數(shù)論數(shù)論剩余類與剩余系剩余類與剩余系1.剩余類的定義與性質(zhì)剩余類的定義與性質(zhì)(1)定義定義1設(shè)m為正整數(shù)，把全體整數(shù)按對(duì)模m的余數(shù)分成m類，相應(yīng)m個(gè)集合記為：K0K1…Km1其中Kr=qmr|q∈Z0≤余數(shù)r≤m1稱為模m的一個(gè)剩余類剩余類(也叫同余類也叫同余類)。K0K1…Km1為模m的全部剩余類.(2)性質(zhì)性質(zhì)(ⅰ)且Ki∩Kj=φ(i≠j).imiKZ10?????(ⅱ)每一整數(shù)僅在K0K1…Km1一個(gè)里

2、.(ⅲ)對(duì)任意a、b∈Z，則a、b∈Kra≡b(modm).?2.剩余系的定義與性質(zhì)剩余系的定義與性質(zhì)(1)定義定義2設(shè)K0K1…Km1為模m的全部剩余類，從每個(gè)Kr里任取一個(gè)ar，得m個(gè)數(shù)a0a1…am1組成的數(shù)組，叫做模m的一個(gè)完全剩余系完全剩余系簡稱完系完系.特別地特別地012…m1叫做模叫做模m的最小非負(fù)完全剩余系的最小非負(fù)完全剩余系.下述數(shù)組叫做模叫做模m的絕的絕對(duì)最小完全剩余系對(duì)最小完全剩余系:當(dāng)m為奇數(shù)時(shí)為奇數(shù)時(shí)當(dāng)m為偶為

3、偶2110112121???????mmm??數(shù)時(shí)數(shù)時(shí)或.12101122?????mmm??210112mm?????(2)性質(zhì)性質(zhì)(ⅰ)m個(gè)整數(shù)構(gòu)成模m的一完全剩余系兩兩對(duì)模m不同余.?(ⅱ)若(am)=1，則x與axb同時(shí)遍歷模m的完全剩余系.證明證明:即證a0a1…am1與aa0baa1b…aam1b同為模m的完全剩余系因a0a1…am1為模m的完系時(shí)若aaib≡aajb(modm)則ai≡aj(modm)矛盾!反之當(dāng)aa0ba

4、a1b…aam1b為模m的完系時(shí)若ai≡aj(modm)則有aaib≡aajb(modm)也矛盾!3證明證明:因a1a2…aφ(m)是個(gè)與m互質(zhì)的整數(shù)并且兩兩對(duì)模m不同余)m(?所以a1a2…aφ(m)屬于個(gè)剩余類且每個(gè)剩余類都與m互質(zhì)故)m(?a1a2…aφ(m)是模m的一個(gè)既約剩余系.(ⅴ)設(shè)m1m2是兩個(gè)互質(zhì)的正整數(shù)而xy分別歷遍模m1m2的既約剩余系則m2xm1y歷遍模m1m2的既約剩余系.證明證明:顯然既約剩余系是完系中所有與

5、?；ベ|(zhì)的整數(shù)做成的.因xy分別歷遍模m1m2的完系時(shí)m2xm1y歷遍模m1m2的完系.由(m1x)=(m2y)=1(m1m2)=1得(m2xm1)=(m1ym2)=1所以(m2xm1ym1)=1(m2xm1ym2)=1故(m2xm1ym1m2)=1.反之若(m2xm1ym1m2)=1則(m2xm1ym1)=(m2xm1ym2)=1所以(m2xm1)=(m1ym2)=1因(m1m2)=1所以(m1x)=(m2y)=1.證畢.推論推論1若m

6、1m2是兩個(gè)互質(zhì)的正整數(shù)則.)()()(2121mmmm????證明證明:因當(dāng)xy分別歷遍模m1m2的既約剩余系時(shí)m2xm1y也歷遍模m1m2的既約剩余系即m2xm1y取遍個(gè)整數(shù)又x取遍個(gè)整數(shù)y取遍)(21mm?)(1m?個(gè)整數(shù)所以m2xm1y取遍個(gè)整數(shù)故.)(2m?)()(21mm??)()()(2121mmmm????推論推論2設(shè)整數(shù)n的標(biāo)準(zhǔn)分解式為(為互異素?cái)?shù)kkpppn????2121?kpp1?)則有.1Nk????)11()