{"id":804,"date":"2020-08-20T23:03:57","date_gmt":"2020-08-20T23:03:57","guid":{"rendered":"http:\/\/localhost\/?page_id=804"},"modified":"2022-04-28T09:04:40","modified_gmt":"2022-04-28T12:04:40","slug":"numeros-primos","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/algebra-a\/numeros-primos\/","title":{"rendered":"N\u00fameros primos"},"content":{"rendered":"
\nVamos come\u00e7ar por uma conta detalhada usando o algoritmo de Euclides.<\/p>\n
\nVamos calcular $\\mdc{232}{136}$. As divis\u00f5es euclidianas ser\u00e3o as seguintes:
\n\\begin{eqnarray*}
\n232&=&1\\cdot 136+96\\\\
\n136&=&1\\cdot 96+40\\\\
\n96&=&2\\cdot 40+16\\\\
\n40&=&2\\cdot 16+8\\\\
\n16&=&2\\cdot 8+0.
\n\\end{eqnarray*}
\nObtemos ent\u00e3o que $\\mdc{232}{136}=8$.<\/p>\n

Determinemos agora n\u00fameros $u,v\\in\\Z$ tais que
\n\\[
\nu\\cdot 232+v\\cdot 136=\\mdc{232}{136}=8.
\n\\]
\nVamos de cima para baixo nas contas do Algoritmo de Euclides. Obtemos das divis\u00f5es acima que
\n\\begin{align*}
\n96&=232-136\\\\
\n40&=136-96=136-(232-136)=-232+2\\cdot 136\\\\
\n16&=96-2\\cdot 40=(232-136)-2(-232+2\\cdot 136)\\\\&=3\\cdot 232-5\\cdot 136\\\\
\n8&=40-2\\cdot 16=(-232+2\\cdot 136)-2(3\\cdot 232-5\\cdot 136)\\\\&=-7\\cdot 232+12\\cdot 136.
\n\\end{align*}
\nEnt\u00e3o obtemos que
\n\\[
\n8=\\mdc{232}{136}=-7\\cdot 232+12\\cdot 136.
\n\\]
\nNote que os coeficientes $u=-7$ e $v=12$ n\u00e3o s\u00e3o \u00fanicos.\n<\/p><\/div>\n

\n
\nUm n\u00famero inteiro $n$ diferente de $\\pm 1$ e de $0$ \u00e9 dito primo<\/em> se os \u00fanicos divisores de $n$ s\u00e3o $\\pm 1$ e $\\pm n$. No caso contr\u00e1rio, o n\u00famero \u00e9 dito composto<\/em>. Os n\u00fameros $1$, $-1$, e $0$ n\u00e3o s\u00e3o considerados nem primos nem compostos.\n<\/div>\n

Por exemplo, o n\u00famero $-5$ \u00e9 primo, pois ele \u00e9 divis\u00edvel por apenas $\\pm 1$ e $\\pm 5$. O n\u00famero $6$ \u00e9 composto, pois ele \u00e9 divis\u00edvel, por exemplo, por $2$.<\/p>\n

A seguinte \u00e9 uma propriedade importante dos n\u00fameros primos.<\/p>\n

Sejam $p$ um primo e $a,b\\in\\Z$ tais que $p\\mid ab$. Ent\u00e3o $p\\mid a$ ou $p\\mid b$.\n<\/div>\n
\nAssuma que as condi\u00e7\u00f5es do Teorema est\u00e3o v\u00e1lidas e que $p\\nmid a$. Ent\u00e3o $\\mdc pa=1$ e obtemos do Algoritmo de Euclides que existem $u,v\\in\\Z$ tais que $up+va=1$. Multiplicando por $b$, obtemos que
\n\\[
\nupb+vab=b.
\n\\]
\nComo $p$ divide $ab$, o n\u00famero $p$ divide $vab$, ent\u00e3o $p$ divide as duas parcelas no lado esquerdo da \u00faltima equa\u00e7\u00e3o. Mas isso implica que $p\\mid b$.\n<\/div>\n

O seguinte teorema \u00e9 bem conhecido dos nossos estudos pr\u00e9vios. Aqui n\u00f3s vamos apresent\u00e1-lo sem demonstra\u00e7\u00e3o;<\/p>\n

\nTodo n\u00famero natural maior ou igual a $2$ pode ser escrito como produto de primos positivos. Al\u00e9m disso, esta decomposi\u00e7\u00e3o \u00e9 unica a menos da ordem dos fatores.\n<\/div>\n

Por exemplo, temos que
\n\\[
\n120=2\\cdot 2\\cdot 2\\cdot 3\\cdot 5=2\\cdot 2\\cdot 3\\cdot 5\\cdot 2=\\cdots=2^3\\cdot 3\\cdot 5.
\n\\]<\/p>\n

Algoritmos.\u00a0<\/strong>Neste momento n\u00e3o se sabe se existe algum algoritmo que pode determinar eficientemente a fatora\u00e7\u00e3o de um n\u00famero\u00a0 grande. De fato, muitos m\u00e9todos na criptografia est\u00e3o baseados na suposi\u00e7\u00e3o que uma pessoa que intercepta a mensagem n\u00e3o vai conseguir fatorar os n\u00fameros envolvidos e ent\u00e3o n\u00e3o consegue decifrar o conte\u00fado.<\/p>\n

O primeiro algoritmo<\/a> eficiente para testar primalidade de um n\u00famero grande foi apresentado por\u00a0Manindra Agrawal<\/a>,\u00a0Neeraj Kayal<\/a>\u00a0e\u00a0Nitin Saxena<\/a>\u00a0em 2002. Este algoritmo \u00e9 conhecido como o Algoritmo AKS e \u00e9 estudado no livro de Shoup.<\/p>\n

O seguinte teorema foi conhecido j\u00e1 na antiguidade e apareceu em particular nos trabalhos de Euclides<\/a>.<\/p>\n

Existem infinitos primos.\n<\/div>\n
\u00a0Suponha com o objetivo de obter uma contradi\u00e7\u00e3o que existem apenas finitos primos, nomeadamente, $p_1=2$, $p_2=3$, $p_3=5,\\ldots,p_m$. Considere o n\u00famero
\n\\[
\nN=p_1p_2p_3\\cdots p_m+1.
\n\\]
\nOra $N$ n\u00e3o \u00e9 primo, pois ele \u00e9 maior que todos os primos que supostamente existem. Al\u00e9m disso, $N$ deve ser divis\u00edvel por algum primo $p$. Por outro lado, os primos $p_1,\\ldots,p_m$ n\u00e3o dividem $N$, pois o resto de $N$ quando for dividido por estes primos \u00e9 igual a $1$. Isto implica que $p$ precisa ser um novo primo que n\u00e3o est\u00e1 na suposta lista de todos os primos. Isto \u00e9 uma contradi\u00e7\u00e3o que significa que a nossa suposi\u00e7\u00e3o foi errada; ou seja, o n\u00famero dos primos precisa ser infinito.\n<\/div>\n
\n","protected":false},"excerpt":{"rendered":"

Vamos come\u00e7ar por uma conta detalhada usando o algoritmo de Euclides. Vamos calcular $\\mdc{232}{136}$. As divis\u00f5es euclidianas ser\u00e3o as seguintes: \\begin{eqnarray*} 232&=&1\\cdot 136+96\\\\ 136&=&1\\cdot 96+40\\\\ 96&=&2\\cdot 40+16\\\\ 40&=&2\\cdot 16+8\\\\ 16&=&2\\cdot 8+0. \\end{eqnarray*} Obtemos ent\u00e3o que $\\mdc{232}{136}=8$. Determinemos agora n\u00fameros $u,v\\in\\Z$ tais que \\[ u\\cdot 232+v\\cdot 136=\\mdc{232}{136}=8. \\] Vamos de cima para baixo nas contas do … Continue reading N\u00fameros primos<\/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\/804"}],"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=804"}],"version-history":[{"count":8,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/804\/revisions"}],"predecessor-version":[{"id":1765,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/804\/revisions\/1765"}],"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=804"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}