Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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

share|cite|improve this answer
    
@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)}}$$

share|cite|improve this answer
    
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$$

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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