>>155 つづき
”次の命題は定理5.6 からの直接の帰結である．
命題8.3 m を2 以上の自然数とする． 法m に関する剰余類が逆元もつためには，零因子でないことが必要十分である．
また，このような剰余類はm と互いに素な整数a によってa と表される．”

http://nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/
「代数入門」(2016)の資料 学習院大学理学部数学科・中野 伸 研究室
http://nakano.math.gakushuin.ac.jp/~shin/html-files/Algebra_Introduction/2016/05.pdf
「５　整数の合同」 最新版 09/12
(抜粋)
整数a, b の最大公約数が1 のとき，a, b は互いに素であるという． 次の命題は，法と互いに素な整数による割り算が可能なことを示している．
命題5.6 互いに素な整数a,m について次が成り立つ．
(1) a は法m に関して可逆である．
(2) b, c ∈ Z がab ≡ ac (mod m) をみたすならば，b ≡ c (mod m) が成り立つ．

証明
(1) gcd(a,m) = 1 よりax+my = 1 (x, y ∈ Z) と書けるが，
　これよりax−1 = −my はm の倍数，すなわちax ≡ 1 (mod m) であるからa は可逆である．
(2) ab ≡ ac (mod m) の両辺に，a の法m に関する逆元x を掛ければよい．

さて，a が法m に関して可逆ならば，逆元x を用いてax = 1 + my (y ∈ Z) と書けるが，このことは定理3.2 よりgcd(a,m) = 1 を意味する．
上の命題とあわせれば，法m に関するa の逆元が存在するためには，a,m が互いに素であることが必要十分であることがわかる．
式で書けば，gcd(a,m) = 1 ←→ ax ≡ 1 (mod m) をみたすx ∈ Z が存在する．
とくに，p が素数のときは，a ?≡ 0 (mod p) である任意の整数a に対して，法p に関する逆元が存在する．

一般に，gcd(a,m) = 1 のとき，ax にx = 1, 2, を順々に代入していってm で割った余りが1 になるものを探すことで，a の法m に関する逆元のひとつが求まる．
実際に，m ≦ 20 くらいならばこの方法は実用的である．
しかし，大きなm に対しては効率が悪い．
命題5.6 の証明をみると，ax + my = 1 (x, y ∈ Z) のとき，x がa の法m に関する逆元になっているので，ユークリッドの互除法を用いてx, y を求めれば効率よく計算できる．
(引用終り)