Solve the congruence


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}}$

  • $\begingroup$ @ThomasAndrews I have edited my answer. Thanks for your help. $\endgroup$ – 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)}}$$

  • $\begingroup$ By the way, does anyone know how to format \pmod so that the parenthesis are adjustable? $\endgroup$ – Elliot G Jan 25 '16 at 18:28
  • $\begingroup$ 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.) $\endgroup$ – 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.