Horrendous Horror.

You want to solve this:

$x \equiv 12 \pmod {71}$ $x \equiv 26 \pmod {73}$ $x \equiv 34 \pmod {75}$ $x \equiv 59 \pmod {77}$

Compute $M = 71 \times 73 \times 75 \times 77$

Compute $M_i = \frac{M}{m_i}$ for each modulus $m_i$

You'll get $(M_1,M_2,M_3,M_4)= (421575, 410025, 39901, 388725)$

Compute $x_i \equiv M_i^{-1} \pmod{m_i}$ for each $m_i$ using Extended Euclidean Algorithm .

You'll get $(x_1,x_2, x_3,x_4) = (37, 41, 61, 8)$

We are ready! Thank the stars!

Compute $x \equiv \sum_{i=1}^{4} m_i M_i x_i \pmod {M}$

You'll get $\boxed{x \equiv 19140334 \pmod {29931825}}$

which is obviously the smallest possible solution.

Why care, anyway?

Go to Wolfram|Alpha and run this code:

ChineseRemainder[{12, 26, 34, 59}, {71, 73, 75, 77}]

I did this by a code. Run this code and you will get the number.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <iostream>


using namespace std;


int main()

{

    long int x=71,y;

    agn: if(((x-12)%71)==0)

    {

        if((x-26)%73==0)

            {

                if((x-34)%75==0)

                {

                    if((x-59)%77==0)

                    {

                     std::cout<< x<<std::endl;

                    goto ter;

                    }

                }

            }

    }


    x++;

    goto agn;

ter: cin>> y;

return x;

}