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