1樓：匿名使用者
為什麼除數和餘數的最大公約數就是被除數和除數的最大設a、b為正整數，且a＞b，a=bq＋r，q、r也為正整數，且0＜r＜b；這裡，a為被除數、b為除數、q為商、r為餘數；
設a與b的最大公約數為d，即(a，b)=d，試證(b，r)=(a，b)=d；
證明:由於(a，b)=d，
所以可設a=md、b=nd，m、n為正整數，且(m，n)=1；
r=a-qb=md-qnd=d(m-qn)，所以d能整除r，即d|r；
由於d|b，
所以d|(b，r)①；
假設(b，r)=d＞d②，
則d|(bq＋r)，即d|a，
所以d|(a，b)，
所以d≦(a，b)，即d≦d，這和②矛盾！
結合①可知(b，r)=d，即(b，r)=(a，b)。
輾轉相除法是求最大公約數和最小公倍數的另一種方法。
具體做法是：用較小數除較大數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反覆，直到最後餘數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。
把這些數相乘就是最小公倍數。
2樓：皇甫蘭英曹璧
設a、b為正整數，且a＞b，a=bq＋r，q、r也為正整數，且0＜r＜b；這裡，a為被除數、b為除數、q為商、r為餘數；設a與b的最大公約數為d，即(a，b)=d，試證(b，r)=(a，b)=d；證明:由於(a，b)=d，所以可設a=md、b=nd，m、n為正整數，且(m，n)=1；r=a-qb=md-qnd=d(m-qn)，所以d能整除r，即d|r；由於d|b，所以d|(b，r)①；假設(b，r)=d＞d②，則d|(bq＋r)，即d|a，所以d|(a，b)，所以d≦(a，b)，即d≦d，這和②矛盾！結合①可知(b，r)=d，即(b，r)=(a，b)。
3樓：匿名使用者
在有餘數的除法裡，如果被除數和除數都能被同一個數整除，那麼餘數也能被這個數整除。反過來除數和餘數都能被同一個數整除，那麼被除數也能被這個數整除。也就是被除數與除數的一切公約數也都是除數與餘數的公約數，當然它們的最大公約數也一定相同。
所以，被除數除以除數，如果商不等於零，那麼這個數的最大公約數就是除數與餘數的最大公約數。
4樓：匿名使用者
這個可以用反證法證明。我試著證明一下。
設被除數a，除數b，商c，餘數d，a、b的最大公約數是e，a、b、c、d、e都是整數
那麼有a÷b=c…………d。這樣可以得到等式a=b×c+d那麼因為e是a、b的公約數，所以e是a和b的約數，因為a是e的倍數，b是e的倍數，那麼b×c也是e的倍數，這樣d=a-b×c是兩個e的倍數相減，所以也是e的倍數。因此e也是b、d的公約數。
再證明e是b、d的最大公約數。用反證法。
設還有一個數x>e也是b、d的公約數。那麼a=b×c+d也是x的倍數，那麼x也是a、b的公約數，因為x>e，這與e是a、b的最大公約數的設定矛盾，這說明不存在比e更大的b、d的公約數，所以e就是b、d的最大公約數。
5樓：匿名使用者
這是一個得到證明的定理。
為什麼除數和餘數的最大公約數就是被除數和除數的最大
6樓：匿名使用者
為什麼除數和餘數的最大公約數就是被除數和除數的最大設a、b為正整數，且a＞b，a=bq＋r，q、r也為正整數，且0＜r＜b；這裡，a為被除數、b為除數、q為商、r為餘數；
設a與b的最大公約數為d，即(a，b)=d，試證(b，r)=(a，b)=d；
證明:由於(a，b)=d，
所以可設a=md、b=nd，m、n為正整數，且(m，n)=1；
r=a-qb=md-qnd=d(m-qn)，所以d能整除r，即d|r；
由於d|b，
所以d|(b，r)①；
假設(b，r)=d＞d②，
則d|(bq＋r)，即d|a，
所以d|(a，b)，
所以d≦(a，b)，即d≦d，這和②矛盾！
結合①可知(b，r)=d，即(b，r)=(a，b)。
輾轉相除法是求最大公約數和最小公倍數的另一種方法。
具體做法是：用較小數除較大數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反覆，直到最後餘數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。
把這些數相乘就是最小公倍數。
為什麼輾轉相除法中的「大數除以小數所得的餘數，與小數的最大公約數，等於原來兩數的最大公約數」 10
7樓：匿名使用者
高二應該有能力證明這個定理啊……
設x=am，y=bm，其中m是x和y的最大公約數。
x＝cbm+d＝am
則(a-cd)m＝d
所以m也是d的公約數。
什麼是最大公約數，什麼叫做最大公約數？
最大公因數，也稱最大公約數 最大公因子，指兩個或多個整數共有約數中最大的一個 能整除這個數的最大數 什麼叫做最大公約數？最大公因數，也稱最大公約數 最大公因子，指兩個或多個整數共有約數中最大的一個。a，b的最大公約數記為 a，b 同樣的，a，b，c的最大公約數記為 a，b，c 多個整數的最大公約數也...
求最大公約數的方法及原理
方法bai du一 短除法 把兩個數一直除以zhi它們的公約數 dao,取它們的商回繼續除答 直到無約數可除為止。然後把約數全部乘起來,即為最大公約數。例 求12與48的最大公約數。解 所以12和48的最大公約數是 2 2 3 12方法二 歐幾里德演算法 輾轉相除法 在兩個數中,找出大數。用大數除以...
利用fun函式,求m和n的最大公約數
演算法叫輾轉相除法 例如求m,n的最大公約數 m n p.q p是m n的商，q是m n就是m除以n的餘數。然後在讓 m n n q 在作上面的迴圈 m n p.q 如果n為0，則m就是所求的最大公約數。另外題目還利用了一個性質，就是最大公約數 最小公倍數 m n 所以最後才有 printf d d...