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

What is the best way of solving for $x,y\in\mathbb N$ given the conditions $\begin{cases}x\mid y+a\\y\mid x + b\end{cases}$? The letters $a,b\in\mathbb N$ denote constant known numbers.

The case when $x,y\in\mathbb Z$ doesn't quite interest me as it seems to provide an infinite amount of solutions. The proof of that that I've thought of is:

Let $\begin{cases}y+a=xk\\x+b=yl\end{cases}$, where $k,l\in\mathbb Z$. By adding the equalities, we can see that $$y(l-1)+x(k-1)=a+b$$

Now let $\begin{cases}\alpha=y(l-1)\\\beta=x(k-1)\\c=a+b\end{cases}$. So we have that $$\alpha + \beta = c$$ We can all notice that this equation has an infinite amount of solutions. Q.E.D.

Regarding the case when $x,y\in\mathbb N$, I've found a solution method that is nearly identical to the one shown above. We have the equation $$y(l-1)+x(k-1)=a+b$$ The fact that we're dealing with natural numbers lets us find all the solutions. The amount of them in this case is always finite. By letting $l=1$, then $l=2$, $l=3$, etc. I could search for all the solutions, but it'd be quite lengthy depending on the size of $a$, $b$.

An approach using inequalities doesn't seem to work. The inequalities $\begin{cases}y+a\ge x\\x+b\ge y\end{cases}$ don't seem to provide great benefits and probably won't let us solve the problem.

So my question is:

What is the best way you can think of of solving such problems?

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

First, suppose $d=gcd(a,b)=1$, if not, cancel $d$ and start afresh. In the latter case, the required solutions are; $x=x'd$ and $y=y'd$ where $x'$ and $y'$ are the solutions obtained after the cancellation of $d$. Since $gcd(a,b)=1$, there exist integers $p$ and $q$ such that $pa+qb=1$ or generally, $(p+nb)a+(q-na)b=1$ for any integer $n$. Since $a=xk-y$ and $b=yl-x$ we obtain, $(p+nb)(xk-y)+(q-na)(yl-x)=1$, or $[(p+nb)k-(q-na)]x+[(q-na)l-(p+nb)]y=1$. Recall, from your result above, $y(l-1)+x(k-1)=a+b$. From the last two equations multiply, the former by $a+b$ and equate coeffients of $x$ and $y$ respectively to obtain; $[(q-na)l-(p+nb)](a+b)=l-1$ and $[(p+nb)k-(q-na)](a+b)=k-1$. With numerical values substituted, $n$ can be eliminated from both equation, and the resulting diophantine equation can then be solved for $l$ and $k$.

share|cite|improve this answer

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.