discrete mathematics - How to compute $8x equiv 33 pmod{35}$?

How to compute $8x \equiv 33 \pmod{35}$?

I followed this video to solve this problem. Is there a better way?

My solution steps:

Divide both sides by 8:

$$x \equiv \frac{33}{8}^{-1} \pmod{35}$$

$$35 = \frac{33}{8} \cdot 8 +2 \tag 1$$

$$\frac{33}{8}=2\cdot\frac{16}{8}+\frac{1}{8} \tag 2$$

$$2=\frac{1}{8}\cdot8+1$$

Now put $1$ by itself:

$$1=2-\frac{1}{8}\cdot 8 \tag 3$$

Now put $2$ by itself from $(1)$:

$$2 = 35 - \frac{33}{8} \cdot 8 \tag 4$$

Now put $\frac{1}{8}$ by itself from (2):

$$\frac{1}{8} = \frac{33}{8} - 2\cdot\frac{16}{8} \tag 5$$

Now substitute $\frac{1}{8}$ with (5) in (3) and simplify:

$$1=2-\left(\frac{33}{8} - 2\cdot\frac{16}{8}\right)\cdot8$$

$$1=2-\frac{33}{8}\cdot8 - 2\cdot 16 \tag 6$$

Now substitute $2$ with $(4)$ in $(6)$ and simplify:

$$1=35-\frac{33}{8}\cdot8-\frac{33}{8}\cdot8-\left(35-\frac{33}{8}\cdot8\right) \cdot 16$$

$$1=17\cdot(35)-\frac{33}{8}\cdot\left(8\cdot8\cdot8\cdot16\right)$$

The solution is usually between $0$ to $35$. However, we get $(-8\cdot8\cdot8\cdot16)$, which is it too small..

Can anyone tell me where I went wrong?

Answer

We wish to find $x$ such that $8x \equiv 33 \pmod{35}$.

Since $8$ and $35$ are relatively prime, we can use the extended Euclidean algorithm to express their greatest common divisor $1$ as a linear combination of $8$ and $35$. We first use the Euclidean algorithm to solve for the greatest common divisor of $8$ and $35$.

$$\begin{align*} 35 & = 4 \cdot 8 + 3\\ 8 & = 2 \cdot 3 + 2\\ 3 & = 1 \cdot 2 + 1\\ 2 & = 2 \cdot 1 \end{align*}$$

We now work backwards to solve for $1$ in terms of $8$ and $35$.

$$\begin{align*} 1 & = 3 - 1 \cdot 2\\ & = 3 - 1 \cdot (8 - 2 \cdot 3)\\ & = 3 \cdot 3 - 1 \cdot 8\\ & = 3 \cdot (35 - 4 \cdot 8) - 1 \cdot 8\\ & = 3 \cdot 35 - 13 \cdot 8 \end{align*}$$
Since $3 \cdot 35 - 13 \cdot 8 = 1$, $$-13 \cdot 8 \equiv 1 \pmod{35}$$ If we multiply both sides of the congruence by $33$, we obtain
$$\begin{align*} 33 \cdot -13 \cdot 8 & \equiv 33 \pmod{35}\\ -429 \cdot 8 & \equiv 33 \pmod{35}\\ (-13 \cdot 35 + 26) \cdot 8 & \equiv 33 \pmod{35}\\ 26 \cdot 8 & \equiv 33 \pmod{35} \end{align*}$$
Hence, $x \equiv 26 \pmod{35}$.

Check: If $x \equiv 26 \pmod{35}$, then $8x \equiv 8 \cdot 26 \equiv 208 \equiv 5 \cdot 35 + 33 \equiv 33 \pmod{35}$.

Note that this is a modification of Thomas Andrews' excellent answer and an elaboration on Bernard's answer. The theorem that states that we can express the greatest common divisor of two integers as a linear combination of those integers is known as Bezout's identity.