{"id":930,"date":"2020-09-16T18:56:26","date_gmt":"2020-09-16T18:56:26","guid":{"rendered":"http:\/\/localhost\/?page_id=930"},"modified":"2022-05-30T07:36:48","modified_gmt":"2022-05-30T10:36:48","slug":"o-pequeno-teorema-de-fermat","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/algebra-a\/o-pequeno-teorema-de-fermat\/","title":{"rendered":"O Pequeno Teorema de Fermat e o Teorema de Euler"},"content":{"rendered":"
Note que o lema acima pode ser expresso na estrutura $\\Z_p$ (onde $p$ \u00e9 primo). De fato, o lema \u00e9 equivalente a afirmar que Assuma agora que $p\\nmid a$. Como no par\u00e1grafo anterior, podemos assumir sem perder generalidade que $a\\in\\{1,\\ldots,p-1\\}$ (note que $a\\neq 0$ pela condi\u00e7\u00e3o que $p\\nmid a$). Em particular, $a$ \u00e9 invert\u00edvel m\u00f3dulo $p$; ou seja existe $b\\in\\{1,\\ldots,p-1\\}$ tal que $ab\\equiv 1\\pmod p$. Multiplicando a congru\u00eancia $\\bar a^p\\equiv a\\pmod p$ por $b$, obtemos que Note que o Teorema de Euler implica o Pequeno Teorema de Fermat (tomando $n=p$ primo e observando que $\\varphi(p)=p-1$), mas n\u00f3s decidimos deduzir o PTF de fatos mais elementares.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":" Seja $p$ um n\u00famero primo positivo e $a,b\\in\\Z$. Tem-se que \\[ (a+b)^p\\equiv a^p+b^p\\pmod p. \\] Exerc\u00edcio. Note que o lema acima pode ser expresso na estrutura $\\Z_p$ (onde $p$ \u00e9 primo). De fato, o lema \u00e9 equivalente a afirmar que \\[ (\\bar a+\\bar b)^p=\\bar a^p+\\bar b^p\\quad\\mbox{para todo}\\quad \\bar a,\\bar b\\in\\Z_p. \\] Este mesmo lema \u00e9 … Continue reading O Pequeno Teorema de Fermat e o Teorema de Euler<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":706,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/930"}],"collection":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/comments?post=930"}],"version-history":[{"count":12,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/930\/revisions"}],"predecessor-version":[{"id":1797,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/930\/revisions\/1797"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/706"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=930"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n\\[
\n(\\bar a+\\bar b)^p=\\bar a^p+\\bar b^p\\quad\\mbox{para todo}\\quad \\bar a,\\bar b\\in\\Z_p.
\n\\]
\nEste mesmo lema \u00e9 conhecido tamb\u00e9m como o Sonho do Calouro<\/a>.<\/p>\n
\nSe $p$ \u00e9 um primo positivo e $a\\in \\Z$, ent\u00e3o
\n\\begin{equation}\\label{eq:cong}
\na^p\\equiv a\\pmod p.
\n\\end{equation}
\nAl\u00e9m disso, se $p\\nmid a$, ent\u00e3o
\n\\[
\na^{p-1}\\equiv 1\\pmod p.
\n\\]\n<\/div>\n
\n\\[
\na^p=(1+\\cdots+1)^p\\equiv 1^p+\\cdots+1^p=1+\\cdots +1=a\\pmod p.
\n\\]
\nIsso mostra que a primeira afirma\u00e7\u00e3o \u00e9 v\u00e1lida.<\/p>\n
\n\\[
\na^{p-1}\\equiv (ba)a^{p-1}=ba^p\\equiv ba\\equiv 1\\pmod p.
\n\\]\n<\/p><\/div>\n
\n\\[
\n\\overline a^{-1}=\\overline a^{p-2}.
\n\\]\n<\/div>\n
\n\\[
\n1\\equiv a^{p-1}=a\\cdot a^{p-2}.
\n\\]
\nOra a defini\u00e7\u00e3o do inverso modular implica que $a^{p-2}$ \u00e9 um inverso de $a$ m\u00f3dulo $p$. A segunda afirma\u00e7\u00e3o segue imediatamente da primeira.\n<\/div>\n
\n\\[
\n\\Z_n^*=\\{\\overline a\\in\\Z_n\\mid\\mbox{$\\overline a$ \u00e9 invert\u00edvel}\\}.
\n\\]
\nDemonstre as seguintes propriedades de $\\Z_n^*$:<\/p>\n\n
\n\\[
\n\\mu_{\\overline a}:\\Z_n\\to \\Z_n,\\quad \\mu_{\\overline a}(\\overline b)=\\overline a\\overline b.
\n\\]
\nMostre que as seguinte afirma\u00e7\u00f5es s\u00e3o equivalentes:<\/p>\n\n
\n\\[
\na^{\\varphi(n)}\\equiv 1\\pmod n.
\n\\]
\nEquivalentemente
\n\\[
\n\\overline a^{\\varphi(n)}=\\overline 1.
\n\\]\n<\/div>\n
\nUsando o exerc\u00edcio imediatamente anterior a esse teorema, assuma que
\n\\[
\n\\Z_n^*=\\{\\overline a_1,\\overline a_2,\\ldots,\\overline a_{\\varphi(n)}\\}.
\n\\]
\nNote que $\\overline a\\in\\Z_n^*$, pois $\\mdc an=1$. Considere o conjunto
\n\\[
\n\\overline a\\Z_n^*=\\{\\overline a\\overline a_1,\\overline a\\overline a_2,\\ldots,\\overline a\\overline a_{\\varphi(n)}\\}
\n\\]
\nNote que todo elemento de $\\overline a\\Z_n^*$ est\u00e1 contido em $\\Z_n^*$ (exerc\u00edcio anterior) e se $i\\neq j$, ent\u00e3o $\\overline a\\overline a_i\\neq \\overline a\\overline a_j$. Portanto $\\overline a\\Z_n^*=\\Z_n^*$. Isso quer dizer que multiplicando os elementos de $\\Z_n^*$ e os elementos de $\\overline a \\Z_n^*$ n\u00f3s obtemos o mesmo elemento de $\\Z_n$. De fato
\n\\[
\n\\prod_{i=1}^{\\varphi(n)}{\\overline a_i}=\\prod_{i=1}^{\\varphi(n)}{\\overline a\\overline a_i}=\\overline a^{\\varphi(n)}\\prod_{i=1}^{\\varphi(n)}{\\overline a_i}.
\n\\]
\nOra, $\\prod {\\overline a_i}$ \u00e9 um elemento invert\u00edvel (primeiro exerc\u00edcio) e podemos multiplicar os dois lados da \u00faltima equa\u00e7\u00e3o acima com seu inverso. Fazendo isso, obtemos que
\n\\[
\n\\overline 1=\\overline a^{\\varphi(n)}.
\n\\]\n<\/div>\n