互素的學問

互素

互素 (Coprime 或 Relatively Prime)，是指兩數或以上的最大公因子 (G.C.D. Greatest Common Divisor) 為 1 。如 3 和 5 是互素，簡記 (3,5) = 1。

但是原來互素是不可傳遞的，即 (a, b) = 1 及 (b, c) = 1 不等於可以推論 (a, c) = 1，如 (2, 3) = (3, 4) = 1 但 (2, 4) = 2。

原來 n 和 n + 1 必定互素，因它們的最大公因子 d 必定要整除它們的差即 (n+1) - n = 1，所以最大公因子 d 只可為 1 ，即 n 和 n + 1 互素。

其實任何兩個不同的素數是永遠互素的，不單如此它們的次方數也世世代代互素下去。

還有 n!+1 和 (n+1)!+1 也必互素，因它們的最大公因子 d 必定要整除 (n+1)(n! + 1) - [(n+1)! + 1] = n，由此得 d 整除 n!。

即 d 整除 (n! + 1) - n! = 1。所以最大公因子 d 只可為 1 ，即 n!+1 和 (n+1)! + 1 互素。

　

圓周率的互素問題

順便一提，互素竟和圓周率 (Pi) 連上關係。

我們任意選取兩整數 m、n ，它們互素的機會率 P((m,n)=1) 為

　

若我們任意選取三整數 k、 m、n ，它們互素的機會率 P((k,m,n)=1)為

當中的 為黎曼 z 函數 (Riemann z Function)。關於黎曼 z 函數的知識，可參看另文《倒數和與素數積》。

　

參考文獻及網址：

Weisstein, E. W. "Relatively Prime." From MathWorld. http://mathworld.wolfram.com/RelativelyPrime.html.