最大公因數和素数

快捷方式: 差异，相似，杰卡德相似系数，参考。

最大公因數和素数之间的区别

最大公因數 vs. 素数

数学中，兩個或多個整數的最大公因數（greatest common factor，hcf）指能够整除这些整数的最大正整数（这些整数不能都为零）。例如8和12的最大公因数为4。最大公因数也称最大公约数（greatest common divisor，gcd）。 整数序列a的最大公因数可以記為(a_1, a_2, \dots, a_n)或\gcd(a_1, a_2, \dots, a_n)。 求兩個整數最大公因數主要的方法：. 質--數（Prime number），又称素--数，指在大於1的自然数中，除了1和該数自身外，無法被其他自然数整除的数（也可定義為只有1與該數本身两个正因数的数）。大於1的自然數若不是質數，則稱之為合數。例如，5是個質數，因為其正因數只有1與5。而6則是個合數，因為除了1與6外，2與3也是其正因數。算術基本定理確立了質數於數論裡的核心地位：任何大於1的整數均可被表示成一串唯一質數之乘積。為了確保該定理的唯一性，1被定義為不是質數，因為在因式分解中可以有任意多個1（如3、1×3、1×1×3等都是3的有效因數分解）。 古希臘數學家歐幾里得於公元前300年前後證明有無限多個質數存在（欧几里得定理）。現時人們已發現多種驗證質數的方法。其中試除法比較簡單，但需時較長：設被測試的自然數為n，使用此方法者需逐一測試2與\sqrt之間的整數，確保它們無一能整除n。對於較大或一些具特別形式（如梅森數）的自然數，人們通常使用較有效率的演算法測試其是否為質數（例如277232917-1是直至2017年底為止已知最大的梅森質數）。雖然人們仍未發現可以完全區別質數與合數的公式，但已建構了質數的分佈模式（亦即質數在大數時的統計模式）。19世紀晚期得到證明的質數定理指出：一個任意自然數n為質數的機率反比於其數位（或n的對數）。 許多有關質數的問題依然未解，如哥德巴赫猜想（每個大於2的偶數可表示成兩個素數之和）及孿生質數猜想（存在無窮多對相差2的質數）。這些問題促進了數論各個分支的發展，主要在於數字的解析或代數方面。質數被用於資訊科技裡的幾個程序中，如公鑰加密利用了難以將大數分解成其質因數之類的性質。質數亦在其他數學領域裡形成了各種廣義化的質數概念，主要出現在代數裡，如質元素及質理想。.

互質

互质（英文：coprime，符號：⊥，又稱互素、relatively prime、mutually prime、co-prime）。在數論中，如果兩個或兩個以上的整數的最大公因數是 1，則稱它們為互质。依此定義：.

互質和最大公因數 · 互質和素数 · 查看更多 »

余数

在算术中，当两个整数相除的结果不能以整数商表示时，余数便是其“餘留下的量”。当余数为零时，被称为整除。.

余数和最大公因數 · 余数和素数 · 查看更多 »

因數

因數是一個常見的數學名詞，又名「--」。.

因數和最大公因數 · 因數和素数 · 查看更多 »

除法

数学中，尤其是在基本计算裏，除法可以看成是「乘法的反运算」，也可以理解为「重复的减法」。除法运算的本质就是「把参与运算的除数变为1，得出被除数的值」。 例如：6 \div 3.

最大公因數和除法 · 素数和除法 · 查看更多 »

整数

整数，是序列中所有的数的统称，包括负整数、零（0）与正整数。和自然數一樣，整數也是一個可數的無限集合。這個集合在数学上通常表示粗體Z或\mathbb，源于德语单词Zahlen（意为“数”）的首字母。 在代數數論中，這些屬於有理數的一般整數會被稱為有理整數，用以和高斯整數等的概念加以區分。.

整数和最大公因數 · 整数和素数 · 查看更多 »