{"id":1386,"date":"2021-11-07T21:43:29","date_gmt":"2021-11-08T00:43:29","guid":{"rendered":"http:\/\/localhost\/?page_id=1386"},"modified":"2023-01-06T14:46:06","modified_gmt":"2023-01-06T17:46:06","slug":"a-funcao-phi-de-euler","status":"publish","type":"page","link":"http:\/\/localhost\/index.php\/ensino\/fundamentos-de-algebra\/a-funcao-phi-de-euler\/","title":{"rendered":"A fun\u00e7\u00e3o $\\varphi$ de Euler"},"content":{"rendered":"
\nSeja $n\\in\\N$. Definimos
\n\\[
\n\\varphi(n)=|\\{a\\in\\{1,\\ldots,n\\}\\mid \\mdc an=1\\}|.
\n\\]
\nOu seja, $\\varphi(n)$ \u00e9 o n\u00famero de naturais entre $1$ e $n$ que s\u00e3o coprimos com $n$. Por exemplo, uma conta f\u00e1cil mostra que
\n\\[
\n\\varphi(1)=\\varphi(2)=1,\\quad \\varphi(3)=\\varphi(4)=2,\\quad \\varphi(5)=4,\\quad \\mbox{etc}.
\n\\]
\nA fun\u00e7\u00e3o $\\varphi$ \u00e9 chamado fun\u00e7\u00e3o de Euler, ou fun\u00e7\u00e3o totiente de Euler. Segue imediatamente da defini\u00e7\u00e3o de $\\varphi$ que $\\varphi(p)=p-1$ sempre que $p$ \u00e9 primo. O seguinte resultado d\u00e1 uma generaliza\u00e7\u00e3o para o caso quando $n$ \u00e9 uma pot\u00eancia de primo.<\/p>\n
\nSe $n=p^k$ onde $p$ \u00e9 primo e $k\\geq 1$, ent\u00e3o
\n\\[
\n\\varphi(n)=p^k-p^{k-1}=p^{k-1}(p-1).
\n\\]<\/div>\n
\nSeja $a\\in\\{1,\\ldots,p^k\\}$. Ent\u00e3o $\\mdc a{p^k}=1$ se e somente se $p\\nmid a$. O n\u00famero dos m\u00faltiplos de $p$ entre $1$ e $p^k$ \u00e9 $p^{k-1}$. Ent\u00e3o o n\u00famero dos inteiros que n\u00e3o s\u00e3o divis\u00edveis por $p$ no mesmo intervalo \u00e9 $p^k-p^{k-1}=p^{k-1}(p-1)$.<\/div>\n

Antes do teorema principal desta p\u00e1gina, colocamos um exerc\u00edcio.<\/p>\n

\nSejam $a,m,n\\in\\N$ tais que $\\mdc mn=1$. Mostre que $\\mdc a{mn}=\\mdc am\\mdc an$. Mostre que a condi\u00e7\u00e3o $\\mdc mn=1$ \u00e9 necess\u00e1ria para deduzir esta afirma\u00e7\u00e3o.<\/div>\n
\nSejam $m,n\\in\\N$ primos entre si. Ent\u00e3o
\n\\[
\n\\varphi(mn)=\\varphi(m)\\varphi(n).
\n\\]<\/div>\n
\nPrimeiro observe que $\\mdc 0{mn}\\neq 1$ e $\\mdc{mn}{mn}\\neq 1$, ent\u00e3o
\n\\[
\n\\varphi(mn)=|\\{a\\in\\{0,\\ldots,mn-1\\}\\mid \\mdc a{mn}=1\\}|.
\n\\]
\n(Ou seja, vamos contar os n\u00fameros $a$ entre $0$ e $mn-1$ que s\u00e3o coprimos com $mn$.) Seja $a\\in\\{0,\\ldots,mn-1\\}$ e escreva
\n\\[
\na=q_mm+r_m=q_nn+r_n
\n\\]
\nonde
\n\\[
\nr_m\\in\\{0,\\ldots,m-1\\}\\quad \\mbox{e}\\quad r_n=\\{0,\\ldots,n-1\\}.
\n\\]
\nDefina a aplica\u00e7\u00e3o $\\psi$ como na demonstra\u00e7\u00e3o do Teorema Chin\u00eas dos restos:
\n\\begin{align*}
\n\\psi&:\\{0,\\ldots,mn-1\\}\\to \\{0,\\ldots,m-1\\}\\times\\{0,\\ldots,n-1\\}\\\\
\na&\\mapsto(r_m,r_n).
\n\\end{align*}
\nPelo Teorema Chin\u00eas dos Restos, $\\psi$ \u00e9 bijetiva.<\/p>\n

Agora note que $\\mdc {r_n}n=\\mdc an$ e $\\mdc {r_m}m=\\mdc am$. Usando o exerc\u00edcio anterior, obtemos que
\n\\[
\n\\mdc a{mn}=\\mdc am\\mdc an=\\mdc {r_m}m\\cdot\\mdc {r_n}n.
\n\\]
\nMas a equa\u00e7\u00e3o anterior implica tamb\u00e9m que $\\mdc a{mn}=1$ se e somente se $\\mdc {r_m}m=\\mdc{r_n}n=1$.<\/p>\n

Restringindo a bije\u00e7\u00e3o $\\psi$ para o conjunto $X=\\{a\\in\\{0,\\ldots,mn-1\\}\\mid \\mdc a{mn}=1\\}$ obtemos uma bije\u00e7\u00e3o
\n\\[
\n\\psi:X\\to Y\\times Z
\n\\]
\nonde
\n\\begin{align*}
\nY&=\\{a\\in\\{0,\\ldots,m-1\\}\\mid \\mdc a{m}=1\\};\\\\
\nZ&=\\{a\\in\\{0,\\ldots,n-1\\}\\mid \\mdc a{n}=1\\}.
\n\\end{align*}
\nA exist\u00eancia da bije\u00e7\u00e3o entre $X$ e $Y\\times Z$ implica que $|X|=|Y\\times Z|$. Assim
\n\\[
\n\\varphi(mn)=|X|=|Y\\times Z|=|Y|\\cdot |Z|=\\varphi(m)\\varphi(n).
\n\\]<\/p>\n<\/div>\n

\nSeja $n$ um n\u00famero inteiro com $n\\geq 2$ e assuma que
\n\\[
\nn=p_1^{\\alpha_1}p_2^{\\alpha_2}\\cdots p_k^{\\alpha_k}
\n\\]
\nonde os $p_i$ s\u00e3o primos distintos dois a dois. Ent\u00e3o
\n\\[
\n\\varphi(n)=\\prod_{i=1}^k\\varphi(p_i^{\\alpha_i})=\\prod_{i=1}^k p_i^{\\alpha_i-1}(p_i-1)
\n\\]<\/div>\n
\nSegue dos dois resultados anteriores.<\/div>\n
\nVamos calcular $\\varphi(10^n)$ para $n\\geq 1$. Temos que
\n\\[
\n10^n=2^n\\cdot 5^n,
\n\\]
\nportanto
\n\\[
\n\\varphi(10^n)=2^{n-1}\\cdot 5^{n-1}\\cdot 4=2^{n+1}\\cdot 5^{n-1}.
\n\\]
\nPor exemplo
\n\\[
\n\\varphi(1000)=\\varphi(10^3)=2^4\\cdot 5^2=400.
\n\\]
\nOu seja, h\u00e1 $400$ naturais $a$ entre $1$ e $1000$ tal que $\\mdc a{1000}=1$.<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Seja $n\\in\\N$. Definimos \\[ \\varphi(n)=|\\{a\\in\\{1,\\ldots,n\\}\\mid \\mdc an=1\\}|. \\] Ou seja, $\\varphi(n)$ \u00e9 o n\u00famero de naturais entre $1$ e $n$ que s\u00e3o coprimos com $n$. Por exemplo, uma conta f\u00e1cil mostra que \\[ \\varphi(1)=\\varphi(2)=1,\\quad \\varphi(3)=\\varphi(4)=2,\\quad \\varphi(5)=4,\\quad \\mbox{etc}. \\] A fun\u00e7\u00e3o $\\varphi$ \u00e9 chamado fun\u00e7\u00e3o de Euler, ou fun\u00e7\u00e3o totiente de Euler. Segue imediatamente da defini\u00e7\u00e3o … Continue reading A fun\u00e7\u00e3o $\\varphi$ de Euler<\/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\/1386"}],"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=1386"}],"version-history":[{"count":10,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1386\/revisions"}],"predecessor-version":[{"id":1986,"href":"http:\/\/localhost\/index.php\/wp-json\/wp\/v2\/pages\/1386\/revisions\/1986"}],"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=1386"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}