Loading AI tools
来自维基百科,自由的百科全书
模逆元(Modular multiplicative inverse)也称为模倒数、数论倒数。
也可以写成
或者
整数对模数之模反元素存在的充分必要条件是和互质,若此模反元素存在,在模数下的除法可以用和对应模反元素的乘法来达成,此概念和实数除法的概念相同。
设为扩展欧几里得算法的函数,则可得到,是, 的最大公因数。
则该模反元素存在,根据结果
在之下,,根据模反元素的定义,此时即为关于模的其中一个模反元素。
事实上, 都是关于模的模反元素,这里我们取最小的正整数解()。
则该模反元素不存在。
因为根据结果,在 之下,不会同馀于,因此满足的不存在。
欧拉定理证明当为两个互质的正整数时,则有,其中为欧拉函数(小于且与互质的正整数个数)。
上述结果可分解为,其中即为关于模之模反元素。
求整数3对同余11的模逆元素,
上述方程可变换为
在整数范围内,可以找到满足该同余等式的值为4,如下式所示
并且,在整数范围内不存在其他满足此同余等式的值。
故,整数3对同余11的模逆元素为4。
一旦在整数范围内找到3的模逆元素,其他在整数范围 内满足此同余等式的模逆元素值便可很容易地写出——只需加上 的倍数便可。
综上,所有整数3对同余11的模逆元素x可表示为
即 {..., −18, −7, 4, 15, 26, ...}.
这是一篇关于代数的小作品。您可以通过编辑或修订扩充其内容。 |
这是一篇关于数论的小作品。您可以通过编辑或修订扩充其内容。 |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.