逆元
その演算において、ある元
aに対し、別の元
bを作用させた時に、
単位元になるような元
例えば、
加算においては単位元は0
整数の元5に対して、加算すると0になるのは-5
なので5の加法逆元は-5
乗算においては単位元は1
整数の元5に対して、乗算すると1になるのは\frac{1}{5}
なので5の乗法逆元は\frac{1}{5}
aに対し、ay\equiv1\pmod Nとなる逆元yを求めたい
\mathrm{gcd}(N,a)=1なので、
(N,a)に
拡張ユークリッドの互除法を適用すると
Nx+ay=1となる2つの整数
(x,y)が得られる
このyが乗法逆元
ある元の逆元はその集合に2つ以上あることはない？
ある元の逆元がその元自身ということはある？