模反元素, 模逆元也称为模倒数, 一整数a, displaystyle, 對同餘n, displaystyle, 之是指滿足以下公式的整數b, displaystyle, displaystyle, equiv, pmod, 也可以寫成, displaystyle, equiv, pmod, 或者, displaystyle, 整数a, displaystyle, 對模数n, displaystyle, 之存在的充分必要條件是a, displaystyle, 和n, displaystyle, 互質, 若此存在, . 模逆元也称为模倒数 一整数a displaystyle a 對同餘n displaystyle n 之模反元素是指滿足以下公式的整數b displaystyle b a 1 b mod n displaystyle a 1 equiv b pmod n 也可以寫成 a b 1 mod n displaystyle ab equiv 1 pmod n 或者 a b mod n 1 displaystyle ab mod n 1 整数a displaystyle a 對模数n displaystyle n 之模反元素存在的充分必要條件是a displaystyle a 和n displaystyle n 互質 若此模反元素存在 在模数n displaystyle n 下的除法可以用和對應模反元素的乘法來達成 此概念和實數除法的概念相同 目录 1 求模反元素 1 1 用扩展欧几里得算法 1 1 1 若 UNIQ postMath 00000011 QINU 1 1 2 若 UNIQ postMath 0000001E QINU 1 2 用歐拉定理 2 举例求模反元素 编辑用扩展欧几里得算法 编辑 设e x g c d a n displaystyle mathrm exgcd a n 為扩展欧几里得算法的函数 則可得到a x n y g displaystyle ax ny g g displaystyle g 是a displaystyle a n displaystyle n 的最大公因数 若g 1 displaystyle g 1 编辑 则该模反元素存在 根據結果a x n y 1 displaystyle ax ny 1 在mod n displaystyle bmod n 之下 a x n y a x 1 displaystyle ax ny equiv ax equiv 1 根據模反元素的定義a a 1 1 displaystyle a cdot a 1 equiv 1 此時x displaystyle x 即為a displaystyle a 关于模n displaystyle n 的其中一個模反元素 事實上 x k n k Z displaystyle x kn k in mathbb Z 都是a displaystyle a 关于模n displaystyle n 的模反元素 這裡我們取最小的正整數解x mod n displaystyle x mod n x lt n displaystyle x lt n 若g 1 displaystyle g neq 1 编辑 则该模反元素不存在 因為根據結果a x n y 1 displaystyle ax ny neq 1 在mod n displaystyle bmod n 之下 a x g g lt n displaystyle ax equiv g g lt n 不會同餘於1 displaystyle 1 因此滿足a a 1 1 displaystyle a cdot a 1 equiv 1 的a 1 displaystyle a 1 不存在 用歐拉定理 编辑 歐拉定理證明當a n displaystyle a n 為兩個互質的正整數時 則有a f n 1 mod n displaystyle a varphi n equiv 1 pmod n 其中f n displaystyle varphi n 為歐拉函數 小於n displaystyle n 且與n displaystyle n 互質的正整數個數 上述結果可分解為a f n a a f n 1 1 mod n displaystyle a varphi n a cdot a varphi n 1 equiv 1 pmod n 其中a f n 1 displaystyle a varphi n 1 即為a displaystyle a 關於模n displaystyle n 之模反元素 举例 编辑求整数3对同余11的模逆元素x displaystyle x x 3 1 mod 11 displaystyle x equiv 3 1 pmod 11 上述方程可变换为 3 x 1 mod 11 displaystyle 3x equiv 1 pmod 11 在整数范围Z 11 displaystyle mathbb Z 11 内 可以找到满足该同余等式的x displaystyle x 值为4 如下式所示 3 4 12 1 mod 11 displaystyle 3 4 12 equiv 1 pmod 11 并且 在整数范围Z 11 displaystyle mathbb Z 11 内不存在其他满足此同余等式的值 故 整数3对同余11的模逆元素为4 一旦在整数范围Z 11 displaystyle mathbb Z 11 内找到3的模逆元素 其他在整数范围Z displaystyle mathbb Z 内满足此同余等式的模逆元素值便可很容易地写出 只需加上m 11 displaystyle m 11 的倍数便可 综上 所有整数3对同余11的模逆元素x可表示为 4 11 z z Z displaystyle 4 11 cdot z z in mathbb Z 即 18 7 4 15 26 这是一篇關於代数的小作品 你可以通过编辑或修订扩充其内容 查论编 这是一篇關於数论的小作品 你可以通过编辑或修订扩充其内容 查论编 取自 https zh wikipedia org w index php title 模反元素 amp oldid 76038307, 维基百科,wiki,书籍,书籍,图书馆,