2
$\begingroup$

I have the following relations

$$a x \equiv b \pmod m\;\;,\;\; m y\equiv b \pmod a$$

Now, I need to find the minimum possible positive values for $x$ and $y$.

Extended Euclid Algorithm doesn't guarantee neither minimum nor positive, it seems.

I tried to solve this with Extended Euclid Algorithm as described in Wikipedia. It produces negative results and even if it is positive, it is not the minimum possible.

Please help me understand the method with which I can get the solution.

1 Answers 1

1

It never minds what solutions you get from wikipedia, WA or any other source: if, for instance, $\,x\,$ is a solution to the first equation, then also $\,x+km\,\,,\,\,k\in\Bbb Z\,$ is a solution , so it is enough you take the first positive solution in the aritmetic progression $\,\{x+km\;\;;\;\;k\in\Bbb Z\}\,$ using the formula for the general $\,n-$th term in a AP:

$$a_n=a_1+(n-1)m\Longrightarrow \text{we want to solve the inequality}\,\,\,a_1+(n-1)m>0$$

Added: Note that it doesn't matter at all what element you call $\,a_1\,$ to in the above formula.

For example, say you want to solve $\,3x=7\pmod {16}\,$ , and you get the solution $\,x=-19\,$ , then you solve, deciding that $\,a_1:=-19\,$ :

$$a_1+(n-1)16=-19+(n-1)16>0\Longrightarrow n-1>\frac{19}{16}\Longrightarrow$$

$$\Longrightarrow n-1=2\Longrightarrow n=3\Longrightarrow $$

the first positive element in our progression is $\,a_3=a_1+2\cdot 16=-19+32=13\,$ , which you can easily check.

  • 0
    Thanks @Don. I am trying to solve a problem using a program. The program (this is another program) which evaluates my program is very stringent in terms of time taken to solve. Lets say, the solution which I get is -12765 and the minimum possible value is 5, the program has to spend time till it gets to 5. So, is there any straight forward way to arrive at the solution?2012-12-30
  • 0
    Look at my edition in my answer2012-12-30
  • 0
    I think I can make use of the same idea when number is positive but not the minimum possible. Thanks @Don. I ll try this in my program... :)2012-12-30
  • 0
    Of course you can, @thefourtheye. You only need a subroutine in your program that can tell apart whether the solution you got is positive or negative, in order to know what inequality to solve.2012-12-30