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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.