To compute $gcd(25, 11)$, Euclid's algorithm would proceed as follows: $$\underline{25} = 2 \cdot \underline{11}+3$$ $$\underline{11} = 3 \cdot \underline{3}+2$$ $$\underline{3} = 1 \cdot \underline{2}+1$$ $$\underline{2} = 2 \cdot \underline{1}+0$$ Thus $gcd(25,11)$ = $gcd(11,3)$ = $gcd(3,2)$ = $gcd(2,1)$ = $gcd(1,0)=1$
*THIS PART I DO NOT UNDERSTAND CAN SOMEONE GO OVER IT PLEASE *
To find $x$ and $y$ such that $25x+11y=1$, we start by expressing 1 in terms of the last pair (1,0). Then work backwards and express it in terms of (2,1) , (3,1), (11,3), and finally (25,11). The first step is: $$1= 1-0$$ to rewrite this in terms of (2,1), we use the substitution $0 = 2-2 \cdot 1$ from the last line of the gcd calculation to get:** $$1 = \underline{1}-(\underline{2} -2 \cdot\underline{1}) = -1 \cdot \underline{2} + 3 \cdot \underline{1}$$** $$$$
how did they get the last statement of the expression i understand that if you evalute it it will equal 1 but to me it seems like they pulled number out of thin air , every time i try to do it, i end up simplifying and i dont get quiet what they got? how do i come up with this statement: $-1 \cdot \underline{2} + 3 \cdot \underline{1}$ from the previosu statement: $\underline{1}-(\underline{2} -2 \cdot\underline{1})$
(they keep going):
The second last line of the gcd calculation tells us that $1=3-1 \cdot 2$. Substituting:
$$ 1 = -1 \cdot \underline{2} + 3( \underline{3} - 1 \cdot \underline{2} = 3 \cdot \underline{3} - 4 \cdot \underline{2} ) $$
continuing in this same way with substitutions $2=11-3 \cdot3 $ and $3 = 25-2 \cdot 11$ gives:
$$1= 3 \cdot \underline{3} - 4(\underline{1} - 3 \cdot \underline{3}) = -4 \cdot \underline{11} + 15 \cdot \underline{3} = -4 \cdot \underline{11} + 15 (\underline{25} - 2 \cdot {11}) = 15 \cdot \underline{25} - 34 \cdot \underline{11}$$ We're done: $15 \cdot 25 - 34 \cdot 11 =1$, so $x=15$ and $y=-34$
Perhaps it would actually be easier to see what’s going on in a symbolic example. Suppose that we applied the algorithm to $m$ and $n$ and get:
$$\begin{align*} n&=q_0m+r_0\tag{1}\\ m&=q_1r_0+r_1\tag{2}\\ r_0&=q_2r_1+r_2\tag{3}\\ r_1&=q_3r_2+0\tag{4}\\ \end{align*}$$
We know then that $\gcd(n,m)=\gcd(m,r_0)=\gcd(r_0,r_1)=\gcd(r_1,r_2)=\gcd(r_2,0)=r_2$. We start by expressing $r_2$ as an integer combination of that last pair, $r_2$ and $0$:
$$r_2=1\cdot r_2-1\cdot 0\;.\tag{5}$$
We can solve $(4)$ for $0$ in terms of $r_1$ and $r_2$ to get $$0=1\cdot r_1-q_3\cdot r_2$$ and substitute this into $(5)$ to eliminate the $0$:
$$\begin{align*} r_2&=1\cdot r_2-1\cdot(1\cdot r_1-q_3\cdot r_2)\\ &=-1\cdot r_1+(1+q_3)\cdot r_2\;,\tag{6} \end{align*}$$
expressing $r_2$ as an integer combination of $r_1$ and $r_2$. We can now solve $(3)$ for $r_2$ in terms of $r_0$ and $r_1$ to get
$$r_2=1\cdot r_0-q_2\cdot r_1$$
and substitute this into the righthand side of $(6)$ to eliminate the $r_2$ on the righthand side:
$$\begin{align*} r_2&=-1\cdot r_1+(1+q_3)\cdot(1\cdot r_0-q_2\cdot r_1)\\ &=(1+q_3)\cdot r_0-(1+(1+q_3)q_2)\cdot r_1\\ &=(1+q_3)\cdot r_0-(1+q_2+q_3q_2)\cdot r_1\;,\tag{7} \end{align*}$$
expressing $r_2$ as an integer combination of $r_0$ and $r_1$. Keep going in the same way. The next step is to eliminate $r_1$ from the righthand side of $(7)$ by solving $(2)$ for $r_1$ to get $r_1=1\cdot m-q_1\cdot r_0$ and substituting into $(7)$ to get
$$\begin{align*} r_2&=(1+q_3)\cdot r_0-(1+q_2+q_3q_2)\cdot(1\cdot m-q_1\cdot r_0)\\ &=-(1+q_2+q_3q_2)\cdot m+\big((1+q_3)+(1+q_2+q_3q_2)q_1\big)\cdot r_0\\ &=-(1+q_2+q_3q_2)\cdot m+(1+q_3+q_1+q_2q_1+q_3q_2q_1)\cdot r_0\;.\tag{8} \end{align*}$$
Finally, solve $(1)$ for $r_0$ to get $r_0=1\cdot n-q_0\cdot m$ and substitute that into the righthand side of $(8)$ to eliminate $r_0$ from that side of the equation:
$$\begin{align*} r_2&=-(1+q_2+q_3q_2)\cdot m+(1+q_3+q_1+q_2q_1+q_3q_2q_1)\cdot(1\cdot n-q_0\cdot m)\\ &=(1+q_3+q_1+q_2q_1+q_3q_2q_1)\cdot n\\ &\qquad-(1+q_2+q_3q_2+q_0+q_3q_0+q_2q_1q_0+q_3q_2q_1q_0)\cdot m\;, \end{align*}$$
finally expressing the gcd $r_2$ as an integer combination of the original integers $n$ and $m$.
It’s just repeated substitution to eliminate the remainders $r_k$ until only $n$ and $m$ are left. (And it’s much easier when you’re working with numbers.)