# Linear congruences $2X\equiv9\pmod{26},\pmod{25}$

May double that of a natural number let rest $$9$$ when divided by $$26$$? And when divided by $$25$$?

I tried:

$$2X\equiv9\pmod{26}$$ As $$(26,2)=2$$ and $$2\nmid9$$ then the congruence linear not admits solution. So far, everything ok!

However in $$2X\equiv9\pmod{25}$$ As $$(25,2)=1$$ we assume that the congruence a single solution.

I tried to find the solution using Diophantine equations, however, observe $$2X\equiv9\pmod{25}\Longrightarrow25\mid2X-9\Longrightarrow\\2X-9=25k\Longrightarrow\fbox{2X-25k=9}$$

I'm on the right track?

How do I proceed if yes.

• Can you reword the question please? It is very hard to understand. Oct 9, 2013 at 19:33
• @copper.hat I want to find the solution to $$2X\equiv9\pmod{25}$$ Oct 9, 2013 at 19:37

Hint

$$2 \cdot 13 \equiv 26 \equiv 1 \pmod{25}$$

So, multiplication by 13 cancels $2$ in $\pmod{25}$.

Alternately Use the Extended Euclidian Algorithm to solve $2a+25b=1$ and multiply it by $9$ to get a solution to your Diophantine equation.

• Not got the idea, use Diophantine equations again? Oct 9, 2013 at 19:38
• Yes, then $$x=17$$ Oct 9, 2013 at 19:42

You're making it too complicated, I'm afraid. $2X\equiv9\pmod{25}$ is equivalent to $2X\equiv34\pmod{25}.$ Since $(2,25)=1,$ then we can conclude that $2$ has a multiplicative inverse modulo $25$ ($13$, in particular, but it isn't necessary to know this to complete the problem). This allows us to effectively "divide by $2$" on both sides of the congruence $2X\equiv34\pmod{25},$ giving us the answer.

• Not got the idea, use Diophantine equations again? Oct 9, 2013 at 19:36
• From a Diophantine point of view, note that the following are equivalent: \begin{align}2X-9 &= 25k\\13(2X-9) &= 13(25k)\\26X-117 &= 25\cdot13k\\X-17+25\cdot(X-4) &= 25\cdot13k\\X-17 &= 25(13k-X+4)\end{align} Oct 9, 2013 at 19:43