同余式和不定方程是數論中古老而富有魅力的內容.考慮數學競賽的需要,下面介紹有關的基本內容.
1. 同余式及其應用
定義:設a、b、m為整數（m＞0），若a和b被m除得的餘數相同，則稱a和b對模m同餘.記為或
一切整數n可以按照某個自然數m作為除數的餘數進行分類，即n=pm+r（r=0，1，…，m-1），恰好m個數類.於是同餘的概念可理解為,若對n1、n2，有n1=q1m+r，n2=q2m+r，那麼n1、n2
對模m的同餘，即它們用m除所得的餘數相等.
利用整數的剩餘類表示,可以證明同余式的下述簡單性質:
(1) 若,則m|(b-a).反過來,若m|(b-a),則;
(2) 如果a=km+b(k為整數),則;
(3) 每個整數恰與0,1,…，m-1，這m個整數中的某乙個對模m同餘；
(4) 同餘關係是一種等價關係：
① 反身性 ；
② 對稱性，則，反之亦然.
③ 傳遞性，，則；
（5）如果，，則
①； ②特別地
應用同余式的上述性質，可以解決許多有關整數的問題.
例1（2023年匈牙利奧林匹克競賽題）求使2n+1能被3整除的一切自然數n.
解∵ ∴ 則2n+1
∴當n為奇數時，2n+1能被3整除； 當n為偶數時，2n+1不能被3整除.
例2 求2999最後兩位數碼.
解考慮用100除2999所得的餘數
∵ ∴
又 ∴∴
∴2999的最後兩位數字為88.
例3 求證31980+41981能被5整除.
證明 ∵
∴∴ ∴
2．不定方程
不定方程的問題主要有兩大類：判斷不定方程有無整數解或解的個數；如果不定方程有整數解，採取正確的方法，求出全部整數解.
(1) 不定方程解的判定
如果方程的兩端對同乙個模m(常數)不同餘,顯然,這個方程必無整數解.而方程如有解則解必為奇數、偶數兩種，因而可以在奇偶性分析的基礎上應用同餘概念判定方程有無整數解.
例4 證明方程2x2-5y2=7無整數解.
證明 ∵2x2=5y2+7，顯然y為奇數.
① 若x為偶數，則
∴∵方程兩邊對同一整數8的餘數不等， ∴x不能為偶數.
②若x為奇數，則但5y2+7
∴x不能為奇數.因則原方程無整數解.
說明:用整數的整除性來判定方程有無整數解,是我們解答這類問題的常用方法.
例5 (第14屆美國數學邀請賽題)不存在整數x,y使方程
①證明如果有整數x，y使方程①成立，
則=知（2x+3y2）+5能被17整除.
設2x+3y=17n+a，其中a是0，±1，±2，±3，±4，±5，±6，±7，±8中的某個數，但是這時（2x+3y）2+5=（17n）2+34na+（a2+5）=a2+5（mod17），而a2+5被17整除得的餘數分別是5，6，9，14，4，13，7，3，1，即在任何情況下（2x+3y）2+5都不能被17整除，這與它能被17整除矛盾.故不存在整數x，y使①成立.
例7 （第33屆美國數學競賽題）滿足方程x2+y2=x3的正整數對（x，y）的個數是（ ）.
（a）0 （b）1（c）2（d）無限個（e）上述結論都不對
解由x2+y2=x3得y2=x2（x-1），
所以只要x-1為自然數的平方，則方程必有正整數解.令x-1=k2(k為自然數),則為方程的一組通解.由於自然數有無限多個,故滿足方程的正整數對(x,y)有無限多個,應選(d).
說明:可用寫出方程的一組通解的方法,判定方程有無數個解.
(2) 不定方程的解法
不定方程沒有統一的解法,常用的特殊方法有:配方法、因式（質因數）分解法、不等式法、奇偶分析法和餘數分析法.對方程進行適當的變形,並正確應用整數的性質是解不定方程的基本思路.
例6求方程的整數解.
解(配方法)原方程配方得(x-2y)2+y2=132.
在勾股數中,最大的乙個為13的只有一組即5,12,13,因此有8對整數的平方和等於132即(5,12),(12,5),(-5,-12),(-12,-5),(5-,12),(12,-5),(-5,12),(-12,5).故原方程組的解只能是下面的八個方程組的解
解得例7(原民主德國2023年中學生競賽題)已知兩個自然數b和c及素數a滿足方程a2+b2=c2.證明:這時有a＜b及b+1=c.
證明（因式分解法）∵a2+b2=c2， ∴a2=（c-b）（c+b），
又∵a為素數，∴c-b=1，且c+b=a2. 於是得c=b+1及a2=b+c=2b+1＜3b，
即＜.而a≥3,∴≤1，∴＜1.∴a＜b.
例9（第35屆美國中學數學競賽題）滿足聯立方程
的正整數（a，b，c）的組數是（ ）.
（a）0 （b）1 （c）2 （d）3 （e）4
解（質因數分解法）由方程ac+bc=23得 （a+b）c=23=1×23.
∵a，b，c為正整數，∴c=1且a+b=23.將c和a=23-b代入方程ab+bc=44得
(23-b)b+b=44,即(b-2)(b-22)=0,
∴b1=2,b2=22.從而得a1=21,a2=1.故滿足聯立方程的正整數組(a,b,c)有兩個,即(21,2,1)和(1,22,1),應選(c).
例10求不定方程2(x+y)=xy+7的整數解.
解由(y-2)x=2y-7,得
分離整數部分得由x為整數知y-2是3的因數,
∴y-2=±1，±3，∴x=3，5，±1. ∴方程整數解為
例11求方程x+y=x2-xy+y2的整數解.
解（不等式法）方程有整數解必須△=（y+1）2-4（y2-y）≥0，解得
≤y≤.
滿足這個不等式的整數只有y=0，1，2.
當y=0時，由原方程可得x=0或x=1；當y=1時，由原方程可得x=2或0；當y=2時，由原方程可得x=1或2.
所以方程有整數解
最後我們來看兩個分式和根式不定方程的例子.
例12求滿足方程且使y是最大的正整數解（x，y）.
解將原方程變形得
由此式可知，只有12-x是正的且最小時，y才能取大值.又12-x應是144的約數，所以，
12-x=1，x=11，這時y=132.
故滿足題設的方程的正整數解為 （x，y）=（11，132）.
例13（第35屆美國中學生數學競賽題）滿足0＜x＜y及的不同的整數對（x，y）的個數是（ ）.
（a）0 （b）1 （c）3 （d）4 （e）7
解法1 根據題意知，0＜x＜1984，由
得 當且僅當1984x是完全平方數時，y是整數.而1984=26·31，故當且僅當x具有31t2形式時，1984x是完全平方數.
∵x＜1984，∵1≤t≤7.當t=1，2，3時，得整數對分別為（31，1519）、（124，1116）和（279，775）.當t＞3時y≤x不合題意，因此不同的整數對的個數是3，故應選（c）.
解法2 ∵1984=∴由此可知：x必須具有31t2形式，y必須具有31k2形式，並且t+k=8（t，k均為正整數）.因為0＜x＜y，所以t＜k.
當t=1，k=7時得（31，1519）；t=2，k=6時得（124，1116）；當t=3，k=5時得（279，775）.因此不同整數對的個數為3.
競賽培訓專題4同余式與不定方程
同余式和不定方程是數論中古老而富有魅力的內容.考慮數學競賽的需要,下面介紹有關的基本內容.1.同余式及其應用 定義 設a b m為整數 m 0 若a和b被m除得的餘數相同，則稱a和b對模m同餘.記為或 一切整數n可以按照某個自然數m作為除數的餘數進行分類，即n pm r r 0，1，m 1 恰好m個...
競賽講座03同余式與不定方程
競賽講座03 同余式與不定方程 同余式和不定方程是數論中古老而富有魅力的內容.考慮數學競賽的需要,下面介紹有關的基本內容.1.同余式及其應用 定義 設a b m為整數 m 0 若a和b被m除得的餘數相同，則稱a和b對模m同餘.記為或 一切整數n可以按照某個自然數m作為除數的餘數進行分類，即n pm ...
初中數學競賽專題培訓 25 同余式
初中數學競賽專題培訓第二十五講 同余式 數論有它自己的代數，稱為同餘理論 最先引進同餘的概念與記號的是數學王子高斯 先看乙個遊戲 有n 1個空格排成一行，第一格中放入一枚棋子，甲乙兩人交替移動棋子，每步可前移1，2或3格，以先到最後一格者為勝 問是先走者勝還是後走者勝？應該怎樣走才能取勝？取勝之道是...