Algoritmo de Euclides estendido: diferenças entre revisões

Explicando como começar a sequência uk e a sequência vk
(Explicando como começar a sequência uk e a sequência vk)
 
<math>r_{k} = au_{k} + bv_{k}</math>
<nowiki> </nowiki>e
<math>r_{k-1} = au_{k-1} + bv_{k-1}</math>
 
então, para o próximo resto, teremos
 
<math>r_\begin{k+1align} = r_{k-1} - r_kq_k
= (au_r_{k-+1} +& bv_= r_{k-1}) - (au_{k}r_kq_k + bv_{k})q_k\\
& = a(u_au_{k-1} -+ u_bv_{k-1}q_k) +- b(v_au_{k-1} -+ v_bv_{k}q_k)q_k \\
& = au_{k+-1} - au_{k}q_k + bv_{k+-1} - bv_{k}q_k \\
& = a(u_{k-1} - u_{k}q_k) + b(v_{k-1} - v_{k}q_k) \\
& = au_{k+1} + bv_{k+1} \\
\end{align}
</math>
 
Ou seja, se a igualdade de Bézout vale para a iteração atual do algoritmo e para a iteração anterior, então, ela vale para a próxima e os valores de BézouBézout são
 
<math>u_{k+1} = u_{k-1} - u_{k}q_k</math>
 
e
 
<math>v_{k+1} = v_{k-1} - v_{k}q_k</math>
 
PercebePerceba que os valores de Bézout também estão sendo totalmente definidos pelos valores das duas últimas iterações do algoritmo.
 
Dessa forma, para estender o Algoritmo de Euclides original, só precisamos guardar os valores referentes à essas duas sequências (<math>v_k</math> e <math>u_{k}</math>) além da que o original já guarda (a sequência <math>r_k</math>) e definir valores para que tenhamos igualdades válidas para <math>k = 0</math> e para <math>k = 1</math> (já que cada sequência é definida em termos de duas iterações anteriores).
 
No entanto, definir esses valores é fácil: podemos tomar
 
<math>(r_0, u_0, v_0) = (a, 1, 0)</math>, o que torna válida a igualdade para <math>k = 0</math> (ou seja, <math>r_0 = au_0 + bv_0</math>)
 
 
<math>(r_1, u_1, v_1) = (b, 0, 1)</math>, o que torna válida a igualdade para <math>k = 1</math> (ou seja, <math>r_1 = au_1 + bv_1</math>)
Dessa forma, para estender o Algoritmo de Euclides original, só precisamos guardar os valores referentes à essas duas sequências (<math>v_k</math> e <math>u_{k}</math>) além da que o original já guarda (a sequência <math>r_k</math>).
 
== Um exemplo ==
283

edições