Take the 2-minute tour ×

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|improve this question

1 Answer 1

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|improve this answer

Your Answer


