Olá Paulo, Considere genericamente uma base q.
Se X = bbb...b e Y = bbb...bbb nessa base, então X = b*(1 + q + ... + q^(a*d-1)) e Y = b*(1 + q + ... + q^(m*d-1)), onde n = a*d, k = m*d e o d = mdc(n,k). Note também que X = b*[(q^d - 1)/(q - 1)]*[(Q^a - 1)/(Q - 1)] e Y = b*[(q^d - 1)/(q - 1)]*[(Q^m - 1)/(Q - 1)], onde Q = q^d. Isso mostra que v = b*[(q^d - 1)/(q - 1)] = b*(1 + q + ... + q^(d-1)) é divisor comum de X e Y. Resta mostrar que é máximo. Para tanto, basta verificar que se p é primo e divide W = [(Q^a - 1)/(Q - 1)] e Z = [(Q^m - 1)/(Q - 1)], então p divide 1, absurdo, donde p não existe e mdc (Z,W) = 1. Em outras palavras, v será o mdc de X e Y. Suponhamos, sem perda de generalidade, que W > Z, ou seja, a > m. p | Z = 1 + Q + ... + Q^(a-1) p | W = 1 + Q + ... + Q^(m-1) Logo, p | (Z - W) = Q^m*(1 + Q + ... + Q^(a - m - 1)). É fácil ver que p não pode dividir Q, do contrário, de p | Z teríamos que p | 1. Assim, p | (1 + Q + ... + Q^(a - m - 1)). Existe um natural s mínimo tal que m > a - s*m > 0. Ao repetir o processo acima trocando a por a - m, e depois por a - 2*m, e assim por diante, obteremos indutivamente, para vários r, que p | 1 + Q + ... + Q^(a - (r+1)*m - 1). Esse processo não pode ser aplicado indefinidamente! Só vale até chegarmos a s-1, gerando implicações sobre s. Em particular, p | 1 + Q + ... + Q^(a - s*m - 1), com c_0 = m > a - s*m = c_1 > 0. Repetindo o processo, agora trocando c_0 por c_1, e assim sucessivamente, obteremos uma seqüência decrescente de naturais c_t tais que p | 1 + Q + ... + Q^(c_t - 1). Ora, por sua natureza decrescente, inteira e positiva, em algum momento o processo termina, com c_t = 1. Isso implica que não teremos saída, e necessariamente p | 1, absurdo. Isso demonstra que v = b*[(q^d - 1)/(q - 1)] = b*(1 + q + ... + q^(d-1)) é o mdc de X e Y. Abraços, Daniel Em 16 de novembro de 2010 22:06, Paulo Argolo <pauloarg...@bol.com.br>escreveu: > Caros Colegas, > > Como podemos provar o teorema abaixo: > > "O máximo divisor comum dos números naturais bbb...b (n dígitos iguais a b) > e bbb...n (k dígitos iguais a b) é bbb...b (d dígitos iguais a b), d é o > máximo divisor comum de n e k." > > Abraços! > Paulo > ========================================================================= > Instru�ões para entrar na lista, sair da lista e usar a lista em > http://www.mat.puc-rio.br/~obmlistas/obm-l.html=========================================================================
