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

Question

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 1

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.

Answer 2

Your answer isn't really wrong, exactly, since $-8 \times 8 \times 16 = -1024 \equiv 26 \pmod{35}$, and $26$ is in fact the right answer.

However, I'd agree with avid19 that the approach is a bit turgid. It seems more economical, even thinking ad hoc, to find the inverse of $8 \pmod{35}$—that is, to find $k$ such that

$$ 8k \equiv 1 \pmod{35} $$

which we can do by finding $m$ such that

$$ 35m \equiv 7 \pmod{8} $$

Since $35 \equiv 3 \pmod{8}$, we can quickly find that $5 \times 3 \equiv 7 \pmod {8}$, and therefore $5 \times 35 = 175 \equiv 7 \pmod{8}$. Then $8 \times 22 = 176 \equiv 1 \pmod{35}$, so the inverse of $8 \pmod{35}$ is $k = 22$.

Therefore, to obtain $33$, we multiply both sides by $33$: $8 \times 33 \times 22 = 726 \equiv 33 \pmod{35}$. Thus,

$$ x = (33 \times 22) \bmod 35 = 726 \bmod 35 = 26 $$

There are more systematic approaches, but when the numbers are this small, I prefer to think ad hoc. Your mileage may vary.

Answer 3

You can't use fractions in modular equations, as ‘modulo $35$’ (or whatever) is not really about integers, but about congruence classes.

However you can think of congruences as ‘almost equalities’. In particular , numbers which are coprime to the modulus $35$ will have an inverse modulo $35$, thanks to Bézout's identity, which one finds usually with the extended Euclidean algorithm: $$-13\cdot 8+3\cdot 35=1$$ whence $8^{-1}\bmod 35\equiv-13\equiv 22$. So let's multiply both side of the congruence equation by $22$: $$8x\equiv 33\mod35\implies 22\cdot 8x\equiv 22\cdot 33=726\equiv26\mod35.$$

Answer 4

Note that $8\cdot4=-3.$ Therefore, $(8 \cdot 4) \cdot 12=-36=-1$. Hence, $8^{-1}=-48=22$. Then, $x=22 \cdot 33=22\cdot -2=-44=26$.

---

If no quick way springs your mind, you can always resort to Euclid's Algorithm, which ammounts essentially to find, given $a,b$ integers with $\gcd(a,b)=1$, numbers $m$ and $n$ such that

$$ma +nb=1.$$

Note now that, if $b=33$ and $a=8$, then we will have found (taking equalities in the quotient) that

$$1=ma+nb=ma.$$

Answer 5

Why are people proposing trial and error? Solving $8x+35y=1$ is solved via the Euclidean algorithm and back substitution:

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

From this we compute the continued fraction $$\frac{35}{8}=4+\dfrac{1}{2+\dfrac{1}{1+\frac{1}{2}}}$$

The previous convergent $$4+\dfrac{1}{2+\dfrac{1}{1}}=\frac{13}3$$

And we get $35\cdot 3-13\cdot 8 = 1$.

So you need: $$x\equiv (-13)\cdot 33\pmod{35}$$

---

If you want to avoid the continued factions, the classical view starts with the Euclidean algorithm and back-substitution. The last line of the algorithm above gives:

$$3+2(-1)=1$$

Substitute $2=8-3\cdot 2$ and you get:

$$3\cdot 3 + 8(-1)=1$$

Then substitute $3=35-8\cdot 4$ and you get:

$$35\cdot 3 +8\cdot (-13)=1$$

(This is equivalent to the continued faction view, but more direct and it becomes more obvious why it works.)

Answer 6

We have: $8x - 33 = 35k \Rightarrow x = \dfrac{33+35k}{8}=4+4k+\dfrac{1+3k}{8}\Rightarrow 1+3k=8t\Rightarrow k=\dfrac{8t-1}{3}=3t-\dfrac{t+1}{3}\Rightarrow t+1 = 3r\Rightarrow t = 3r-1\Rightarrow k = 3(3r-1)-r = 8r-3\Rightarrow x = 4+4(8r-3)+3r-1 =35r-9, r\in \mathbb{Z}$

Answer 7

Here is a trick, which works nicely for $8$, or any power of $2$.

We want $8x\equiv 33\equiv 68\pmod{35}$. So we want $2x\equiv 17\pmod{35}$, or equivalently $2x\equiv 52\pmod{35}$, giving $x\equiv 26\pmod{35}$.