{"id":1492,"date":"2021-12-12T08:45:21","date_gmt":"2021-12-12T11:45:21","guid":{"rendered":"http:\/\/localhost\/?page_id=1492"},"modified":"2023-01-06T14:48:56","modified_gmt":"2023-01-06T17:48:56","slug":"numeros-de-carmichael-e-o-teste-de-primalidade-de-miller","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/numeros-de-carmichael-e-o-teste-de-primalidade-de-miller\/","title":{"rendered":"N\u00fameros de Carmichael"},"content":{"rendered":"
\nSeja $n$ um n\u00famero natural com $n\\geq 5$ e seja $a\\in\\{2,\\ldots,n-1\\}$. Lembre que $n$ \u00e9 dito pseudoprimo na base $a$ se $a^{n-1}\\equiv 1\\pmod n$. Observe que se $n$ for pseudoprimo na base $a$, ent\u00e3o $a^n\\equiv a\\pmod n$.<\/p>\n
\nUm n\u00famero composto $n$ \u00e9 dito n\u00famero de Carmichael se $a^n\\equiv a\\pmod n$ para todo $a\\in\\{1,\\ldots,n-1\\}$.<\/div>\n
\nMostre que um n\u00famero de Carmichael \u00e9 \u00edmpar.<\/div>\n

N\u00fameros de Carmichael s\u00e3o os mais prov\u00e1veis de passarem no teste de primalidade de Fermat, pois se $n$ \u00e9 de Carmichael, ent\u00e3o $b^{n-1}\\equiv 1\\pmod n$ vale para qualquer base $b$ coprimo com $n$. Ou seja, $n$ ser\u00e1 pseudoprimo para muitas bases.<\/p>\n

O menor n\u00famero de Carmichael \u00e9 561. Usando a defini\u00e7\u00e3o de n\u00fameros de Carmichael, este fato n\u00e3o \u00e9 f\u00e1cil de verificar sem usar um computador. No entanto, a verifica\u00e7\u00e3o pode ser feita sabendo que
\n\\[
\n561=3\\cdot 11\\cdot 17.
\n\\]
\nSeja $b\\in\\{1,\\ldots,560\\}$ arbitr\u00e1rio. N\u00f3s vamos mostrar que $b^{561}\\equiv b\\pmod{561}$. Esta congru\u00eancia \u00e9 equivalente ao fato que $561\\mid (b^{561}-b)$. Para provar esta divisibilidade, basta verificar que $3$, $11$, e $17$ s\u00e3o divisores de $b^{561}-b$ para todo $b\\in\\{1,\\ldots,560\\}$.<\/p>\n

Primeiro tratamos a afirma\u00e7\u00e3o que $17\\mid (b^{561}-b)$; ou seja
\n\\[
\nb^{561}\\equiv b\\pmod {17}.
\n\\]
\nSe $17\\mid b$, ent\u00e3o os dois lados da congru\u00eancia s\u00e3o congruentes com zero, ent\u00e3o n\u00e3o h\u00e1 nada para fazer. Assuma que $17\\nmid b$. Neste caso, o Pequeno Teorema de Fermat d\u00e1 que $b^{16}\\equiv 1\\pmod{17}$ e isso implica que
\n\\[
\nb^{560}=(b^{16})^{35}\\equiv 1\\pmod{17}.
\n\\]
\nObtemos assim que $b^{561}\\equiv b\\pmod{17}$ ou seja $17\\mid( b^{561}-b)$.<\/p>\n

Notando que $560=561-1$ \u00e9 divis\u00edvel por $3-1=2$ e por $11-1=10$, as divisibilidades $3\\mid (b^{561}-b)$ e $11\\mid (p^{561}-b)$ podem ser verificadas similarmente.<\/p>\n

Observe que na conta acima os fatos cruciais sobre o n\u00famero 561 foram os seguintes:<\/p>\n

    \n
  1. o n\u00famero 561 \u00e9 livre de quadrado; ou seja, ele n\u00e3o \u00e9 divis\u00edvel por $p^2$ para nenhum primo $p$;<\/li>\n
  2. se $p$ divide 561, ent\u00e3o $p-1$ divide 560.<\/li>\n<\/ol>\n

    Acontece que estes dois fatos de fato s\u00e3o necess\u00e1rios e suficientes para um n\u00famero ser de Carmichael.<\/p>\n

    \n(Korselt<\/a>)
    \nSeja $n\\geq 2$ um n\u00famero natural composto. Ent\u00e3o $n$ \u00e9 um n\u00famero de Carmichael (ou seja, $b^n\\equiv b\\pmod n$ para todo $b\\in\\{1,\\ldots,n-1\\}$) se e somente se as seguintes propriedades s\u00e3o v\u00e1lidas:<\/p>\n
      \n
    1. $n$ \u00e9 livre de quadrado ($n$ n\u00e3o \u00e9 divis\u00edvel por $p^2$ para nenhum primo $p$);<\/li>\n
    2. se $p$ \u00e9 um primo que divide $n$, ent\u00e3o $p-1$ divide $n-1$.<\/li>\n<\/ol>\n<\/div>\n
      \nVamos come\u00e7ar com a demonstra\u00e7\u00e3o da volta. Assuma que $n\\in\\N$ satisfaz as duas propriedades no teorema. Escreva $n=p_1\\cdots p_k$ onde os $p_i$ s\u00e3o primos distintos e seja $a\\in\\Z$. Precisamos provar que $a^n\\equiv a\\pmod n$; ou seja $n\\mid a^n-a$, mas esta \u00faltima divisibilidade \u00e9 equivalente \u00e0s divisibilidades que $p_i\\mid a^n-a$ para todo $i$.<\/p>\n

      Se $p_i\\mid a$, ent\u00e3o $p_i\\mid a^n-a$. Se $p_i\\nmid a$, ent\u00e3o o Pequeno Teorema de Fermat implica que $a^{p_i-1}\\equiv 1\\pmod{p_i}$. Pela condi\u00e7\u00e3o 1., temos que $p-1\\mid n-1$; ou seja $n=q(p_i-1)+1$ com algum $q\\in\\Z$. Logo
      \n\\[
      \na^n=a^{q(p_i-1)+1}=(a^{p_i-1})^qa\\equiv a\\pmod{p_i}.
      \n\\]
      \nMas isso implica que $p_i\\mid a^n-a$. Como isso \u00e9 verdadeiro para todo $i\\in\\{1,\\ldots,k\\}$, obtemos que $n\\mid a^n-a$; ou seja $a^n\\equiv a\\pmod n$.<\/p>\n

      Agora consideremos a ida. Assuma que $n\\in\\N$ \u00e9 um n\u00famero de Carmichael. Promeiro provaremos afirma\u00e7\u00e3o 1. Assuma por contradi\u00e7\u00e3o que $p^2\\mid n$ com algum primo $p$. Como $n$ \u00e9 Carmichael, $p^n\\equiv p\\pmod n$, ou seja $n\\mid p^n-p$. Mas isso implica que
      \n\\[
      \np^2\\mid p^n-p=p(p^{n-1}-1)
      \n\\]
      \no que \u00e9 imposs\u00edvel, pois o primeiro fator no lado direito \u00e9 divis\u00edvel por $p$, mas n\u00e3o por $p^2$, enquanto o segundo fator n\u00e3o \u00e9 divis\u00edvel por $p$.<\/p>\n

      Agora assuma que $p$ \u00e9 um primo tal que $p\\mid n$. Precisamos provar que $p-1\\mid n-1$. O Teorema da Raiz Primitiva implica que existe $a\\in\\Z$ tal que $|a|_p=p-1$ (ou seja, $a^{p-1}\\equiv 1\\pmod p$, mas $a^k\\not\\equiv 1\\pmod p$ para todo $k\\in\\{1,\\ldots,p-2\\}$). Como $n$ \u00e9 Carmichael, temos que $a^n\\equiv a\\pmod n$, e assim $a^n\\equiv a\\pmod p$ (como $p\\mid n$). Mas $a$ \u00e9 invert\u00edvel m\u00f3dulo $p$ e assim $a^{n-1}\\equiv 1\\pmod p$ tamb\u00e9m segue. Isso implica que
      \n\\[
      \np-1=|a|_p\\mid n-1
      \n\\]
      \ne \u00e9 isso que n\u00f3s queremos provar.<\/p>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

      Seja $n$ um n\u00famero natural com $n\\geq 5$ e seja $a\\in\\{2,\\ldots,n-1\\}$. Lembre que $n$ \u00e9 dito pseudoprimo na base $a$ se $a^{n-1}\\equiv 1\\pmod n$. Observe que se $n$ for pseudoprimo na base $a$, ent\u00e3o $a^n\\equiv a\\pmod n$. Um n\u00famero composto $n$ \u00e9 dito n\u00famero de Carmichael se $a^n\\equiv a\\pmod n$ para todo $a\\in\\{1,\\ldots,n-1\\}$. Mostre que … Continue reading N\u00fameros de Carmichael<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1193,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1492"}],"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=1492"}],"version-history":[{"count":8,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1492\/revisions"}],"predecessor-version":[{"id":1996,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1492\/revisions\/1996"}],"up":[{"embeddable":true,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1193"}],"wp:attachment":[{"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/media?parent=1492"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}