2010/12/14 Bernardo Freitas Paulo da Costa <bernardo...@gmail.com> > 2010/12/14 Lucas Prado Melo <luca...@dcc.ufba.br>: > > 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 <= 10000. > Já é uma boa iniciativa (não sei porque Farey ajuda, mas você deve > saber...) e não achar nada até 10000 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<ad, então 0 <= d(b-aq) < ad, e portanto 0 <= b-aq < a ... Onde b-aq = r' que é o resto da divisão de b por a por definição. E, no final, 2*r <= db sse 2*dr' <= db sse 2*r' <= b Ou seja, o teorema vale para (ad, bd) sse valer para (a, b) -- []'s Lucas
