This question is part of my assignment and I am really struggling with it.
Let us now apply these steps to a more general situation. As before we will suppose that the Euclidean algorithm runs in $3$ steps.
$$r_0 ÷ r_1 =m_1 R\;r_2$$
$$r_1 ÷ r_2 =m_2 R\;r_3$$
$$r_2 ÷ r_3 =m_3 R\;0$$
Prove that $r_3$ is factor of $r_0$ and $r_1$.
They have given the example of $\gcd(81,33) = 3$.
- The questions is asking for a proof to show why $3$ (the GCD should be a factor of $15,33$ and $81$)
You should have found that the last step of the algorithm gives 15 3 = 5R0. Use
this to conclude that 3 is a factor of 15. - You should have found that the second step of the algorithm gives 33 15 = 2R3.
Use this to conclude that 3 is a factor of 33 and 15. - You should have found that the first step of the algorithm gives 81 33 = 2R15. Use
this to conclude that 3 is a factor of 81 and 33.
I understand that since 15 is directly divisible by 3 , 15 has one of it's factor as 3.
And intuitively also I understand that 33 and 81 has factors of 3, but I do not know how can I prove that with what they are asking me.
Best Answer
Just do it.
$r_0\div r_1= m_1Rr_2 \implies r_0 = r_1\times m_1 + r_2$.
$r_1 \div r_2 = m_2Rr_3 \implies r_1 = m2\times r_2 + +r_3$
So $r_0 = r_1\times m_1 + r_2 = (m2\times r_2 +r_3)\times m_1 +r_2$
And $r_2\div r_3 = m_3R0\implies r_2 = m_3\times r_3$.
So $r_0 = r_1\times m_1 + r_2 = (m_2\times r_2 +r_3)\times m_1 +r_2=$
$(m_2\times (m_3\times r_3) +r_3)\times m_1 +(m_3\times r_3) =$
$[(m_2\times m_2 + 1)\times m_1 + m_3]\times r_3$.
So $r_3$ is a factor of $r_0$.
Do the same for $r_1$