[obm-l] Phi de Euler
Oi, Platao e Duda: Dentro do espirito de se buscar sempre a solucao mais bonita pra cada problema, aqui vai a minha candidata pra este ai: Se mdc(n,k) = 1 entao mdc(n,n-k) = 1. Logo, se n 2, podemos arranjar os inteiros positivos menores que n e primos com n em pares disjuntos da forma {k,n-k}. Isso quer dizer que Phi(n) eh par para n 2. Eh claro que se k = n - k entao n = 2k e mdc(n,k) = k 1 (a menos que k = 1 == n = 2, mas esse caso jah foi descartado). E se mudarmos a pergunta original para: A imagem da funcao Phi contem todos os inteiros positivos pares? (por exemplo, 14?) Um abraco, Claudio. on 30.01.04 01:04, Eduardo Casagrande Stabel at [EMAIL PROTECTED] wrote: Oi Platão e demais. Não querendo corrigir, mas já enriquecendo a mensagem do Platão. Se n é primo (com exceção a n=2) então Phi(n) = n-1 é par. Se n é potência de primo n = p^i (com i=2) então Phi(n) = p^i - p^(i-1) também é par. Já que a função Phi é multiplicatica, isto é, se mdc(m,n)=1 então Phi(mn) = Phi(m) Phi(n), então segue a conclusão de que, a menos para n = 2, Phi(n) é um número par. Para quem não conhece (a maioria), o Platão é amigo meu, de Novo Hamburgo, e portanto também gaúcho. Saudações ao mais novo membro da lista, todos esperamos boas contribuições como essa! Seja bem-vindo! Abração, Duda. From: Platão Gonçalves Terra Neto [EMAIL PROTECTED] Basta ver que se p é primo, ímpar, então phi(p)=p-1, par. Para n=b^c, b primo, phi(b^c)=b^c-b^(c-1), que é par, ou seja, se n=a1^p2*a2^p2*...an^pn, sendo ai, todos primos , distintos , n2 e pi expoentes, então phi(n) é par. Se n=2^k, phi(n)=2^k-2^(k-1), que é par, exceção, para phi(2)=1. phi(1)=1. Logo, phi(n) é par , para todo n2, donde ,N* não é imagem de phi(n) - Original Message - From: André Martin Timpanaro [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, January 29, 2004 8:38 PM Subject: [obm-l] Dúvida A afirmação abaixo é verdadeira? Dado um número natural n não nulo existe algum natural m tal que phi(m)=n. Onde phi(x) é a função phi de Euler. Em outras palavras, a imagem de phi(x) é N* ? André T. _ MSN Messenger: converse com os seus amigos online. http://messenger.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
RE: [obm-l] Phi de Euler
Muito interessante essa demonstração combinatória! Quanto a sua reformulação, ainda restringindo o contradomínio aos números pares a função phi é altamente não sobrejetiva... Frederico. From: Claudio Buffara [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Phi de Euler Date: Fri, 30 Jan 2004 09:44:19 -0200 Oi, Platao e Duda: Dentro do espirito de se buscar sempre a solucao mais bonita pra cada problema, aqui vai a minha candidata pra este ai: Se mdc(n,k) = 1 entao mdc(n,n-k) = 1. Logo, se n 2, podemos arranjar os inteiros positivos menores que n e primos com n em pares disjuntos da forma {k,n-k}. Isso quer dizer que Phi(n) eh par para n 2. Eh claro que se k = n - k entao n = 2k e mdc(n,k) = k 1 (a menos que k = 1 == n = 2, mas esse caso jah foi descartado). E se mudarmos a pergunta original para: A imagem da funcao Phi contem todos os inteiros positivos pares? (por exemplo, 14?) Um abraco, Claudio. on 30.01.04 01:04, Eduardo Casagrande Stabel at [EMAIL PROTECTED] wrote: Oi Platão e demais. Não querendo corrigir, mas já enriquecendo a mensagem do Platão. Se n é primo (com exceção a n=2) então Phi(n) = n-1 é par. Se n é potência de primo n = p^i (com i=2) então Phi(n) = p^i - p^(i-1) também é par. Já que a função Phi é multiplicatica, isto é, se mdc(m,n)=1 então Phi(mn) = Phi(m) Phi(n), então segue a conclusão de que, a menos para n = 2, Phi(n) é um número par. Para quem não conhece (a maioria), o Platão é amigo meu, de Novo Hamburgo, e portanto também gaúcho. Saudações ao mais novo membro da lista, todos esperamos boas contribuições como essa! Seja bem-vindo! Abração, Duda. From: Platão Gonçalves Terra Neto [EMAIL PROTECTED] Basta ver que se p é primo, ímpar, então phi(p)=p-1, par. Para n=b^c, b primo, phi(b^c)=b^c-b^(c-1), que é par, ou seja, se n=a1^p2*a2^p2*...an^pn, sendo ai, todos primos , distintos , n2 e pi expoentes, então phi(n) é par. Se n=2^k, phi(n)=2^k-2^(k-1), que é par, exceção, para phi(2)=1. phi(1)=1. Logo, phi(n) é par , para todo n2, donde ,N* não é imagem de phi(n) - Original Message - From: André Martin Timpanaro [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, January 29, 2004 8:38 PM Subject: [obm-l] Dúvida A afirmação abaixo é verdadeira? Dado um número natural n não nulo existe algum natural m tal que phi(m)=n. Onde phi(x) é a função phi de Euler. Em outras palavras, a imagem de phi(x) é N* ? André T. _ MSN Messenger: converse com os seus amigos online. http://messenger.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = _ MSN Messenger: converse com os seus amigos online. http://messenger.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Phi de Euler
Com relacao a beleza matematica, uma regra que eu acho que falha pouco eh a seguinte: se um resultado tem uma demonstracao combinatoria, entao essa demonstracao eh a mais bonita. O unico contra-exemplo que me ocorre eh o caso do uso de algebra linear pra se demonstrar alguns resultados de combinatoria, mas isso eh a minha opiniao pessoal... Outro resultado parecido que tem uma demonstracao combinatoria identica eh: se n eh um inteiro positivo, entao d(n) eh impar se e somente se n eh quadrado perfeito, onde d(n) = no. de divisores positivos de n. Acho que dah pra provar que se p eh um primo tal que 2p+1 eh composto, entao a equacao Phi(x) = 2p nao tem solucao. Um abraco, Claudio. on 30.01.04 11:00, Frederico Reis Marques de Brito at [EMAIL PROTECTED] wrote: Muito interessante essa demonstração combinatória! Quanto a sua reformulação, ainda restringindo o contradomínio aos números pares a função phi é altamente não sobrejetiva... Frederico. From: Claudio Buffara [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Phi de Euler Date: Fri, 30 Jan 2004 09:44:19 -0200 Oi, Platao e Duda: Dentro do espirito de se buscar sempre a solucao mais bonita pra cada problema, aqui vai a minha candidata pra este ai: Se mdc(n,k) = 1 entao mdc(n,n-k) = 1. Logo, se n 2, podemos arranjar os inteiros positivos menores que n e primos com n em pares disjuntos da forma {k,n-k}. Isso quer dizer que Phi(n) eh par para n 2. Eh claro que se k = n - k entao n = 2k e mdc(n,k) = k 1 (a menos que k = 1 == n = 2, mas esse caso jah foi descartado). E se mudarmos a pergunta original para: A imagem da funcao Phi contem todos os inteiros positivos pares? (por exemplo, 14?) Um abraco, Claudio. on 30.01.04 01:04, Eduardo Casagrande Stabel at [EMAIL PROTECTED] wrote: Oi Platão e demais. Não querendo corrigir, mas já enriquecendo a mensagem do Platão. Se n é primo (com exceção a n=2) então Phi(n) = n-1 é par. Se n é potência de primo n = p^i (com i=2) então Phi(n) = p^i - p^(i-1) também é par. Já que a função Phi é multiplicatica, isto é, se mdc(m,n)=1 então Phi(mn) = Phi(m) Phi(n), então segue a conclusão de que, a menos para n = 2, Phi(n) é um número par. Para quem não conhece (a maioria), o Platão é amigo meu, de Novo Hamburgo, e portanto também gaúcho. Saudações ao mais novo membro da lista, todos esperamos boas contribuições como essa! Seja bem-vindo! Abração, Duda. From: Platão Gonçalves Terra Neto [EMAIL PROTECTED] Basta ver que se p é primo, ímpar, então phi(p)=p-1, par. Para n=b^c, b primo, phi(b^c)=b^c-b^(c-1), que é par, ou seja, se n=a1^p2*a2^p2*...an^pn, sendo ai, todos primos , distintos , n2 e pi expoentes, então phi(n) é par. Se n=2^k, phi(n)=2^k-2^(k-1), que é par, exceção, para phi(2)=1. phi(1)=1. Logo, phi(n) é par , para todo n2, donde ,N* não é imagem de phi(n) - Original Message - From: André Martin Timpanaro [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, January 29, 2004 8:38 PM Subject: [obm-l] Dúvida A afirmação abaixo é verdadeira? Dado um número natural n não nulo existe algum natural m tal que phi(m)=n. Onde phi(x) é a função phi de Euler. Em outras palavras, a imagem de phi(x) é N* ? André T. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =
Re: [obm-l] Phi de Euler
Dividindo em alguns casos é de fato possível demonstrar sua última afirmação. è fácil ver que x teria que ser da forma 2^a . q^b , com a=0 ou 1 e q primo. Daí é só testar as possibilidades... Imagino que exista alguma demonstração mais direta, mas essa é bem construtiva. Frederico. From: Claudio Buffara [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: [obm-l] Phi de Euler Date: Fri, 30 Jan 2004 12:13:32 -0200 Com relacao a beleza matematica, uma regra que eu acho que falha pouco eh a seguinte: se um resultado tem uma demonstracao combinatoria, entao essa demonstracao eh a mais bonita. O unico contra-exemplo que me ocorre eh o caso do uso de algebra linear pra se demonstrar alguns resultados de combinatoria, mas isso eh a minha opiniao pessoal... Outro resultado parecido que tem uma demonstracao combinatoria identica eh: se n eh um inteiro positivo, entao d(n) eh impar se e somente se n eh quadrado perfeito, onde d(n) = no. de divisores positivos de n. Acho que dah pra provar que se p eh um primo tal que 2p+1 eh composto, entao a equacao Phi(x) = 2p nao tem solucao. Um abraco, Claudio. on 30.01.04 11:00, Frederico Reis Marques de Brito at [EMAIL PROTECTED] wrote: Muito interessante essa demonstração combinatória! Quanto a sua reformulação, ainda restringindo o contradomínio aos números pares a função phi é altamente não sobrejetiva... Frederico. From: Claudio Buffara [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Phi de Euler Date: Fri, 30 Jan 2004 09:44:19 -0200 Oi, Platao e Duda: Dentro do espirito de se buscar sempre a solucao mais bonita pra cada problema, aqui vai a minha candidata pra este ai: Se mdc(n,k) = 1 entao mdc(n,n-k) = 1. Logo, se n 2, podemos arranjar os inteiros positivos menores que n e primos com n em pares disjuntos da forma {k,n-k}. Isso quer dizer que Phi(n) eh par para n 2. Eh claro que se k = n - k entao n = 2k e mdc(n,k) = k 1 (a menos que k = 1 == n = 2, mas esse caso jah foi descartado). E se mudarmos a pergunta original para: A imagem da funcao Phi contem todos os inteiros positivos pares? (por exemplo, 14?) Um abraco, Claudio. on 30.01.04 01:04, Eduardo Casagrande Stabel at [EMAIL PROTECTED] wrote: Oi Platão e demais. Não querendo corrigir, mas já enriquecendo a mensagem do Platão. Se n é primo (com exceção a n=2) então Phi(n) = n-1 é par. Se n é potência de primo n = p^i (com i=2) então Phi(n) = p^i - p^(i-1) também é par. Já que a função Phi é multiplicatica, isto é, se mdc(m,n)=1 então Phi(mn) = Phi(m) Phi(n), então segue a conclusão de que, a menos para n = 2, Phi(n) é um número par. Para quem não conhece (a maioria), o Platão é amigo meu, de Novo Hamburgo, e portanto também gaúcho. Saudações ao mais novo membro da lista, todos esperamos boas contribuições como essa! Seja bem-vindo! Abração, Duda. From: Platão Gonçalves Terra Neto [EMAIL PROTECTED] Basta ver que se p é primo, ímpar, então phi(p)=p-1, par. Para n=b^c, b primo, phi(b^c)=b^c-b^(c-1), que é par, ou seja, se n=a1^p2*a2^p2*...an^pn, sendo ai, todos primos , distintos , n2 e pi expoentes, então phi(n) é par. Se n=2^k, phi(n)=2^k-2^(k-1), que é par, exceção, para phi(2)=1. phi(1)=1. Logo, phi(n) é par , para todo n2, donde ,N* não é imagem de phi(n) - Original Message - From: André Martin Timpanaro [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, January 29, 2004 8:38 PM Subject: [obm-l] Dúvida A afirmação abaixo é verdadeira? Dado um número natural n não nulo existe algum natural m tal que phi(m)=n. Onde phi(x) é a função phi de Euler. Em outras palavras, a imagem de phi(x) é N* ? André T. = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html = _ MSN Messenger: converse com os seus amigos online. http://messenger.msn.com.br = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =