# Find $k,l$ given $x = 25 + 38k = 59 +69l, \exists k,l \in \mathbb{Z+}$

Find the smallest positive integer solution to the following system of congruence:
$25\pmod{38}\equiv x \equiv 59\pmod{69}$

$x = 25 + 38k = 59 +69l, \exists k,l \in \mathbb{Z+}$

I am not having any idea to solve, and request for help

The only idea that occurs is to use the property of both $k,l$ being positive integers. Expressing the equality of the two, we get:
$25+38k = 59 +69l$
=> $38k = 34 + 69l$
=> $k = \frac{34 + 69l}{38}$
=> $k = \frac{17}{19} + (1+ \frac{31}{38})l$
=> $\frac{17}{19} + \frac{31}{38}l = k - l =$ a positive integer.

So, need check $\frac{34 + 31l}{38}$to be integer value for different values (positive) of $l$, with smallest being the answer for $l$, and $k \gt l$, as $k-l$ is positive.
So, a second question arises: Even if I find smallest value of $l$ it does not mean that there is no smaller value of $k$ that would not be possible for a larger $l$.

• Notice that if $a$ and $b$ are two possible solutions then $a-b$ is a multiple of both $38$ and of $69$. The lowest common multiple of $38$ and $69$ is $2622$. So there is only one answer between $1$ and the lowest common multiple of $2622$. In fact if there is any answer $k$ then all answer will be $k + 2622m$. – fleablood Jan 18 '18 at 17:47

Remember Euclid's Algorithm for determined greatest common divisor.

$69 = 38 + 31$ so $\gcd(69,38) = \gcd(38,31)$

$38 = 31 + 7$ so $\gcd(38,31) = \gcd(31,7)$

$31 = 4*7 + 3$ so $\gcd(31,7) = \gcd(7,3)$

$7 = 2*3 + 1$ so $\gcd(7,3) = \gcd(3,1) = 1$.

If we keep track of how many times we add and subtract we get:

$69 = 38 + 31; 31=69 - 38$

$38 = 31 + 7;7= 38 - 31 = 38 -(69- 38)= 2*38 - 69$.

$31= 4*7 + 3; 3 = 31 -4*7 = (69-38) - 4(2*38 -69) = 5*69 -9*38$

$7 = 2*3 + 1; 1 = 7- 2*3 = (2*38 - 69) - 2(5*69-9*38) = 20*38-11*69$

so $20*38 - 11*69 = 1$.

So there is always a solution to $xk - ym = \gcd(k,m)$

Multiply the expression $20*38 - 11*69 =1$ on both sides by $34$ are you get:

$34*20*38 - 11*34*69 = 34$

$680*38 - 374*69 = 34$

But $680$ and $374$ are such huge numbers. We can get them smaller be subtraction and adding multiples of $38*69$.

$680*38 - 374*69 = 34$

$680*38-690*38 - 374*69 + 69*380 = 34$

$-10*38 + 6*69 = 34$

$-10*38 + 69*38 + 6*69 - 69*38 = 34$

$59*38 -32*69 = 34$

So $25 +59*38 = 59 + 32*69$

is the solution you want.

• Very fine solution. Just need logic behind division of modulus, as each modulus will be having a different residue, multiplier (to make it equal to a given multiple of the given modulus). If that part were described, or hinted; then a complete solution indeed. – jiten Jan 18 '18 at 18:37
• Also, I requested some more parts of the answer at your earlier answer with link: math.stackexchange.com/a/2610178/424260 – jiten Jan 18 '18 at 18:42
• People like you are the soul of MSE. – jiten Jan 18 '18 at 18:45

solving this Diophantine equation we obtain $$k=59+69C$$ and $$l=32+38C$$ where $C$ is a non negative constant note $$38\cdot 59-69\cdot 32=34$$

• But, can you please elaborate how you obtained the values: $66, 36$. Unable to find out. – jiten Jan 18 '18 at 16:35
• ok i 've made a Little typo, sorry it's corrected and i have added a line – Dr. Sonnhard Graubner Jan 18 '18 at 16:45
• I still am confused about $32$ in second line, also why this 'matrix-multiplication' sort of multiplication & subtraction has occurred, is not clear. – jiten Jan 18 '18 at 16:49
• the numbers $32$ and $59$ are Special Solutions of your equation – Dr. Sonnhard Graubner Jan 18 '18 at 16:51
• i hope this will help you! – Dr. Sonnhard Graubner Jan 18 '18 at 17:20

Look up Chinese Remainder Theorem which addresses precisely this.

But if you roll up your sleeves and do it:

$25 + k38 = 59 + 69l$ so

$38k -69l = 34$

$38k - (2*38 - 7)l = 34$

$38(k-2l) + 7l = 34$. Let $m=k-2l$

$38m + 7l = 34$.

$(3+ 5*7)m + 7l = 34$

$3m + 7(5m + l) = 34$. Let $n = 5m+l$.

$3m + 7n = 34$

$3m + 2*3n + n = 34$

$3(m + 2n) + n = 34$. Let $a = m+2n$.

$3a + n = 34$.

Let $a=11; n = 1$. So $a=m+2n; 11=m + 2; m = 9$. and $n= 5m + l; 1=5*9 +l; l = -44$. and $m = k - 2l; 9=k +88; k = -79$.

So $25 - 79*38 = -2977$ and $59 - 44*69=-2977$.

So $-2977\equiv 25 \mod 38$ and $-2977 \equiv 59 \mod 69$.

That's of course not positive but.

$25 - 79*38 = 59- 44*69 \iff$

$25 - 79*38 + 69*38 = 59 - 44*69 + 69*38 \iff$

$25 - 10*38 = 59 - 6*69 \iff$

$25 - 10*38 + 69*38 = 59 - 6*69 + 69*38 \iff$

$25 + 59*38 = 59 + 32*69$

And $25+59*38 = 59 + 32 * 69 =2267$.

$2267\equiv 25\mod 38$ and $2267\equiv 59\mod 69$ and as the lowest common multiple of $38$ and $69$ is $2622$ this is the smallest positive such number.

• It is an answer with thought process clearly shown with meaningful steps to approach the problem from scratch, just hidden is the logic for division of one modulus by another. – jiten Jan 18 '18 at 18:49
• I think it is a super-set of the CRT, as all the 3 quantities ($x_i, a_i, m_i)$ are different. In CRT, $x$ is constant across all the equations. – jiten Jan 18 '18 at 21:12
• $x$ is what you solve for. $x = 25 \mod 38$ and $x = 59 \mod 69$. By CRT $x$ has a unique solution $\mod 38*69$. – fleablood Jan 18 '18 at 21:56