[obm-l] Re: [obm-l] Re: [obm-l] Inequação com resto
2010/12/14 Bernardo Freitas Paulo da Costa > 2010/12/14 Lucas Prado Melo : > > Olá, > Oi, > > > recentemente encontrei a seguinte conjectura (que ele diz parecer > evidente > > para ele, mas que eu não consigo provar pra mim mesmo) num trabalho > > acadêmico de um colega: > > Seja a, b naturais diferentes de 0, com a <= b. Seja b%a o resto de b na > > divisão por 'a'. > > Então 2*(b%a) <= b > > > > Alguém poderia provar (ou dar contra-exemplo)? Eu tentei fazer uma busca > por > > pelos 'a' e 'b' primos entre si (usando sequências de Farey), mas não > > consegui encontrar um contraxemplo com b <= 1. > Já é uma boa iniciativa (não sei porque Farey ajuda, mas você deve > saber...) e não achar nada até 1 deveria ser um "sinal" bom para > começar a procurar uma demonstração :) > > Escreva b = q*a + r (a divisão euclidiana de b por a, quociente q, > resto r). A gente quer mostrar que 2*r <= b. O que a gente sabe : > 0 <= r < a > 0 <= a <= b, logo q >= 1 > > Então r = b - q*a, 2*r = r + b - q*a = b + (r - q*a). Como q >= 1, q*a > >= a > r, logo o termo entre parênteses é negativo (estritamente) e > assim 2r = b + Negativo < b. > > Veja que a "idéia" de provar isso foi a seguinte: fixe o a, e faça > variar o b. Se b for muito perto do a, o resto r vai ser "pequeno", e > daí não funciona. Se b for muito maior, o resto r vai ser pequeno > porque menor do que a. No "meio do caminho", você tem b = 2a - 1, que > deixa resto (a-1), mas, nem assim, dá certo, já que 2(a-1) < 2a - 1 = > b. > Obrigado a todos pelas respostas :-) Eu usei Farey para encontrar pares de números primos entre si, já que quando o par de números não é primo entre si podemos dividí-los pelo mdc e usar a resposta do novo par para responder ao original. Prova: Seja o caso para ad, bd com mdc(a,b)=1. bd = q*ad + r => d(b - aq) = r Por definição de resto, 0<=r
[obm-l] Re: [obm-l] Inequação com resto
2010/12/14 Lucas Prado Melo : > Olá, Oi, > recentemente encontrei a seguinte conjectura (que ele diz parecer evidente > para ele, mas que eu não consigo provar pra mim mesmo) num trabalho > acadêmico de um colega: > Seja a, b naturais diferentes de 0, com a <= b. Seja b%a o resto de b na > divisão por 'a'. > Então 2*(b%a) <= b > > Alguém poderia provar (ou dar contra-exemplo)? Eu tentei fazer uma busca por > pelos 'a' e 'b' primos entre si (usando sequências de Farey), mas não > consegui encontrar um contraxemplo com b <= 1. Já é uma boa iniciativa (não sei porque Farey ajuda, mas você deve saber...) e não achar nada até 1 deveria ser um "sinal" bom para começar a procurar uma demonstração :) Escreva b = q*a + r (a divisão euclidiana de b por a, quociente q, resto r). A gente quer mostrar que 2*r <= b. O que a gente sabe : 0 <= r < a 0 <= a <= b, logo q >= 1 Então r = b - q*a, 2*r = r + b - q*a = b + (r - q*a). Como q >= 1, q*a >= a > r, logo o termo entre parênteses é negativo (estritamente) e assim 2r = b + Negativo < b. Veja que a "idéia" de provar isso foi a seguinte: fixe o a, e faça variar o b. Se b for muito perto do a, o resto r vai ser "pequeno", e daí não funciona. Se b for muito maior, o resto r vai ser pequeno porque menor do que a. No "meio do caminho", você tem b = 2a - 1, que deixa resto (a-1), mas, nem assim, dá certo, já que 2(a-1) < 2a - 1 = b. Abraços, -- Bernardo Freitas Paulo da Costa = Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] Inequação com resto
Caso 2a >b, a divisão b/a dá 1, com resto igual a b-a, que é menor que b/2. Caso 2a=b, o resto é zero. Caso 2ahttp://www.mat.puc-rio.br/~obmlistas/obm-l.html =
[obm-l] Re: [obm-l] Inequação com resto
Dado b>=a, escreva b=ma+r onde m eh inteiro positivo e 0<=r=1 (pois b>=a), temos b=ma+r>=a+r>r+r=2r. Ou seja, 2r > Olá, > > recentemente encontrei a seguinte conjectura (que ele diz parecer evidente > para ele, mas que eu não consigo provar pra mim mesmo) num trabalho > acadêmico de um colega: > Seja a, b naturais diferentes de 0, com a <= b. Seja b%a o resto de b na > divisão por 'a'. > Então 2*(b%a) <= b > > Alguém poderia provar (ou dar contra-exemplo)? Eu tentei fazer uma busca > por pelos 'a' e 'b' primos entre si (usando sequências de Farey), mas não > consegui encontrar um contraxemplo com b <= 1. > > -- > []'s > Lucas >
