0
$\begingroup$

When doing a problem on computer arithmetic with large integers, I reached a step when I needed to solve system of congruences. I came up with the following equations: $$x ≡ 65 \pmod{99})\\ x ≡ 2 \pmod{98}\\ x ≡ 51 \pmod{97}\\ x ≡ 10 \pmod{95}$$

I tried to solve using chinese remainder theorem, but it became too large and complex.

The original question is : Find sum of numbers $123,684$ and $413,456$ by representing the numbers as $4$-tuple by using remainder modulo of pair-wise relatively prime numbers less than $100.$

While solving by chinese remainder theorem the inverse modulo becomes too large.I need to solution to either the solving of congruences or the full question.

$\endgroup$
  • $\begingroup$ I would use first some smaller numbers as modulus, maybe 16, 25, 33, 43. $\endgroup$ – dan_fulea Sep 1 '18 at 3:06
  • $\begingroup$ The modulus you are looking for is a little less than $100^4=10^8$ That is large (but doable if you are determined) for hand calculations but trivial for a computer. What tools are you using? $\endgroup$ – Ross Millikan Sep 1 '18 at 5:09
0
$\begingroup$

If I start with $10$ to satisfy the bottom one every time I add $95$ I subtract $2$ in the $\pmod{97}$. I'm looking for $-46 \pmod {97}$ so have to add $\frac {56}2$ copies of $95$. The bottom two are solved by $10+28\cdot 95=2670 \pmod {9215}$. $2670 \equiv 24 \pmod {98}$ while $9215 \equiv 3 \pmod {98}$. We can add $\frac {198-24}3\cdot 9215=534\ 470$ to get the second line so our solutions are now $537\ 140 \pmod {903\ 070}$ Finally we have to consider the first. It turns out $537\ 140 \equiv 65 \pmod {99}$ so we are done. The solutions are $537\ 140 \pmod {89\ 403\ 930}$. All the computations were done with the iPhone calculator.

$\endgroup$

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.