Closed No3371 closed 5 years ago
如果 p 是質數,無論任何自然數 n,一定能被 p 整除 (n的p次方與n同餘模p)
又因 ,當 n 本身不是 p 的倍數,也就是說,n 無法被 p 整除,那 麼 應該能夠被 p 整除
歐拉:當 m, n 互質 => 當 m 是質數的情況,因為 φ(m) = m - 1,將 m 代入:
費馬小定律 (Fermat's Little Theorem)
如果 p 是質數,無論任何自然數 n,一定能被 p 整除 (n的p次方與n同餘模p)
又因 ,當 n 本身不是 p 的倍數,也就是說,n 無法被 p 整除,那 麼 應該能夠被 p 整除
A與B沒有1以外的公因數,則A與B為互質數 (Coprime)
歐拉 (Euler's totient function)
歐拉定理在 m 是質數的情況下,就會成為費馬小定理
歐拉:當 m, n 互質 => 當 m 是質數的情況,因為 φ(m) = m - 1,將 m 代入: