Can we always solve this as a Linear Diophantine Equation

elementary-number-theorylinear-diophantine-equations

Given $d=gcd(a,m) \mid b$,
is it always possible to solve a congruence equation in the form

$$ax+(-m)y=b$$

Since I have expressed the problem as a linear diophantine equation,
can't I just solve a problem like this using backwards substitution and the Extended-Euclidean Algorithm?

Is it possible to solve this without the use of continued fractions or just guessing?

Also, supposing I can solve this using backwards substitution and the Extended-Euclidean Algorithm, if the $gcd\neq$ $1$, then I have multiple solutions to the diophantine equation. How would I find these solutions particularly (not looking for the generalized form here)

Any and all help would be appreciated. I do have a specific example, but I am asking more about an approach. I have tried this problem, but would like to save myself a bit of time if someone can kind of point me in the correct direction.

Edit:

I have included a specific problem that has served as strong motivation for me posting this.

The problem:

$$33x\equiv183\pmod{753}$$ Obviously, by the Euclidean Algorithm, we know that the $gcd=3$ and we know that $3$|$183$ $=$ $61$ We are interested in all solutions in the integers.

I hope this serves as some context and motivation for my question.

Best Answer

Thanks for giving an explicit example. I will try to solve in $\Bbb Z$ the equation as a human (so that the idea becomes transparent): $$ 33x+753y=183\ ,\qquad x,y\in\Bbb Z\ . $$ (1) We note first that the g.c.d. of $33$ and $753$ is $(33,753)=3$. A necessary condition to solve is that $3$ also divides the RHS, $183$, yes, this is the case, and $183/3=61$. So we divide by $3$ in both sides and get the simpler equation: $$ 11x+251y=61\ ,\qquad x,y\in\Bbb Z\ . $$ (2) In the new situation, the relevant gcd is $(11,251)=1$. We will solve first $$ 11X+251Y=1\ ,\qquad X,Y\in\Bbb Z\ . $$ It is clear than that for each such solution $(X,Y)$ setting $x=61X$ and $y=61Y$ we get a solution of the initial equation. So let us get a particular solution $X,Y$ first. For this, we build the continued fraction and the convergents for $251/11$, here explicitly: $$ \frac{251}{11} =22+\frac9{11} =22+\frac1{11/9} =22+\frac1{1+\frac 29} =22+\frac1{1+\frac 1{9/2}} =22+\frac1{1+\frac 1{4+\frac12}} =[22;1,4,2] \ . $$ (This is a systematic way to use the repeated euclidean algorithm in one relation.) The "convergents" are fractions that approximate better and better (up to given denominators) the fraction we started with. $$ \begin{aligned} [22;]&=22\ ,\\ [22;1]&=22+\frac 11=23\ ,\\ [22;1,4]&=22+\frac 1{1+\frac 14}=22+\frac 45=\frac{114}5\ ,\\ [22;1,4]&=\frac{251}{11}\ . \end{aligned} $$ The theory of continued fractions insures that the difference of two successive convergents has as denominator the product of the denominators of the fractions in the difference, and the numerator is alternatively $\pm 1$. In our case, using computer power to make typing easier, sage:

sage: a = 251/11
sage: a.continued_fraction()
[22; 1, 4, 2]
sage: a.continued_fraction().convergents()
[22, 23, 114/5, 251/11]
sage: 22-23
-1
sage: 23-114/5
1/5
sage: 114/5-251/11
-1/55

We only need the last relation, consider in $$ \frac{114}5-\frac {251}{11}=\frac{-1}{5\cdot 11} $$ the computation for the numerator, $$ 11\cdot 114-251\cdot 5=-1\ , $$ and from it we can extract a particular solution $$(X_0,Y_0)=(-114,5)$$ of $11X+251Y=1$. Each other solution satisfies $$11(X-X_0)+251(Y-Y_0)=0\ ,$$ so the only way to arrange this is $(X-X_0)=251k$, $(Y-Y_0)=-11k$, $k\in \Bbb Z$. (It is premature to apply it here, but it is good to observe it here.) Sometimes, because of this, the particular solution is (re)arranged to have the $X$-part in the range $[0,251)$ and/or the $Y$-part in the range $[0,11)$. Check:

sage: 11*(-114) + 5*251
1

(3) We pass from the particular solution for $11X+251Y=1$ above to a particular solution for $11x+251y=61$. We compute $5\cdot 61=305$, and reduce modulo $11$ to get either $8$ or $-3$. For both we get then a solution...

sage: ( 61 - 251*8 )/11
-177
sage: ( 61 - 251*(-3) )/11
74

Here is the right point to mention that any other solution for the $x$-part differs from the above special one by a multiple of $251$.

(4) This solves the problem after the division with gcd $=3$, we can take $x=74$ modulo $251$. And also the initial problem, also taking $x=74$ modulo $753$.

I did not try to do a quick expedition of the human facts for the human solution, but even if... there would have been maybe the half of the line. This is somehow too much, compared with the following solutions of the same problem:

sage: R = Zmod(251)
sage: R(61)/R(11)
74
sage: R(11)^(-1) * R(61)
74
sage: R.is_field()
True

sage: R = Zmod(753)
sage: [ x for x in R if R(33) * x == R(183) ]
[74, 325, 576]

(There are three solutions modulo $753$. We have found the $74$, the next ones are obtained by adding $251$.)

Related Question