# Finding the solution of a congruence.

Solve the congruence

$$4x\equiv16\mod{26}.$$

How do I find the solution to this? I have tried by the euclidean algorithm but the gcd is not $1$ so it doesn't work.

\begin{align} 26&=&6&\times4&+2\\ 4&=&2&\times2&+0 \end{align}

Note: I understand we can see that $4$ and $17$ are solutions but how would I work this out algorithmically?

-

While solving congruences, it is better to convert the congruence into the division algorithm form and then go for solving.

$4x \equiv 16 \pmod{26} \Rightarrow 26 \: | \: 4x-16$

It finally reduces down to $13 \: | \: 2(x-4) \Rightarrow 13 \: | \: (x-4)$.

By Euclidean algorithm, we have unique integer $k$ such that $x-4=13k$.

So required solution is $\color{red}{x=13k+4} \:, \:\color{blue}{k \in \mathbb{Z}}$

-
@ThomasAndrews I have edited my answer. Thanks for your help. – SchrodingersCat Jan 26 at 5:30

You have to reduce factors, first. $26$ and $4$ are not relatively prime, but their common factor divides $16$, so you can solve $2x\equiv 8\pmod {13}$.

More generally, if you want to solve $ax\equiv b\pmod{d}$, you need $\gcd(a,d)$ to be a factor of $b$ (or else there are no solutions) and then divide $\gcd(a,d)$ from all of them to get an equation:

$$\frac{a}{\gcd(a,d)}x\equiv \frac{b}{\gcd(a,d)}\pmod{\frac{d}{\gcd(a,d)}}$$

-
By the way, does anyone know how to format \pmod so that the parenthesis are adjustable? – Elliot G Jan 25 at 18:28
alternatively why not use the euclidean algorithm on the original system i.e., (generate and) solve $2 = 4x' +26y'$, and set $x = 8x'$. (My point is 'algorithmic' in that you have to calculate/know the gcd anyway in general.) – peter a g Jan 25 at 18:28

The relation can be "translated" into: $$26\mid 4x-16$$ or equivalently $$4x=16+26k\text{ for }k\in\mathbb Z$$ Dividing both sides by factor $2$ results in $$2x=8+13k\text{ for }k\in\mathbb Z$$ Evidently there will be solutions for $x\in\mathbb Z$ if and only if $k$ is even.

Stating $k=2m$ we first find: $$2x=8+26m\text{ for }m\in\mathbb Z$$Dividing both sides by factor $2$ again we end up with:$$x=4+13m\text{ for }m\in\mathbb Z$$

-