8
$\begingroup$

Largest number that leaves same remainder while dividing 5958, 5430 and 5814 ?


$$5958 \equiv 5430 \equiv 5814 \pmod x$$ $$3\times 17\times 19 \equiv 5\times 181\equiv 3\times 331\pmod x$$ $$969 \equiv 905\equiv 993\pmod x$$

After a bit of playing with the calculator, I think the answer is $48$ but I don't know how to prove it.

Sorry if the answer is too obvious, I am still trying to wrap my head modular arithmetic and not very successful yet.It would be great help if anybody would give me some hints on how to proceed ahead. Thanks. $\ddot \smile$

$\endgroup$
  • $\begingroup$ The first congruence corresponds to the title. What do you mean with the other two congruences? Are you solving three problems at once here? $\endgroup$ – user236182 Aug 25 '16 at 23:13
  • 3
    $\begingroup$ I see you divided all the terms by 6. That's .. not really okay. 12 = 22 mod 10 but 6 != 11 mod 10. $\endgroup$ – fleablood Aug 26 '16 at 0:03
20
$\begingroup$

Okay, first we set it up even though we have no idea where we are going.

$5958 \equiv n \mod x$

$5430 \equiv n \mod x$

$5814 \equiv n \mod x$.

Then we noodle a bit to make it smaller and more pallatable.

$5958 - 5814 = 144 \equiv 0 \mod x$

$5814 - 5430 = 384 \equiv 0 \mod x$

and

$5958 - 5430 = 528 \equiv 0 \mod x$

Well, now it's very clear that $x$ is a common divisor and all we have to do is find the $x = \gcd(144,384, 528)$

$x = \gcd(144 = 2^43^2, 384 = 2^7*3, 528 = 2^4*3*11) = 2^4*3 = 48$.

And we're done.

$\endgroup$
  • 11
    $\begingroup$ we could noodle a bit further to get 528 - 384 = 144 = 0 mod x and so on and accidentally stumble onto the Euclidean Algorithm completely inadvertently. $\endgroup$ – fleablood Aug 25 '16 at 23:35
  • 3
    $\begingroup$ ... then we wonder briefly "well, what was the remainder anyway" and then decide "screw it, I don't care". $\endgroup$ – fleablood Aug 25 '16 at 23:38
  • 3
    $\begingroup$ ... then we decide the heck with it and calculate that the remainder was $n=6$. $\endgroup$ – fleablood Aug 25 '16 at 23:39
  • $\begingroup$ Thanks for clearing my doubts through this answer and the comment below the question. :) $\endgroup$ – A---B Aug 26 '16 at 0:14
  • 1
    $\begingroup$ Don't really have any recomendations. Any number theory book covers it. Ivan Niven's book was the one I learned from but any will do. $\endgroup$ – fleablood Aug 26 '16 at 18:03
7
$\begingroup$

Since $5958 \equiv 5430 \mod{x}$, then $x | 5958 -5430 = 528$. Likewise $x | 5958 - 5814 = 144$ and $x | 5814 - 5430 = 384$. So $x$ is a common divisor of $528,$ $144,$ and $384$. So you want $x=\gcd(528, 144, 384) = 48$.

$\endgroup$
  • $\begingroup$ Thanks for the answer. $\ddot \smile$ $\endgroup$ – A---B Aug 26 '16 at 0:14
3
$\begingroup$

Let the number leaving the same remainder be $a$ and the remainder be $b$.

So, $\gcd(5958-a,5430-a,5814-a)=b$

Note that

$(1)$ $$\gcd(x,y,z)=\gcd{\gcd(x,y)\gcd(y,z)}$$ $(2)$ $$\gcd(x,y) \mid x-y$$

$\endgroup$
  • $\begingroup$ thanks for the hints, took me a while but got them at last $\ddot \smile$ $\endgroup$ – A---B Aug 26 '16 at 0:18
-1
$\begingroup$

The only "small" solutions (below 10000000) seem to be ${1,2,3,4,6,8,12,16,24,48}$. Of course, you can add $lcm({5958, 5430, 5814}) = 1741612770 $ to a solution and get another, bigger one.

The set above was found by letting do the computer what a computer can do best: Computing stuff. Here is the Haskell Code I used:

[x | x <- [1..870806385 + 49], 5958 `mod` x == 5430 `mod` x, 5430 `mod` x == 5814 `mod` x]

$\endgroup$
  • 1
    $\begingroup$ You can't add $1741612770$ to any of these, as it would then leave $5958$ etc. as remainders. $\endgroup$ – Ross Millikan Aug 25 '16 at 23:32
  • 1
    $\begingroup$ there can't be any solutions greater than 5430 so no point in pointing out that these are only the small ones. If n > 5430 then the remainder dividing into 5430 is 5430. $\endgroup$ – fleablood Aug 25 '16 at 23:32
  • 1
    $\begingroup$ I think you misunderstood the question or i did not frame it well, either way thanks for putting the effort. $\endgroup$ – A---B Aug 26 '16 at 0:15

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.