1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\alpha a + \beta m = d \implies a (k \alpha) + (-m)(-k\beta) = k\times d$. $\endgroup$ – Math Lover Jul 4 '18 at 18:10
  • $\begingroup$ If $a$ and $m$ have a common divisor, divide with it to get $d=1$.Now find first a solution for the "same equation", where $b$ replaced by $1$. Each such solution leads by multiplication with $b$ to the one for the posted diophantic equation. Now use either the extended Euler method to get the g.c.d., or use continued fractions. Explicitly one can say something if we have that explicit linear diophantine equation... $\endgroup$ – dan_fulea Jul 4 '18 at 20:49
  • $\begingroup$ @dan_fulea This would be a good answer. I would be most inclined to award you an answer if you put it in that form. $\endgroup$ – Prime Jul 4 '18 at 20:50
  • 2
    $\begingroup$ Please give an explicit example, may be simple, or complicated, the one which was leading to the post, or a similar one, i will better illustrate the way to work out details based on this example. The theory is else known, but i personally feel that a discussion like here, en.wikipedia.org/wiki/…, is too dry to help in didactical way, and/or may be not illuminating for -say- 10% of the readers, the ones like me that need a striking example... $\endgroup$ – dan_fulea Jul 4 '18 at 20:57
  • $\begingroup$ Sure. I will provide an edit to my question in $\leq$ $30$ min. $\endgroup$ – Prime Jul 4 '18 at 20:58
2
$\begingroup$

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$.)

$\endgroup$
2
$\begingroup$

Bezout's Identity says that it is possible to solve $$ ax-my=b $$ precisely when $\gcd(a,m)\mid b$. In the example given, $\gcd(33,753)\mid183$.

Using the Extended Euclidean Algorithm as implemented in this answer $$ \begin{array}{r} &&22&1&4&2\\\hline 1&0&1&-1&\color{#C00}{5}&-11\\ 0&1&-22&23&\color{#C00}{-114}&251\\ 753&33&27&6&\color{#C00}{3}&0\\ \end{array} $$ where, below the line, $753$ times the first row plus $33$ times the second row equals the third row, we get that $$ (5)753+(-114)33=3 $$ multiplying by $61$, we get $$ (305)753+(-6954)33=183 $$ Thus, all integer solutions are given by $$ x=-6954+251k $$ for some $k\in\mathbb{Z}$. By adjusting $k$, we can reduce this to $$ x=74+251k $$ for some $k\in\mathbb{Z}$.

$\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.