How to solve linear congruences using the Extended Euclidean Algorithm?

Here is the complete solution using the Extended Euclidean Algorithm. **Problem:** Solve $17x \equiv 3 \pmod{29}$. **Step 1: Run the Euclidean algorithm on $29$ and $17$.** \begin{align*} 29 &= 1 \cdot 17 + 12 \\ 17 &= 1 \cdot 12 + 5 \\ 12 &= 2 \cdot 5 + 2 \\ 5 &= 2 \cdot 2 + 1 \\ 2 &= 2 \cdot 1 + 0 \end{align*} The GCD is $1$, so $17$ has an inverse modulo $29$. **Step 2: Extended algorithm (back-substitution).** From the second-last line: $1 = 5 - 2 \cdot 2$ Substitute $2 = 12 - 2 \cdot 5$: $1 = 5 - 2(12 - 2 \cdot 5) = 5 \cdot 5 - 2 \cdot 12$ Substitute $5 = 17 - 12$: $1 = 5(17 - 12) - 2 \cdot 12 = 5 \cdot 17 - 7 \cdot 12$ Substitute $12 = 29 - 17$: $1 = 5 \cdot 17 - 7(29 - 17) = 12 \cdot 17 - 7 \cdot 29$ **Step 3: Extract the inverse.** $12 \cdot 17 - 7 \cdot 29 = 1$ implies $12 \cdot 17 \equiv 1 \pmod{29}$. So the inverse of $17$ modulo $29$ is $12$. **Step 4: Solve the congruence.** Multiply both sides by $12$: $$17x \equiv 3 \pmod{29} \implies x \equiv 12 \cdot 3 \equiv 36 \equiv 7 \pmod{29}$$ **Answer:** $\boxed{x \equiv 7 \pmod{29}}$. **Verification:** $17 \cdot 7 = 119 = 4 \cdot 29 + 3 \equiv 3 \pmod{29}$ ✓