나머지 곱셈의 역원

$$나머지\;곱셈의\;역원$$

$$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}$$

참고 - 나머지 곱셈의 역원