互質(互素)

互質

互素一般指本詞條

互質是公約數只有1的兩個整數,叫做互質整數。公約數只有1的兩個自然數,叫做互質自然數,後者是前者的特殊情形

基本介紹

  • 中文名:互質
  • 外文名:relatively prime
  • 別稱互素
  • 表達式:(c,m)=1
  • 套用學科:數學
  • 套用領域:計算機
定義,判別方法,程式語言實現,C語言,Java語言,

定義

互質,若N個整數的最大公因數是1,則稱這N個整數互質。
互質
例如8,10的最大公因數是2,不是1,因此不是整數互質。
7,11,13的最大公因數是1,因此這是整數互質。
5和5不互質,因為5和5的公因數有1、5。
1和任何數都成倍數關係,但和任何數都互質。因為1的因數只有1,而互質數的原則是:只要兩數的公因數只有1時,就說兩數是互質數。因為1隻有一個因數所以1既不是質數(素數),也不是合數,無法再找到1和其他數的別的公因數了。1和-1與所有整數互素,而且它們是唯一與0互素的整數。
互質數的寫法:如c與m互質,則寫作(c,m)=1。
國小數學教材對互質數是這樣定義的:“公約數只有1的兩個數,叫做互質數。”
這裡所說的“兩個數”是指自然數
“公約數只有 1”,不能誤說成“沒有公約數。”
這裡有一個誤區,認為0不與任何數互質。嚴格地按照互質的定義來看0與1,-1均互質,通過任意有理數的表示方式a/b(a,b互質且b為正整數),同樣可以得出0與1,-1均必須互質,否則0不是有理數。

判別方法

(1)兩個不同的質數一定是互質數
例如,2與7、13與19。
(2)一個質數,另一個不為它的倍數,這兩個數為互質數。
例如,3與10、5與 26。
(3)1不是質數也不是合數,它和任何一個自然數(1本身除外)在一起都是互質數。如1和9908。
(4)相鄰的兩個自然數是互質數。如 15與 16。
(5)相鄰的兩個奇數是互質數。如 49與 51。
(6)較大數是質數的兩個數是互質數。如97與88。
(7)兩個數都是合數(二數差又較大),較小數所有的質因數,都不是較大數的約數,這兩個數是互質數。
如357與715,357=3×7×17,而3、7和17都不是715的約數,這兩個數為互質數。
(8)兩個數都是合數(二數差較小),這兩個數的差的所有質因數都不是較小數的約數,這兩個數是互質數。如85和78。85-78=7,7不是78的約數,這兩個數是互質數。
(9)兩個數都是合數,較大數除以較小數的餘數(不為“0”且大於“ 1”)的所有質因數,都不是較小數的約數,這兩個數是互質數。如 462與 221
462÷221=2……20,
20=2×2×5。
2、5都不是221的約數,這兩個數是互質數。
(10)減除法。如255與182。
255-182=73,觀察知 73182。
182-(73×2)=36,顯然 3673。
73-(36×2)=1,
(255,182)=1。
所以這兩個數是互質數。
三個或三個以上自然數互質有兩種不同的情況:一種是這些成互質數的自然數是兩兩互質的。如2、3、5。另一種不是兩兩互質的。如6、8、9。

程式語言實現

C語言

int gcd(int a,int b){    if(b==0)        return a;    else         return gcd(b,a%b);} //遞歸法求最大公約數,當最大公約數是1的時候,兩個數互質
if(gcd(x,y)==1)那么x,y互質

Java語言

public int gcd(int a, int b) {            if(a<b){                    swap(a,b);    }           if(b==0)        return a;            else        return gcd(b,a%b);    }

相關詞條

熱門詞條

聯絡我們