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

$$피보나치\;수\;구하기$$ $$F_0\;=\;F_1\;=\;1,\;F_{n+1}\;=\;F_n\;+\;F_{n-1},\;n\;\geq\;1$$ $$1,\;1,\;2,\;3,\;5,\;8\;....$$$$위와\;같은\;수열이\;피보나치\;수열이다.$$ $$f_0\;=\;0,\;f_1\;=\;1,\;f_{n+1}\;=\;f_n\;+\;f_{n-1},\;n\;\geq\;1$$ $$0,\;1,\;1,\;2,\;3,\;5,\;8\;....$$$$편의를\;위해\;0\;부터\;시작하기도\;한다.$$ $$f_k+1\;=\;F_k,\;k\;>\;0$$ $$n\;번째\;피보나치\;수\;f_n\;은\;어떻게\;구할까?$$ $$f_2\;=\;f_1\;+\;f_0$$$$f_3\;=\;f_2\;+\;f_1$$$$...$$$$..

$$나머지\;곱셈의\;역원$$ $$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\;나머지\;곱셈의\;역원을\..

$$페르마의\;소정리\;$$ $$소수\;p\;정수\;a\;에\;대해$$$$a^{p}\;\equiv\;a\;(mod\;p)$$ $$보조정리$$ $$정수\;a,\;b,\;x,\;m\;에\;대해\;m\;과\;x\;가\;서로소이면$$$$ax\;\equiv\;bx\;(mod\;m)$$$$\Rightarrow\;a\;\equiv\;b\;(\;mod\;m\;)$$ $$보조정리\;증명$$ $$ax\;\equiv\;bx\;(mod\;m)이면,\;아래와\;같이\;표현할\;수\;있다.$$ $$ax\;=\;mq_{ax}\;+\;r$$$$bx\;=\;mq_{bx}\;+\;r$$ $$ax\;-\;bx\;=\;(q_{a}\;-\;a_{b})m$$$$\Rightarrow\;(a\;-\;b)x\;=\;(q_{a}\;-\;q_{b})m..

$$유클리드\;호제법의\;확장$$ $$정수\;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..

$$유클리드\;호제법$$ $$유클리드\;호제법은\;영어로\;표기하면\;그냥\;Euclidean\;algorithm\;이다.$$$$두\;수를\;서로\;나누어\;최대공약수를\;구하는\;방법\;이다.$$ $$정리$$$$a, b\;가\;정수일\;때\;a를\;b로\;나눈\;나머지를\;r이라고\;하자\;( a \le b,\;0 \le r \le b)$$$$a와\;b의\;최대공약수를\;(a,b)라고\;하면,\;다음이\;성립한다.$$$$(a,b)\;=\;(b,r)$$ $$예시$$$$(1071,1029)\;=\;(1029,42)\;=\;(42,21)\;=\;(21,0)\;=\;21$$$$b,r이\;새로운\;a,b가\;되어\;(a,b)=(b,r)\;을\;반복한다$$ $$증명$$$$a,b\;가\;정수이고,\;a \ge b\..