오늘 걷지 않으면 내일 뛰어야 합니다

$$나머지\;곱셈의\;역원$$ $$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)\;라고\;하자.$$$$이\;때,\;아래\;형태의\;해가\;되는\;정수쌍\;x\;와\;y\;를\;구할\;수\;있다.$$ $$ax\;+\;by\;=\;(a,b)$$ $$유클리드\;호제법의\;과정을\;나열하면\;아래와\;같다.$$ $$a\;=\;bq_{1}\;+\;r_{2}$$$$b\;=\;r_{2}q_{2}\;+\;r_{3}$$$$r_{2}\;=\;r_{3}q_{3}\;+\;r_{4}$$$$...$$$$r_{n-1}\;=\;r_{n}q_{n}\;+\;r_{n+1}$$$$r_{n}\;=\;r_{n+1}q_{n+1}\;+\;r_{n+2}$$$$r_{n+1}\;=\;r_{n+2}q_{n+2}\;+\;0$$ $$나머지가\;0..