1
$\begingroup$

This is a problem about Diophantine equation.

The problem is the following.

If $ax+by=c$ is solvable and $b\ne0$, then prove that it has a solution $x_0$, $y_0$ with $0 \le x_0 <|b|$

First I thought that $x=x_1-\frac bg k$ , $y=y_1+\frac ag k$, where $g=gcd(a,b)$, $k$ is integer and $x_1$, $y_1$ is initial solution.


But, after this step, I am stuck and can't find what to do next.

Please help me solve this problem!!!

Thank you

$\endgroup$
1
$\begingroup$

You are nearly finished. Let us use a weaker result than the one you quoted. If $(x_1,y_1)$ is a solution, so is $(x_1-bk,y_1+ak)$ for any integer $k$. If $a$ and $b$ are not relatively prime, this does not produce all solutions, but it is enough for our needs.

By the result often called the Division Algorithm, there is a unique $r$, with $0\le r\lt |b|$, and an integer $q$, such that $x_1=q|b|+r$. This $r$ is the $x_0$ that we want. We pick $k=q$ if $b$ is positive, and $k=-q$ if $b$ is negative.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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