1

I'm trying to solve the following eqution:

$ \left\{ \begin{array}{l l} 5x (mod \space m) = 7\\ 7x (mod \space m) = 5 \end{array} \right. $

for $x$ and $m$.

(this is a part from a problem someone gave me to solve: to write a mathematic algorithm, which if gets 7 returns 5 and if gets 5 returns 7. The two obvious solutions are $12-x$ and $35/x$, but now i'm trying to find the modular one).

I tried to use the Chinese remainder theorem but of course it didn't work. because the theorem need all the moduluses (the $m$s) to be coprime and here both are the same m.

I also tried to use the fact that the following is true:

$ \left\{ \begin{array}{l l} m \space|\space 7-5x\\ m\space|\space5-7x \end{array} \right. $

But i don't know how to continute from here.

Thank you for your help.

or523
  • 279
  • 2
  • 11

2 Answers2

2

Think of it like simultaneous equations.

$5x \equiv 7\pmod m$, so $35x \equiv 49 \pmod m$.

$7x \equiv 5\pmod m$, so $35x \equiv 25 \pmod m$.

So we know that $24\equiv 0 \pmod m$.

Can you solve it from here?

user11977
  • 1,416
2

Hint $\ {\rm mod}\ m\!:\ 49\equiv 35x\equiv 25\,\Rightarrow\,24\equiv 0.\,$ Notice $\,{\rm mod}\ 24\!:\ 5^2\equiv 1\equiv 7^2\,$ therefore we have $ 5x\equiv 7\!\!\overset{\times\ 5}\iff x\equiv 5(7)\equiv 11,\,$ and $\,\ 7x\equiv 5\!\!\overset{\times\ 7}\iff x\equiv 7(5)\equiv 11,\,$

Bill Dubuque
  • 272,048