1樓：
這個回答裡，真正的證明部分其實很少，大部分篇幅都是在引導思路，模擬「從零開始」的解題心路歷程，因此其中你已經知道的部分可以直接跳過。
首先，必要條件是顯然的，我們只看充分條件的部分，即「c被(a,b)整除」推出「ax+by=c有整數解」。因為abc都擁有(a,b)這一公因子，我們先約去這一項，得到Ax+By=C，其中(A,B)=1。原問題轉化為「(A,B)=1」推出「Ax+By=C有整數解」。
感覺題主可能是年齡比較小的學生，所以接下來我盡量詳細地一步步引導思路，關鍵結論用標出，如果覺得太顯然的話，可以跳過對應部分。
下面正式開始。我們現在除了問題以外一無所知，可以先取一組具體的數字代進去，看看有沒有什麼規律，或者說，尋找這個問題的本質是什麼。
比如3x+5y=19，我們可以先嘗試當y=0時，x的取值。x=6時，3x+5y=18；x=7時，3x+5y=21。顯然無法湊出19。
接著考慮加入乙個5，也就是y=1的情形。x=4時，3x+5y=17；x=5時，3x+5y=20，還是湊不出來。再試y=2的情形，發現x=3正好能使3x+5y=19，於是我們得到了方程的一組整數解。
回顧一下，我們不斷新增5的過程，起到了什麼作用呢？對，起到了為19÷3補齊餘數的作用。換句話說，調整y的取值，能夠幫助我們湊出C÷A的餘數。
為了表達簡潔，我們用mod符號表示餘數，例如19 mod 3 = 1表示19÷3的餘數等於1。
於是，我們找到了解這個方程的本質：尋找合適的y，使得 。同理，需要尋找合適的x，滿足 。
問題是，這樣的x和y一定存在嗎？因為這是證明題，所以答案必須是肯定的。接下來我們就來證明，從僅有的條件 ，能推出滿足條件的x和y一定存在。
二者是對稱的，我們還是先看y。考慮y=0, 1, 2,...，稍微動動腦就能發現， ，所以我們只需要考慮y=0, 1, ...
, A-1。而A的餘數恰恰也是這些，通過具體數字代入計算可以發現， 的值正好是A的餘數的某種排列，比如A=5, B=3時， 依次為0, 3, 1, 4, 2，正好不重不漏。這並不是巧合，利用簡單的反證法就可以證明：
若存在 ，使得 ，那麼 ，也就是說A能整除 。根據 ，B不包含A的任何因數，因此只能是 能被A整除。但是， 的取值範圍是 ，不可能被A整除，矛盾。
故y=0, 1, ..., A-1時， 不可能出現重複。
在餘數不能重複的情況下，取值只能是0, 1, ..., A-1的某種排列了。如果把 記為t，那麼這就是說，必然存在某個y，使得 。同理，必然存在x滿足 。
但這並不足以推出我們的最終目標：解出Ax+By=C。不過，通過上面的舉例和分析，我們也不難看出，我們並不需要考慮任意的C，而只需要考慮C=0, 1, 2, ...
, [A,B]-1。比如，當3x+4y=14時，3(x+4)+4y=26，3(x+8)+4y=38。這樣一來，最終的目標也可以相應變成：
當 時，必然存在一組x, y，使得 。因為 ，所以 。這個等式與我們上面已經證明的等式之間存在什麼關係呢？
還是回到那個例子：3x+5y=19，我們用現在已經知道的方法來重新試方程的解。因為19 mod 3 = 1，所以找到乙個y=2使得5y mod 3 = 1；因為19 mod 5 = 4，所以找到乙個x=3使得3x mod 5 = 4，組合起來得到x=3, y=2，正好是方程的乙個解，也就是說， 。
換個別的例子，最後同樣能發現，找到的x和y正好對應著方程的解。這是巧合嗎？為什麼「除以3餘1」和「除以5餘4」一定對應著「除以15餘4」呢？
還是那句話，因為這是證明題，所以我們可以肯定這並不是巧合。假如我們不是在做題，而是在自己探索數學規律，我們也可以先假定結論成立，然後再嘗試證明或者推翻這個結論。
不知道到這裡你能不能自己「感受」出來。我們的證明方法跟剛才的證明方法幾乎是一樣的。 可能的餘數是0, 1, ...
, AB-1，一共AB個。而A和B可能的餘數兩兩組合，也一共有AB種情況。我們還是要證明，A和B可能的餘數兩兩組合其實對應著AB餘數的某種排列。
假設A的不同餘數 和B的不同餘數 滿足
並且 。
但這是不可能的，因為 能推出 ，所以必須 。同理必須 。
所以，A和B餘數的不同組合必須對應於不同的AB餘數。
反過來也是成立的，AB的每乙個餘數也都對應著不同的A和B的餘數組合。這部分的證明和第乙個是類似的，你可以自己試一試。
所以，A和B可能的餘數兩兩組合就只能是對應著AB餘數的某種排列了。
到這裡，我們的目標其實已經達到了。回過頭來整理一下，我們通過觀察具體的例子，把證明過程分成了兩步：先是證明了從 能推出必然存在x, y滿足 。
接著，我們證明這一組 與 是互相對應的，也就是說，我們找到的x, y同時也滿足 。最後，我們只需要根據 與 的差值調整x的大小，就能得到方程 的一組解了。
兩步證明都是在尋找某兩組相同數量的數之間的相互對應（或者叫一一對映），從而同時得到解在餘數意義下的唯一性以及解的存在性。這兩組一一對映之所以成立，和我們唯一的已知條件 密不可分。你也可以想一想，如果沒有這個條件，那麼證明過程的哪些地方會出問題？
能自己想通的話，說明你對互素已經有初步的數感了。本科的代數結構課中會對相關的性質進行更加科學系統的研究，感興趣也可以提前了解一下XD，有些內容其實並不難懂。
2樓：guofuxi
常見的方法是用裴蜀定理，求出一組特解，再寫出通解公式 ，令每個未知數都取正整數，解不等式組，即可求出正整數解的組數。本人採取特殊的方法，用乙個未知數x表示另乙個未知數y，令其大於零，求出[c/a〕個整數，再利用整數中b的密度，乘以1/b,即易得公式，求非負整數解時，再加零解。
3樓：Septsea
Uninvited.
-> : clear. , => .
<- : If , this is clear, so let's assume that at least one of them is not zero. Let , and .
The equation is equivalent to
where . By Bézout's identity, there are integers such that
Hence the equation has a solution: .
怎麼證明整數與分數的數量相等
首先，每乙個整數自己就是有理數，所以有理數個數大於等於整數個數。其次，每乙個有理數都能寫成互質的p q，並能被對映 單射至乙個整數。所以整數的個數大於等於有理數個數。所以有理數個數等於整數個數。 Tastror 修改 建立有序數列 不妨寫成 使它對應整數 利用最簡分數的對映 就可以構造出乙個從有理數...
怎麼證明乙個正整數 a 的任意兩個因子的最小公倍數仍是 a 的因子？
目標當然就是證明公倍數一定是最小公倍數的整數倍這裡只需要注意到，如果a和b被m,n分別整除，那麼a b也被m,n分別整除 因此，根據數學歸納法，假設能夠取到最小的公倍數，使得它不是最小公倍數的整數倍，那麼它必然小於最小公倍數，否則它與最小公倍數的差將是更小的公倍數，並且無法被最小公倍數整除 然而這與...
怎麼證明由三種基本結構所構成的演算法可以解決任何複雜問題
已登出 這麼關鍵的問題沒多少人關注，那些程式設計師都幹嘛去了？我認為作為乙個與編寫程式有關工作的人，或者想要真正了解程式設計這門藝術的人，不搞清楚這個問題，Ta都只是個半吊子，根本就沒有試圖想要認真的去了解程式設計這門藝術的真諦。這裡雖然談不上證明，但我可以給出自己思考嚴密的邏輯要點。因為用很多方法...