五、模反元素

還剩下最后一個(gè)概念：

如果兩個(gè)正整數(shù)a和n互質(zhì)，那么一定可以找到整數(shù)b，使得 ab-1 被n整除，或者說ab被n除的余數(shù)是1。

這時(shí)，b就叫做a的"模反元素"。

比如，3和11互質(zhì)，那么3的模反元素就是4，因?yàn)?(3 × 4)-1 可以被11整除。顯然，模反元素不止一個(gè)， 4加減11的整數(shù)倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，則 b+kn 都是a的模反元素。

歐拉定理可以用來證明模反元素必然存在。

可以看到，a的 φ(n)-1 次方，就是a的模反元素。

==========================================

好了，需要用到的數(shù)學(xué)工具，全部介紹完了。RSA算法涉及的數(shù)學(xué)知識，就是上面這些，下一次我就來介紹公鑰和私鑰到底是怎么生成的。