# Finding the solution of the congruence $4x\equiv16\pmod{26}$

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 '16 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 '16 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 '16 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$$

In your question you have done extended Euclidean algorithm with $26$ and $4$. From this you can see that $\gcd(4,26)=2$ and you can also get $$2=4\cdot(-6)+26\cdot1$$ meaning that $$4\cdot(-6)\equiv 2\pmod{26}.$$ Now you can simply multiply both sides by $16/2=8$ to get \begin{gather*} 4\cdot(-48)\equiv 16\pmod{26}\\ 4\cdot4\equiv 4\pmod{26} \end{gather*}

This gives you one solution $x_0=4$. (Of course, you could have easily guessed this solution, since $4\cdot4=16$. But the above also describes an algorithm how to arrive to the solution.)

However, you probably want to find all solutions. In general, $ax\equiv b\pmod n$ has solution only if $d\mid b$ where $d=\gcd(a,b)$. And if you have one solution $x_0$, all solutions can be expressed as $x=x_0+k\frac nd$ where $k\in\mathbb Z$.

In you case $n/d=26/2=13$, so the remaining solutions will differ from the one we have found by multiples of $13$.

So if we look at the congruence classes modulo $26$, all solutions are $x\equiv 4\pmod{26}$ and $x\equiv17\pmod{26}$. (In general we have $d$ congruence classes which solve the given linear congruence.)