0901-證明歐拉函數phi的積性

【寫在前面】

一個數若既與 m 互質又與 n 互質，那麼他便和 m*n 互質

完全剩餘系：一個整數的集合，對 m 取模後，餘數周遊了 0; 1; 2; 3; ……m 

歐拉函數：phi（n）-->不超過n且與n互質的整數的個數

特别的：phi（1）=1

現在我們需要證明phi（m*n ) = phi （m ）*phi（n） 【m，n互質】

這個矩陣裡列舉了從1到m*n的所有數，很容易發現第一行裡有phi（m）個與 m 互質的數，而一個數 r 若與 m 互質，則 k * m + r也與m互質，這是顯而易見的

然後看任意一列，可以得出結論任意一列都是 n 的完全剩餘系，（也就是說沒有兩個數他們對 n 取模後相等），那麼任意一列都有phi（n）個與n互質的數，那麼phi（n）*phi（m）便等于 phi（n*m）

是以為什麼 任意一列都是 n 的完全剩餘系呢？

首先我們假設有兩個數對n取餘後相等：k1*m+b = k2*m+b (mod n)，那麼我們可以改寫為k1*m+b = t1*n+r ; k2*m+b= t2*n+r,兩兩相減則： (k1-k2)m = (t1-t2)n，又因為m和n互質，是以m不能提供n的因數，那麼（k1-k2)就必然是n的倍數了，然後又因為k1和k2都是在0~n-1這個範圍裡的，是以任意兩個相減都不會産生n的倍數，那麼假設不成立，沒有兩個數對n取餘後相等，證畢

一個關于歐拉定理的證明