Finding a solution to congruences modulo $801*1729$ Given $x \equiv 676\pmod{801}$ and $x \equiv 1447\pmod{1729}$. I need to solve for $x$. I think I know how to use the Chinese Remainder Theorem to generally solve this sort of problem, but I'm not sure how to efficiently do this with these large numbers. 
$1729\pmod{801} \equiv 127 \pmod{801}$ and $801\pmod{1729}$ can't be reduced. So for some integers a and b such that $127*a \equiv 676\pmod{801}$ and $801*b \equiv 1447\pmod{1729}$, 
$x = 1729*a+801*b$
I just don't know how to get $a$ and $b$ without endless trial and error.
 A: The better I know for this sort of problems with large numbers is to go to a linear diophantine equation in two variables which is translation of the two given modular equalities and solving it completely finding out first a particular solution. This way we have
$$x=676+801X=1447+1729Y.................(*)$$
When the coefficients are not large, a particular solution is in general easily found while with large coefficients this problem is less easy but always one can find one. In the case of the equation $(*)$ we find $(X,Y)=(124,57)$ so the general solution has the form
$$\begin{cases}X=124+1729t\\Y=57+801t\end{cases}$$
Consequently $$x=676+801(124+1729t)=100000+1384929t$$
(the same expression is get taking $x=1447+1729(124+1729t)$ of course).
Thus the minimal positive solution is $\color{red}{x=100000}$
(In fact $100000-676=99324=124\cdot801$ and $100000-1447=98553=57\cdot1729$)
A: Note that $801=3^2  \times 89 $ and $1729 =7 \times 13 \times 19 $ and so they are coprime.
Use Euclid's Algorithm to calulate
\begin{eqnarray*}
1729 \times 82 \equiv 1 \pmod{801} \\
801 \times 1552 \equiv 1 \pmod {1729}
\end{eqnarray*}
A solution can be constructed easily by $x=676 \times 1729 \times 82 +1447 \times 801 \times 1552 $. Now reduce this value modulo $ 801 \times 1729$ to get $\color{blue}{100000}$.
