Exercises — Extended Euclidean algorithm

The base rows never involve division — they just record "$a$ is one copy of $a$" and "$b$ is one copy of $b$". $(r_0,x_0,y_0)=(100,1,0),(r_1,x_1,y_1)=(28,0,1).$ Check the meaning: $1\cdot 100+0\cdot 28=100=r_0$ ✓ and $0\cdot 100+1\cdot 28=28=r_1$ ✓.

The gcd is the last non-zero remainder, so $\gcd (a,b)=6$. The Bézout coefficients come from that same row: $x=2,y=-7$, giving $2a-7b=6$. (This is exactly the "stop at the right row" rule — never the zero row.)

Quotients: $\lfloor 99/78\rfloor =1$, $\lfloor 78/21\rfloor =3$, $\lfloor 21/15\rfloor =1$, $\lfloor 15/6\rfloor =2$, $\lfloor 6/3\rfloor =2$. Result: $\gcd (99,78)=3$, with $x=-11,y=14$. Check: $99(-11)+78(14)=-1089+1092=3$ ✓.

We want $x$ with $17x\equiv 1(\mathrm{mod}60)$. Run Extended Euclidean on $(60,17)$ — the coefficient of $17$ in $60y+17x=1$ is the inverse.

So $60\cdot 2+17\cdot (-7)=120-119=1$. The coefficient of $17$ is $-7$. Reduce mod $60$: $-7+60=53$. Answer: $17^{-1}\equiv 53(\mathrm{mod}60)$. Check: $17\cdot 53=901=15\cdot 60+1$ ✓.

A solution exists iff $\gcd (99,78)$ divides the right side. From 2.1, $\gcd =3$, and $3\mid 12$ (since $12/3=4$), so solutions exist. We already have the Bézout combination $99(-11)+78(14)=3$. Multiply the whole equation by $12/3=4$: $99(-11\cdot 4)+78(14\cdot 4)=3\cdot 4=12.$ Particular solution: $x=-44,y=56$. Check: $99(-44)+78(56)=-4356+4368=12$ ✓.

Once one particular solution $(x_0,y_0)=(-44,56)$ is known, all solutions come from sliding along the line while staying on integers. The step sizes are $b/g$ and $a/g$ where $g=\gcd$: $\frac{b}{g}=\frac{78}{3}=26,\frac{a}{g}=\frac{99}{3}=33.$ $\boxed{x=-44+26t,y=56-33t,t\in \mathbb{Z}}$ Why these steps? Adding $26$ to $x$ adds $99\cdot 26$ to the left; subtracting $33$ from $y$ subtracts $78\cdot 33$. Since $99\cdot 26=78\cdot 33=2574$, the two changes cancel — the equation still holds. Using $b/g$ (not $b$) guarantees we hit every integer solution, not just some. Check at $t=1$: $x=-18,y=23$; $99(-18)+78(23)=-1782+1794=12$ ✓.

Write $N=2+5k$ from the first congruence. Substitute into the second: $2+5k\equiv 3(\mathrm{mod}7)\Rightarrow 5k\equiv 1(\mathrm{mod}7).$ We need $5^{-1}(\mathrm{mod}7)$. Extended Euclidean on $(7,5)$:

So $7(-2)+5(3)=1$, hence $5^{-1}\equiv 3(\mathrm{mod}7)$. Then $k\equiv 3\cdot 1=3(\mathrm{mod}7)$, so $k=3$. $N=2+5\cdot 3=17.$ Check: $17=3\cdot 5+2\Rightarrow 17\equiv 2(\mathrm{mod}5)$ ✓; $17=2\cdot 7+3\Rightarrow 17\equiv 3(\mathrm{mod}7)$ ✓. And $0\le 17<35$.

$d=e^{-1}(\mathrm{mod}40)$. Extended Euclidean on $(40,7)$:

$40(3)+7(-17)=120-119=1$. Coefficient of $7$ is $-17$; reduce: $-17+40=23$. Answer: $d=23$. Check: $7\cdot 23=161=4\cdot 40+1\equiv 1(\mathrm{mod}40)$ ✓.

A congruence $ax\equiv c(\mathrm{mod}m)$ has solutions iff $g=\gcd (a,m)$ divides $c$; then there are exactly $g$ solutions mod $m$. Here $a=14,m=100$: $g=\gcd (14,100)=2$, and $2\mid 30$ ✓ — so 2 solutions exist. Divide everything by $g=2$: $7x\equiv 15(\mathrm{mod}50)$. Now $\gcd (7,50)=1$, so invert $7$. Extended Euclidean on $(50,7)$:

$50(1)+7(-7)=1$, so $7^{-1}\equiv -7\equiv 43(\mathrm{mod}50)$. Then $x\equiv 43\cdot 15=645\equiv 645-12\cdot 50=45(\mathrm{mod}50)$. The two solutions mod $100$ are $x=45$ and $x=45+50=95$. Check: $14\cdot 45=630=6\cdot 100+30\equiv 30$ ✓; $14\cdot 95=1330=13\cdot 100+30\equiv 30$ ✓. Answers: $x\in \{45,95\}$.

Let $x$ = number of big jumps, $y$ = number of small jumps. Landing on $1$ means $63x-40y=1.$ (a) Possible? This is a Diophantine equation $63x+40(-y)=1$. Solvable iff $\gcd (63,40)\mid 1$. Since $\gcd (63,40)=1$, yes. Extended Euclidean on $(63,40)$:

$63(7)+40(-11)=441-440=1$. So $x_0=7$ and (matching $63x-40y=1$) $-y_0=-11\Rightarrow y_0=11$. (b) General solution: since $\gcd =1$, $x=7+40t$ and $y=11+63t$ (both must stay $\ge 0$; increasing $t$ from $0$ only grows them, decreasing sends $x$ negative at $t=-1$: $7-40<0$). The smallest non-negative $x$ is at $t=0$. Answer: $x=7$ big jumps and $y=11$ small jumps. Check: $63\cdot 7-40\cdot 11=441-440=1$ ✓. See the jump-line figure below.

The gcd is the last non-zero remainder, and its Bézout coefficients live in that same row. A congruence $ax\equiv c(\mathrm{mod}m)$ is solvable iff ::: $\gcd (a,m)$ divides $c$. To turn a Bézout solution of $ax+by=g$ into a solution of $ax+by=c$, you ::: multiply the whole equation (and both coefficients) by $c/g$. The general Diophantine solution steps $x$ by ::: $b/g$ and $y$ by $-a/g$. A negative inverse coefficient is fixed by ::: adding $m$ until it lands in $[0,m)$.