0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – fleablood Jan 18 '18 at 17:47
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jiten Jan 18 '18 at 18:37
  • $\begingroup$ Also, I requested some more parts of the answer at your earlier answer with link: math.stackexchange.com/a/2610178/424260 $\endgroup$ – jiten Jan 18 '18 at 18:42
  • $\begingroup$ People like you are the soul of MSE. $\endgroup$ – jiten Jan 18 '18 at 18:45
1
$\begingroup$

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

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – jiten Jan 18 '18 at 18:49
  • $\begingroup$ 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. $\endgroup$ – jiten Jan 18 '18 at 21:12
  • 1
    $\begingroup$ $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$. $\endgroup$ – fleablood Jan 18 '18 at 21:56

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.