Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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? – thefourtheye Dec 30 '12 at 11:45
Look at my edition in my answer – DonAntonio Dec 30 '12 at 11:56
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... :) – thefourtheye Dec 30 '12 at 12:00
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. – DonAntonio Dec 30 '12 at 12:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.