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

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

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

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

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

5、?；ベ|的整數(shù)做成的.因xy分別歷遍模m1m2的完系時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是兩個互質的正整數(shù)則.)()()(2121mmmm????證明證明:因當xy分別歷遍模m1m2的既約剩余系時m2xm1y也歷遍模m1m2的既約剩余系即m2xm1y取遍個整數(shù)又x取遍個整數(shù)y取遍)(21mm?)(1m?個整數(shù)所以m2xm1y取遍個整數(shù)故.)(2m?)()(21mm??)()()(2121mmmm????推論推論2設整數(shù)n的標準分解式為(為互異素數(shù)kkpppn????2121?kpp1?)則有.1Nk????)11()