O algoritmo de Euclides consiste numa sequência de divisões inteiras para determinar o máximo divisor comum entre dois números naturais. Não o vou descrever, o leitor interessado investiga e encontra sem problemas.
Vou dar um exemplo.
Suponhamos que se pretende calcular $mdc(310402,23725)$. Faz-se:
\begin{eqnarray*}
{310402}&{=}&{23725\times {\color{blue}13}+1977}\\
{23725}&{=}&{1977\times {\color{blue}12}+{\color{red}1}}\\
{1977}&{=}&{1\times {\color{blue}1977}+0}
\end{eqnarray*}
O último resto diferente de zero, é ${\color{red}1}$ logo $mdc(310402,23725)={\color{red}1}$.
Isto implica que a fracção $\frc{310402}{23725}$ é irredutível.
Estão a ver aqueles números a azul?
\[\frc{310402}{23725}=[{\color{blue}13};{\color{blue}12},{\color{blue}1977}]\]
Ou seja,
\[\frc{310402}{23725}={\color{blue}13}+\frc{1}{{\color{blue}12}+\frc{1}{{\color{blue}1977}}}\]
No post anterior eu demonstrei por indução, umas fórmulas de recorrência. Desta vez deixo a cargo do leitor o trabalho de escrever uma demonstração de que sempre que temos uma fracção irredutível, isto funciona. É mais simples, mas mesmo assim dou uma sugestão: comece por obter o desenvolvimento em fracção contínua passo por passo, sem recorrer ao algoritmo das fracções contínuas, recorrendo apenas ao algoritmo de Euclides.
Note-se que o facto de o algoritmo de Euclides ter um número finito de passos, implica que um número racional terá sempre uma "fracção simples finita".
Divagações matemáticas, probabilísticas, físicas, exactas, aproximadas e até disparatadas...
Sem comentários:
Enviar um comentário