# Computer arithmetic on large integers, (Chinese remainder theorem)

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.

• I would use first some smaller numbers as modulus, maybe 16, 25, 33, 43. – dan_fulea Sep 1 '18 at 3:06
• 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? – Ross Millikan Sep 1 '18 at 5:09

## 1 Answer

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.