最大公因數- 維基百科

最大公因數（Highest Common Factor，簡寫H.C.F.；或者Greatest Common Divisor，簡寫G.C.D.），又叫最大公約數，係兩個或以上嘅整數入面嘅最大嗰個因數。

最大公因數 出自維基百科，自由嘅百科全書 跳去導覽 跳去搵嘢 最大公因數（HighestCommonFactor，簡寫H.C.F.；或者GreatestCommonDivisor，簡寫G.C.D.），又叫最大公約數，係兩個或以上嘅整數入面嘅最大嗰個因數。

譬如8同12嘅最大公因數係4。

喺數論入面，常用嘅叫法係GCD。

而兩個整數a、b既最大公因數會用 gcd ( a , b ) = d {\displaystyle\gcd(a,b)=d} 或者用 ( a , b ) = d {\displaystyle(a,b)=d} 嚟表達。

目錄 1定義 2性質 3搵公因數既方法 3.1輾轉相除法 3.2例出公因數 4應用 5求解相關定理 定義[編輯] 最大公因數嚴謹嘅數學定義需要用到可除性。

假設有兩個整數a、b，其中一個係唔等於零。

a、b嘅最大公因數 gcd ( a , b ) {\displaystyle\gcd(a,b)} 係一個整正數d，而d符合以下兩個條件： d | a , d | b {\displaystyled|a,d|b} 如果有另一個 d ′ {\displaystyled'} 符合條件一，上面講嘅d需要符合 d ′ < d {\displaystyled' 0 {\displaystylek>0} ，咁 gcd ( k a , k b ) = k × gcd ( a , b ) {\displaystyle\gcd(ka,kb)=k\times\gcd(a,b)} 。

如果 k {\displaystylek} 係一個整數，唔等於零，咁 gcd ( k a , k b ) = | k | gcd ( a , b ) {\displaystyle\gcd(ka,kb)=|k|\gcd(a,b)} 。

呢個 | k | {\displaystyle|k|} 係解絕對值。

證明： 假設 gcd ( a , b ) = d {\displaystyle\gcd(a,b)=d} ，得出 d | a , d | b {\displaystyled|a,d|b} 。

由 d | a {\displaystyled|a} ，代入 a = q b + r {\displaystylea=qb+r} ，得出 d | ( q b + r ) {\displaystyled|(qb+r)} 。

因為 d | b {\displaystyled|b} ，所以 d | q b {\displaystyled|qb} ，再由此可以推斷出 d | r {\displaystyled|r} 。

因為 r = a − q b {\displaystyler=a-qb} ，所以 gcd ( a , b ) = gcd ( b , r ) {\displaystyle\gcd(a,b)=\gcd(b,r)} 。

呢個性質可以用嚟證明輾轉相除法。

而其他兩個性質係需要用到輾轉相除法嚟證明。

搵公因數既方法[編輯] 搵公因數嘅方法有好多，其中一個就係輾轉相除法，不過重有幾個都係常用。

輾轉相除法 例出公因數 短除法 輾轉相除法[編輯] 內文：輾轉相除法 利用輾轉相除法去搵53同123嘅GCD。

123 = 53 × 2 + 17 {\displaystyle123=53\times2+17} 53 = 17 × 3 + 2 {\displaystyle53=17\times3+2} 17 = 2 × 8 + 1 {\displaystyle17=2\times8+1} 2 = 2 × 1 + 0 {\displaystyle2=2\times1+0} ∴ gcd ( 53 , 123 ) = 1 {\displaystyle\therefore\gcd(53,123)=1} 例出公因數[編輯] 例出所有公因數去搵12同8嘅GCD。

12 = 12 × 1 = 2 × 6 = 3 × 4 {\displaystyle{\begin{aligned}12&=12\times1\\&=2\times6\\&=3\times4\\\end{aligned}}} 8 = 8 × 1 = 2 × 4 {\displaystyle{\begin{aligned}8&=8\times1\\&=2\times4\\\end{aligned}}} ∴ gcd ( 8 , 12 ) = 4 {\displaystyle\therefore\gcd(8,12)=4} 應用[編輯] 公因數嘅概念可以喺數學上面證明好多有用嘅性質。

假設 n ∈ Z {\displaystylen\in\mathbb{Z}} 係整數，咁 gcd ( n , n + 1 ) = 1 {\displaystyle\gcd(n,n+1)=1} 。

假設 n ∈ Z {\displaystylen\in\mathbb{Z}} 係整數，咁 gcd ( n , n + 1 ) {\displaystyle\gcd(n,n+1)} 只可以係 1 {\displaystyle1} 或者 2 {\displaystyle2} 。

gcd ( gcd ( a , b ) , b ) = gcd ( a , b ) {\displaystyle\gcd(\gcd(a,b),b)=\gcd(a,b)} 。

如果 k = a b c + 1 {\displaystylek=abc+1} ，咁 gcd ( k , a ) = gcd ( k , b ) = gcd ( k , c ) = 1 {\displaystyle\gcd(k,a)=\gcd(k,b)=\gcd(k,c)=1} 。

如果 gcd ( a , b ) = d {\displaystyle\gcd(a,b)=d} ，咁 gcd ( a d , b d ) = 1 {\displaystyle\gcd{\bigl(}{\frac{a}{d}},{\frac{b}{d}}{\bigr)}=1} 。

如果一個整數係可以被 3 {\displaystyle3} 整除，咁佢嘅數字加埋一定係可以被 3 {\displaystyle3} 整除。

「 ⟺ {\displaystyle\iff} 」 求解相關定理[編輯] 輾轉相除法 相對質數 最小公倍數 比舒公式 歐幾理得推論 睇傾改數學基礎課題數學常識數論 數字 加法 減法 乘法 除法 四則運算 分數 分數四則混算 近似值 倍數 因數 最小公倍數及最大公因數 小數 小數分數互化 百分數 百分數小數分數互化 圖形與空間 柱體 錐體 球體 直線 曲線 圓形 多邊形 長方形 正方形 梯形 菱形 平行四邊形 三角形 角 直角 銳角 鈍角 方向 東 東南 南 西南 西 西北 北 東北 平行 垂直 圖形拉砌與分割 對稱 頂 棱 面 切面 圓 度量 長度 距離 單位 厘米 米 公里及英里 毫米 貨幣 硬幣 紙幣 時間 時 分 秒 年 月 日 星期 上午 下午 24小時制 重量 克 公斤 升 毫升 周界 圓周 面積 平方厘米 平方米 長方形 正方形 梯形 菱形 平行四邊形 三角形 體積 立方厘米 立方米 長方體 正方體 容量 速率 數據處理 象形圖 方塊圖 棒形圖 平均數 折線圖 代數學 代數學 方程 基本數學數同代數學 有向數同數線 數值估算 近似同誤差 有理數同無理數 百分比同應用 比率 代數應用 指數定律 線性方程 聯立方程 恆等式 公式 不等式 度量、圖形同空間 估計 面積 體積 幾何 全等同相似 直線嘅角 三角形嘅角 演繹幾何 畢氏定理 四邊形 坐標同幾何 三角比同應用 數據處理 統計學基本原則 圖表 集中趨勢 概率嘅簡單概念 導微積分基本方程概念 線性方程 二次方程 分數方程 不等式 變數 迴歸線性 函數圖像 函數 函數移位 組合函數 單對單函數 可逆函數 多項式 二次函數 多項式 多項式除法 多項式嘅根 虛根 代數基本定理 指數函數同對數 指數函數 指數定律 對數 對數定律 指數對數方程 三角比 弧度 三角比 正弦函數 餘弦函數 正切函數 正弦定理 餘弦定理 在實數入面嘅三角比函數 標準圓定義嘅三角比 正弦函數 餘弦函數 正切函數 反正弦函數 反餘弦函數 反正切函數 分析三角學 三角比公式 三角比之和同之差 雙角公式 半角公式 積和公式同和積公式 其他三角比公式 向量，虛數面同極坐標 向量 點積 虛數極三角比 虛數四則運算 極坐標 極坐標幾何 線性方程系統同線性編程 線性方程系統 矩陣 分開分數 幾何 拋物綫 橢圓 雙曲線 數列同數串 直加數列 倍加數列 睇傾改數論數論分支 抽象代數數論 分析數論 Geometricnumbertheory Computationalnumbertheory Transcendentalnumbertheory Combinatorialnumbertheory Arithmeticgeometry Arithmetictopology Arithmeticdynamics 數字概念 數字 自然數 質數 有理數 無理數 根數 Transcendentalnumber 質進數 Arithmetic Arithmeticfunction 基本概念 最大公因數 最小公倍數 可除性 相對質數 商餘及同餘 計算逆元素及極高次方 基本定理 餘數定理 輾轉相除法 比舒公式 歐幾理得推論 質數分解 商餘計算 線性商餘方程 孫子定理 歐拉定理 衛信定理 進階數論概念 始根 商餘平方 進階數論理論 Quadraticforms Modularforms L-functions Diophantineequations Diophantineapproximation 無窮分數 局部趨向 局部趨向數列 無窮分數趨向性 e嘅無窮分數 循環無窮分數 兩個平方之和 科馬兩個平方之和 Listofnumbertheorytopics (recreational) 由「https://zh-yue.wikipedia.org/w/index.php?title=最大公因數&oldid=1520655」收 屬於2類：數論算術 導覽選單 個人架生 未簽到同呢個互聯網地址嘅匿名人傾偈貢獻開戶口簽到 空間名 文章討論 變種 expanded collapsed 外觀 閱改睇返紀錄 多啲 expanded collapsed 查嘢 導覽 頭版目錄正嘢時人時事是但一版關於維基百科聯絡處捐畀維基百科 交流 說明書城市論壇社區大堂最近修改 架撐 有乜連過嚟連結頁嘅更改上載檔案專門版固定連結此版明細引用呢篇文維基數據項 打印/匯出 下載PDF印得嘅版本 第啲維基項目 維基同享 第啲話 AlemannischالعربيةAsturianuAzərbaycancaБеларускаяБългарскиবাংলাBosanskiCatalàکوردیČeštinaЧӑвашлаCymraegDanskDeutschΕλληνικάEnglishEsperantoEspañolEestiEuskaraفارسیSuomiFrançaisGalegoעבריתहिन्दीHrvatskiMagyarՀայերենBahasaIndonesiaIdoÍslenskaItaliano日本語Қазақшаಕನ್ನಡ한국어LugandaLombardLietuviųLatviešuമലയാളംМонголBahasaMelayuPlattdüütschNederlandsNorskbokmålଓଡ଼ିଆਪੰਜਾਬੀPolskiPiemontèisPortuguêsRomânăРусскийSrpskohrvatski/српскохрватскиසිංහලSimpleEnglishSlovenčinaSlovenščinaShqipСрпски/srpskiSvenskaதமிழ்తెలుగుไทยTagalogTürkçeТатарча/tatarçaУкраїнськаاردوTiếngViệt吴语ייִדיש中文 改拎