나머지 곱셈의 역원
$$나머지\;곱셈의\;역원$$
$$a\;\times\;a^{-1}\;=\;1$$
$$a^{-1}\;를\;a\;의\;곱셈의\;역원이라고\;한다.$$
$$a\;\times\;a^{-1}\;\equiv\;1\;(mod\;m)$$
$$a^{-1}\;를\;a\;의\;m\;나머지\;곱셈의\;역원이라고\;한다.$$
$$역원을\;구하는\;방법$$
$$1.\;유클리드\;호제법의\;확장\;활용$$
$$a\;와\;b\;의\;최대공약수를\;(a,b)\;라\;할\;때$$
$$ax\;+\;by\;=\;(a,b)$$
$$위\;식을\;만족시키는\;정수쌍\;x\;와\;y\;를\;구할\;수\;있다.$$
$$a\;와\;b\;가\;서로소인\;경우\;a\;의\;b\;나머지\;곱셈의\;역원을\;구할\;수\;있다.$$
$$a\;와\;b\;가\;서로소면,\;(a,b)\;=\;1\;이다.$$
$$ax\;+\;by\;=\;1$$
$$위\;식을\;만족하는\;정수쌍\;x,\;y$$
$$유클리드\;호제법의\;확장으로\;구할\;수\;있다.$$
$$이\;때,\;(ax\;+\;by)\;\equiv\;ax\;(mod\;b)\;이다.$$
$$ax\;\equiv\;1\;(mod\;b)\;가\;되므로$$
$$ax\;+\;by\;=\;1\;을\;만족하는\;정수쌍\;x,\;y\;는\;각각$$
$$a\;\times\;a^{-1}\;\equiv\;1\;(mod\;b),\;a^{-1}\;=\;x$$
$$b\;\times\;b^{-1}\;\equiv\;1\;(mod\;a),\;b^{-1}\;=\;y$$
$$단,\;x\;와\;y\;는\;음수가\;될\;수\;있다.$$
$$양수를\;구하고\;싶다면?$$
$$a\;=\;bq_{a}\;+\;r_{a}$$
$$x\;=\;bq_{x}\;+\;r_{x}$$
$$\begin{align}ax\;&=\;(bq_{a}\;+\;r_{a})(bq_{x}\;+\;r_{x})\\&=\;(bq_{a}\;bq_{b})\;+\;(r_{x}\;bq_{a})\;+\;(r_{a}\;bq_{x})\;+\;(r_{a}\;r_{x})\\&=\;b(b\;q_{a}\;q_{b}\;+\;r_{x}q_{a}\;+\;r_{a}\;q_{x})\;+\;r_{a}\;r_{x}\\&=\;bQ\;+r_{a}\;r_{x}\end{align}$$
$$ax\;\equiv\;r_{a}\;r_{x}\;(mod\;b)$$
$$ax\;의\;b로\;나눈\;나머지는\;a\;와\;x\;각각\;b\;로\;나눈\;나머지의\;영향을\;받는다.$$
$$(x\;+\;b)\;=\;b(q_{x}\;+\;1)\;+\;r_{x}$$
$$b\;(몫)\;를\;더하는\;연산은\;나머지에\;영향을\;주지\;않으므로\;$$
$$ax\;\equiv\;a(x\;+\;b)\equiv\;a(x\;+\;2b)\;\equiv\;...\;\equiv\;(x\;+\;ib)\;\equiv\;1\;(mod\;b)$$
$$그러므로\;양수가\;될\;때까지\;몫을\;더해주면\;양수인\;나머지\;곱셈의\;역원을\;얻을\;수\;있다.$$
$$2.\;페르마의\;소정리\;활용$$
$$p\;가\;소수일\;때,\;a^{p}\;\equiv\;a\;(mod\;p)$$
$$보조정리를\;활용하면$$
$$a^{p-1}\;\equiv\;1\;(mod\;p)$$
$$a^{p-1}\;=\;a\;a^{p-2}\;이므로,\;a\;의\;p\;나머지\;곱셈의\;역원은\;a^{p-2}\;이다.$$
$$a\;a^{-1}\;\equiv\;a\;a^{p-2}\;\equiv\;a^{p-1}\;\equiv\;1\;(mod\;p)$$
$$a^{-1}\;=\;a^{p-2}$$
참고 - 나머지 곱셈의 역원