最大公因數 最大公因數英語highest common factorhcf也稱最大公約數英語greatest common divisorgcd是數學詞彙指能够整除多個非零整數的最大正整数例如和的最大公因数为 整数序列 a displaystyle a 的最大公因数可以記為  a   a     a n  displaystyle aadots an 或 gcd  a   a     a n  displaystyle gcdaadots an  最大公因数的值至少為例如 gcd        displaystyle gcd 最大則為該組整數中絕對值最小的絕對值例如 gcd        displaystyle gcd 和 gcd         displaystyle gcd  求兩個整數最大公因數主要的方法 列舉法分別列出兩整數的所有因數並找出最大的公因數 質因數分解分別列出兩數的質因數分解式並計算共同項的乘積 短除法兩數除以其共同質因數直到兩數互質時所有除數的乘積即為最大公因數 兩個整數 a  b displaystyle ab 的最大公因數和最小公倍數lcm的關係為 gcd  a  b  lcm   a  b    a b  displaystyle gcdaboperatorname lcm abab 兩個整數的最大公因數可用於計算兩數的最小公倍數或分數化簡成最簡分數 兩個整數的最大公因數和最小公倍數中存在分配律 gcd  a  lcm   b  c    lcm   gcd  a  b   gcd  a  c   displaystyle gcdaoperatorname lcm bcoperatorname lcm gcdabgcdac lcm   a  gcd  b  c    gcd  lcm   a  b   lcm   a  c   displaystyle operatorname lcm agcdbcgcdoperatorname lcm aboperatorname lcm ac 在直角坐標中兩頂點為        a  b  displaystyle ab 的線段會通過 gcd  a  b    displaystyle gcdab 個格子點