1. 首頁 > 生活百科 > >

怎么求公約數

公約數生活百科


怎么求公約數

文章插圖
最大公約數的求法一共有三種：
1、找查約數法：分別找出兩個數的所有約數 ， 再找出兩個數的所有公約數 ， 最大的那個就是最大公約數 。
2、更相減損法：任意兩個數 ， 判定是否為偶數 ， 是就用2約簡 ， 不是就用較大的數減較小的數 ， 所得的差和較小的數比較 ， 再用大的減小的 ， 直到所得的減數和差相等 ， 再用約掉的2的個數與所得的相等的數的乘積就是最大公約數 。
3、輾轉相除法：以小的數除大數 ， 所得的是整數 ， 那這個數就是最大公約數 ， 不然就用余數來除剛才的除數 ， 直到得到整數 ， 這時作為除數的就是最大公約數 。
最簡單的算公約數的方法叫做：輾轉相除法.
比如求145和25的公約數
先用145減去25的若干倍,使得減剩下的數比25小.也就是145-5乘以25=20.
然后只需要求25和20的公約數,重復上述過程：
【怎么求公約數】用25減去20的若干倍,使得減剩下的數比20小.也就是25-20=5.
然后只需要求20和5的公約數,顯然是5.
當然,還可以繼續一步,就是20-4乘以5=0.到0了,因為0不能做公約數,所以之前的那個5就是公約數.
這個原理很簡單,假設x和y的公約數是a,那么y,x都能被a整除,從而y-kx能被a整除,k是某個正整數.
于是a也是x與y-kx的公約數.因為越小的數,越容易看出來公約數,而y-kx比y小.

    推薦閱讀