奧數(shù)講義數(shù)論專題：余數(shù)及同余

55華杯賽數(shù)論專題：余數(shù)及同余一、帶余除法的定義：（1）當(dāng)時：我們稱a可以被b整除，記作稱為a除以b的商或完全商一般地，如果a是整數(shù)，b是整數(shù)（b≠0）,若有a÷（1）當(dāng)時：我們稱a可以被b整除，記作稱為a除以b的商或完全商（2）當(dāng)時：我們稱（2）當(dāng)時：我們稱a不可以被b整除，記作，q稱為a除以b的商或不完二、同余的概念1的整數(shù)m除，所得的余數(shù)相同，就說這兩個整數(shù)對于除數(shù)m1的整數(shù)m那么這兩個整數(shù)對于除數(shù)ma和1的正整數(shù)，如果所得的余數(shù)相同，就說b對于模m同余，記作由于一個整數(shù)被m、、2m個數(shù)，所以全體整數(shù)可按被m除的余數(shù)分類，凡是余數(shù)相同的歸為一類，全體整數(shù)就被劃分成了m的任何兩數(shù)被m除的余數(shù)都相等，即同一類中任何兩數(shù)的差都能被m兩數(shù)被m三、同余的性質(zhì)如果那么ab對于模m是同余的，那么ab的差能被m（mod3則則則（mod（modm），a×c≡b×d（modm）.則。（其中n為正整數(shù)1708，43【答案】95【解答】根據(jù)被除數(shù)-余數(shù)=商×除數(shù)，可知，所求兩位數(shù)一定是707-43=665的大于43的約數(shù)，所以所求的兩位數(shù)是95.例2.數(shù)713、1103、830、947被一個數(shù)除所得余數(shù)相同（余數(shù)不為0），求這個除數(shù).而39，133.而947=156=2×13×3×2，39，133.例3.從1、2、…100中最多能選出多少個數(shù)，使選出的數(shù)中每兩個的和都不能被3整除？【答案】354.求7、2、…1003134、47、10100.除以32333132323114、、1010034.求7【解答】方法一：由于（143【解答】方法一：由于（14373），所以（77）而，（729而，（72971），所以.故75.6.5.的末三位數(shù)是多少？【解答】首先，僅考慮后三位數(shù)字，所求的數(shù)目相當(dāng)于5.的末三位數(shù)是多少？【解答】首先，僅考慮后三位數(shù)字，所求的數(shù)目相當(dāng)于的平方再乘以的末三位.其末三位為；然后來看前者.它是一個奇數(shù)的平方，設(shè)其為（k其末三位為；然后來看前者.它是一個奇數(shù)的平方，設(shè)其為（k為奇數(shù)），由于81，所以8數(shù)，則200，則，105，105，所以所求的末三例6.有2個三位數(shù)相乘的積是一個五位數(shù)，積的后四位是1031，第一個數(shù)各個位的數(shù)字之和是10，第二個數(shù)的各個位數(shù)字之和是8，求兩個三位數(shù)的和.【答案】360【解答】觀察條件僅給出了兩個乘數(shù)的數(shù)字之和，同時發(fā)現(xiàn)乘積的一部分已經(jīng)給出，即乘積的一部分數(shù)字之和已經(jīng)給出，我們可以采用棄九法原理的倒推來構(gòu)造出原三位數(shù)。因為這是一個一定正確的算式，所以一定可以滿足棄九法的條件，兩個三位數(shù)除以9的余數(shù)1898，那么□10319.□只能是3。將31031分解質(zhì)因數(shù)發(fā)現(xiàn)僅有一種情況可以滿足是兩個三位數(shù)的乘積，即.143217360。例7.三個連續(xù)的兩位數(shù)除以5的余數(shù)之和是7，除以7的余數(shù)之和是9，除以9的數(shù)之和是15.則這三個數(shù)除以11的余數(shù)之和是 .【答案】12【解答】三個連續(xù)的兩位數(shù)除以5的余數(shù)之和是7，那么只可能是3+4+0=7，所以第一個數(shù)被5除余3；同樣方法可以得出第一個兩位數(shù)除以7余2，除以9余4或者7.94，727×9-5=58531134512.97，535×9-2=435×9×2-2=8872100100的自然數(shù)x有個.8.定義、b中較大的數(shù)除以較小的數(shù)所得的余數(shù)，例如55【解答】如果x29，那么x295，29×1+5=34，29×2+5=63，29×3+5=92.如果x29，那么x29-5=245，68、12、24.所以滿足條件的數(shù)一共有7個.例9.一個自然數(shù)的7倍除以231所得的余數(shù)是28，它的11倍除以231所得的余數(shù)143，那么它的15倍除以231所得的余數(shù)是 .【答案】27【解答】33421231202，那么它的15倍除以231的余數(shù)是202×15÷231=13……27.方法二：注意到11×2-7=15，所以所求余數(shù)為143×2-28≡258≡27（mod231）.1063，90，13025個余數(shù)中最大的一個是多少？【答案】20【解答】因為63+90+130-25=258，所以除數(shù)一定是258的約數(shù).而258=2×3×43因為25÷3>8，說明至少有一個余數(shù)大于8，因此除數(shù)大于9.但又顯然小于63（否則它去除63的余數(shù)就是63），所以滿足要求的除數(shù)只可能是43，經(jīng)檢驗，它除63，90，130的余數(shù)分別是20，4，1，滿足要求.所求最大余數(shù)是20.例11.在小于1000的正整數(shù)中，分別除以18及33所得余數(shù)相同的數(shù)有多少個？【答案】9901718330~1710001833198396、594、、990017189900911717綜上所述共18×4+10+17=99個.12603，939，393A除甲數(shù)所得余數(shù)是A2AA2A【答案】17【解答】某數(shù)A除甲數(shù)所得余數(shù)是A除乙數(shù)所得余數(shù)的2倍，A除乙數(shù)所得余數(shù)是A除丙數(shù)所得余數(shù)的2倍，也即某數(shù)A除甲數(shù)與除乙數(shù)的2倍及丙數(shù)的4倍余數(shù)相同，939×2=1878，393×4=