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 , n>2 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 n>2, 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
=
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 , n>2 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 n>2, 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
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 , n>2 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 n>2, 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
=
