Fórum de Matemática
DÚVIDAS? Nós respondemos!

Sendo a = 111...1 (m dígitos iguais a 1) e b = 111...1 (n dígitos iguais a 1), como podemos provar que o mdc(a,b) = 111...1 (d dígitos iguais a 1, sendo d o mdc(m,n) )?

Para simplificar vamos designar por \([1]_n\) ao número 111...1 com n algarísmos 1.
Seja \(d=\mbox{m.d.c.}(m,n)\) e \(D=\mbox{m.d.c.}([1]_m,[1]_n)\).
Queremos mostrar que \(D=[1]_d\). Para tal vamos ver que \([1]_d\) divide \(D\) e vice-versa.

Parte 1 (\([1]_d\) divide \(D\)):
Não é difícil ver que se \(k\) divide \(n\) então \([1]_k\) divide \([1]_n\). Então temos que \([1]_d\) divide tanto \([1]_m\) como \([1]_n\). Logo \([1]_d\) divide \(D\).

Parte 2 (\(D\) divide \([1]_d\)):
É sabido (ver identidade de Bézout) que se \(d=\mbox{m.d.c.}(m,n)\) então existem inteiros \(x\) e \(y\) tais que \(d=xm+yn\) (sendo que \(x>0\) e \(y<0\) ou \(x<0\) e \(y>0\)). Sem perda de generalidade suponhamos que \(x>0\) e \(y<0\), logo \(d=|x|m-|y|n\). Neste caso temos que \([1]_m\) divide \([1]_{|x|m}\) (logo \(D\) também divide \([1]_{|x|m}\)) e que \([1]_n\) divide \([1]_{|y|n}\) (logo \(D\) também divide \([1]_{|y|n}\)). Portanto \(D\) divide \([1]_{|x|m}-[1]_{|y|n}=[1]_{d}\times 10^{|y|n}\). Como \(D\) e \(10^{|y|n}\) são coprimos temos portanto que \(D\) divide \([1]_d\).