Use extended Euclidean algorithm to find $j,k$ such that $52j+15k=3$

Question

Is this questions suggesting that $\gcd(52,15)=3$ i.e. $52j+15k=3$? if it is then why am I getting $1$ when I am computing the $\gcd$. $$ \gcd(52,15) = \gcd(15,7) = \gcd(7,1) = \gcd(1,0) = 1 $$ Am I going in the right direction or not?

Answer 1

First, we find $\gcd(\color{#c00}{52}, \color{#0a0}{15})$ using the Euclidean Algorithm. $$ \begin{align*} \color{#c00}{52}&=3 * \color{#0a0}{15} + \color{#00c}{7}\\ \color{#0a0}{15}&=2 * \color{#00c}{7} + 1\\ \color{#00c}{7}&=1*\color{#00c}{7}+0 \end{align*} $$ So, $\gcd(\color{#c00}{52}, \color{#0a0}{15})=1$. You correctly calculated the $\gcd$ to be one. Now we rewrite the previous equations in terms of the remainders so we can substitute them back in: $$ \begin{align*} \color{#00c}{7}&=\color{#c00}{52}-3*\color{#0a0}{15}\\ 1&=\color{#0a0}{15}-2*\color{#00c}{7} \end{align*} $$ which gives $$ \begin{align*} 1&=\color{#0a0}{15}-2*(\color{#c00}{52}-3*\color{#0a0}{15})\\ 1&=\color{#0a0}{15}-2*\color{#c00}{52}+6*\color{#0a0}{15}\\ 1&=\color{#00c}{7}*\color{#0a0}{15}-2*\color{#c00}{52}. \end{align*} $$ To finish, we multiply the whole equation by $3$: $$ \begin{align*} 3(1)&=3(\color{#00c}{7}*\color{#0a0}{15}-2*\color{#c00}{52})\\ 3&=3*\color{#00c}{7}*\color{#0a0}{15}-3*2*\color{#c00}{52}\\ 3&=21*\color{#0a0}{15}-6*\color{#c00}{52}. \end{align*} $$ Thus, we have that $j=-6$ and $k=21$.