페르마의 소정리

$$페르마의\;소정리\;$$

$$소수\;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)x\;가\;m의\;배수인데\;x\;는\;m\;과\;서로소이므로\;(a\;-\;b)\;가\;m의\;배수가\;된다.$$

$$이\;때,\;a\;와\;b\;는\;아래와\;같이\;표현\;가능하다.$$

$$a\;=\;mq_{a}\;+\;r_{a}$$

$$b\;=\;mq_{b}\;+\;r_{b}$$

$$(a\;-\;b)\;=\;(q_{a}\;-\;q_{b})m\;+\;(r_{a}\;-\;r_{b})$$

$$(a\;-\;b)가\;m\;의\;배수이므로,\;r_{a}와\;r_{b}\;가\;같다.$$

$$즉,\;a\;\equiv\;b\;(mod\;m)\;이\;성립한다.$$

$$보조정리를\;활용,\;a가\;p의\;배수가\;아닌\;경우$$

$$a^{p}\;\equiv\;a\;(mod\;p)$$

$$\Rightarrow\;a^{p-1}\;\equiv\;1\;(mod\;p)$$

$$페르마의\;소정리\;증명,\;귀납법$$

$$n\;=\;0\;인\;경우\;성립한다.$$

$$0^{p}\;=\;0$$

$$0^{p}\;\equiv\;0\;(mod\;p)$$

$$n\;=\;k\;인\;경우\;성립한다고\;가정하자.$$

$$이\;때,\;n\;=\;k+1\;인\;경우\;성립하는가?$$

$$(k+1)^{p}\;=\;\sum\limits_{n=0}^{p}{{p}\choose{n}}\;k^{n}\;=\;k^{p}\;+\;\sum\limits_{n=1}^{p-1}{{p}\choose{n}}\;k^{n}\;+\;1$$

$${{p}\choose{n}}\;=\;\frac{p\;(p\;-\;1)\;...\;(p\;-\;n\;-\;1)}{n\;(n\;-\;1)\;...\;1}$$

$${{p}\choose{n}}\;는\;1\;보다\;큰\;정수이며,\;p\;는소수이므로$$

$$0\;<\;n\;<\;p\;이면,\;{{p}\choose{n}}\;가\;p\alpha\;형태가\;된다.$$

$$(k+1)^{p}\;=\;k^{p}\;+\;(p\alpha_{1}k\;+\;p\alpha_{2}k^{2}\;+\;...\;+p\alpha_{p\;-\;1}k^{p-1})\;+\;1$$

$$이\;때,\;p로\;나누어\;떨어지는\;p\alpha_{i}k^{i}\;항은\;나머지\;값에\;영향을\;주지\;못한다.$$

$$즉,\;(k+1)^{p}\;\equiv\;k^{p}\;+\;1\;(mod\;p)\;가\;성립한다.$$

$$이\;때,\;n\;=\;k인\;경우에\;대해\;성립한다\;가정한\;상태이므로$$

$$k^{p}\;\equiv\;k\;(mod\;p)\;가\;성립한다.$$

$$그러므로,\;k^{p}\;+\;1\;\equiv\;k\;+\;1\;(mod\;p)\;도\;성립한다.$$

$$n\;=\;k\;일\;때\;성립한다\;가정하면,\;n\;=\;k\;+\;1\;일\;때도\;성립한다.$$

$$따라서,\;페르마의\;소정리는\;모든\;양의\;정수에\;대해\;성립한다.$$

참고 - 페르마의 소정리 - 나무위키