1
$\begingroup$

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.

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

2 Answers 2

1
$\begingroup$

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.

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

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.

$\endgroup$
2
  • $\begingroup$ Not got the idea, use Diophantine equations again? $\endgroup$ Oct 9, 2013 at 19:36
  • $\begingroup$ 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}$$ $\endgroup$ Oct 9, 2013 at 19:43

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.