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

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

Dr. Sonnhard Graubner · Answer 1 · 2018-01-18T16:41:19.093

1

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

edited Jan 18 '18 at 16:41

answered Jan 18 '18 at 16:27

Dr. Sonnhard Graubner

95,283

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
But, please tell how they are obtained. I am clueless about those two (special solution) numbers. – jiten Jan 18 '18 at 16:52
Please guide, as a small hint would (I hope) suffice to solve this type of problems, and even for more than $2$ constituent equations. – jiten Jan 18 '18 at 17:03
see here https://www.wikihow.com/Solve-a-Linear-Diophantine-Equation – Dr. Sonnhard Graubner Jan 18 '18 at 17:20
1

i hope this will help you! – Dr. Sonnhard Graubner Jan 18 '18 at 17:20

score 1 · Answer 2 · answered Jan 18 '18 at 17:41

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

score 1 · Accepted Answer · answered Jan 18 '18 at 18:33

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: https://math.stackexchange.com/a/2610178/424260 — jiten, Jan 18 '18 at 18:42

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

3 Answers3