Teoria de números/Máximo divisor comum: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
m correção da seq de Fibonacci, e pequenos ajustes
+exemplo
Linha 518:
Dado <math>n\ge 1\,\!</math>, sejam <math>a\,\!</math> e <math>b\,\!</math> os <u>menores números</u> tais que o algoritmo de Euclides aplicado a <math>a\,\!</math> e <math>b\,\!</math> leva exatamente <math>n\,\!</math> passos, então <math>a=F_{n+2}\,\!</math> e <math>b=F_{n+1}\,\!</math>.
}}
 
==== Exemplificando ====
 
Para determinar o valor de <math>(F_7, F_6) = (13, 8)\,\!</math>, seria necessário efetuar cinco divisões:
:{|
|-
|align=right| <math>13 = 8\cdot1 + 5\,\!</math>
|-
|align=right| <math>8 = 5\cdot1 + 3\,\!</math>
|-
|align=right| <math>5 = 3\cdot1 + 2\,\!</math>
|-
|align=right| <math>3 = 2\cdot1 + \mathbf{1}\,\!</math>
|-
|align=right| <math>2 = \mathbf{1}\cdot2 + 0\,\!</math>
|}
Logo, <math>(13,8) = 1\,\!</math>.
 
No entanto, se qualquer dos números for menor, o algoritmo requer menos etapas. Por exemplo, ao determinar <math>(13, 7)\,\!</math> tem-se:
:{|
|-
|align=right| <math>13 = 7\cdot1 + 6\,\!</math>
|-
|align=right| <math>7 = 6\cdot1 + \mathbf{1}\,\!</math>
|-
|align=right| <math>6 = \mathbf{1}\cdot6 + 0\,\!</math>
|}
Donde, <math>(13,7) = 1\,\!</math>.
 
Já o cálculo de <math>(12, 8)\,\!</math> é ainda mais simples:
:{|
|-
|align=right| <math>12 = 8\cdot1 + \mathbf{4}\,\!</math>
|-
|align=right| <math>8 = \mathbf{4}\cdot2 + 0\,\!</math>
|}
Portanto, <math>(12,8) = 4\,\!</math>.
 
== Exercícios ==