Find the highest common factor.

Question

Find the highest common factor h of 366 and 305. Find s, t ∈ Z such that h = 366s + 305t.

I think i have to go through Euclid's algorithm to find h, then backtracking gives you s,t. but not sure how to implement the numbers.

Answer 1

HINT:

$$366=2\cdot 3\cdot 61$$ and $$305=5\cdot 61$$

Answer 2

There is something called the extended euclidean algorithm that is used to calculate these numbers. However, one can figure $s$ and $t$ from the usual euclidean algorithm as well. In your example using the euclidean algorithm we get that $$ 366 = 305 +61$$ $$ 305 = 5\times61$$ So we see that $h=61$ and so rearranging the first equation gives us $s=1$, $t=-1$. More generally if we are given two numbers $a,b$ the euclidean algorithm gives us a bunch of equations $$ a=q_1b+r_1$$ $$ b=q_2r_1 +r_2$$ $$ r_1 = q_3r_2 + r_3$$ $$ \vdots$$ $$ r_n = q_{n+2}r_{n+1}$$ Where $r_{n+1}$ is then the GCD. To figure out $s$ and $t$, we back track. Multiplying the first equation by $q_2$ and then using the second equation gives us that $$q_2a = (q_2q_1+1)b -r_2$$ we then repeat until we get an expression in terms of a,b and $r_{n+1}$ and this will give us $s$ and $t$.

Answer 3

Here is a standard layout for the extended Euclidean algorithm, which relies on the fact that all intermediate remainders are linear combinations of the given numbers. In addition, if you proceed one step further, you write $0$ as such a linear combination, i.e. you obtain the l.c.m. $$\begin{array}[t]{l@{\qquad}rrrr} \text{Successive Divisions}& r_i & u_i & v_i & q_i\\ \hline & 366 & 1 &0 & \\ 366 = {\color{red}1} \times 305 +\color{blue}{61} & 305 & 0 & 1 & \color{red}{1} \\ \hline 305 = {\color{red}5} \times 61 + \color{blue}{0} & \color{blue}{61} & 1 & -1 & \color{red}5 \\ & \color{blue}{0} & -5 & 6 \\ \hline \end{array}$$ Thus we have $$\gcd(366,305)=61=1\cdot 366-1\cdot305,\quad\operatorname{lcm}(366,305)=5\cdot366=6\cdot305$$