Solve $33x≡9$ (mod 29)

Question

I'm having trouble solving congruences. I can't seem to find a method (a series of steps) to follow in order to find the solutions of a linear congruence. In particular, I have $33x≡9$ (mod 29). My thoughts: gcd (33,29) $=1$, so there is one solution. I don't know what to do next (I tried using Euclid's algorithm...). Thanks

Answer 1

We have $$33=4\mod29$$ and $$4^{-1}=22\mod29$$ because $4(22)=88=29*3+1$. Therefore the answer is $$9*22=198=24\mod29$$

Answer 2

$$\begin{align} 33x=29y+9 & =>4x=29(y-x)+9 \\ & => y-x=2k+1\\ & =>2x=29k+19\\ & => k=2n+1\\ & => x=29n+24.\end{align} $$

Answer 3

Hint $\ {\rm\ mod}\ 29\!:\ x\equiv \dfrac{9}{33}\equiv \dfrac{-20}{4}\equiv -5\equiv 24$

Such reduction and ad-hoc sign twiddling works quite well for small numbers. For larger numbers one can use the Extended Euclidean Algorithm to invert the denominator. Or one can use Gauss's algorithm, since here the modulus is prime.

Beware $\ $ The use of fractions in modular arithmetic is valid only when the denominator is invertible, i.e. coprime to the modulus. Otherwise the quotient need not be unique, for example mod $\rm\:10,\:$ $\rm\:4\,x\equiv 2\:$ has solutions $\rm\:x\equiv 3,8,\:$ so the "fraction" $\rm\:x \equiv 2/4\pmod{10}\,$ cannot designate a unique solution of $\,4x\equiv 2.\,$ Indeed, the solution is $\rm\:x\equiv 1/2\equiv 3\pmod 5,\,$ which requires canceling $\,2\,$ from the modulus too, since $\rm\:10\:|\:4x-2\iff5\:|\:2x-1.\:$

Generally the grade-school rules of fraction arithmetic apply universally (i.e. in all rings) where the denominators are invertible. This fundamental property will be clarified conceptually when one learns in university algebra about the universal properties of fractions rings and localizations.

Answer 4

The Euclidean algorithm is indeed the method par excellence for computing modular inverses. Or more to the point, the extended Euclidean algorithm, which finds a solution to the equation

$$ 33 u + 29 v = 1$$

for you. (or it would solve $4u + 29v = 1$ for you, if you've already figured out that $33 \equiv 4$ and simplified the problem) (I put $1$ on the right hand side, since you already know the $\gcd$ is $1$)

How does this help you? Well, what happens if you simplify this equality modulo $29$?