Finding a solution to congruences modulo $801*1729$

Question

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.

Answer 1

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$)

Answer 2

The beginning is some version of the Extended Euclidean Algorithm...

$$ 1729 \cdot 82 - 801 \cdot 177 = 1 $$

$$ 1729 \cdot 82 \equiv 1 \pmod{801} $$ $$ 1729 \cdot 82 \equiv 0 \pmod{1729} $$ $$ 801 \cdot (-177) \equiv 1 \pmod{1729} $$ $$ 801 \cdot (-177) \equiv 0 \pmod{801} $$

What numbers $R,S$ ought we to choose in $$ 1729 \cdot 82 R - 801 \cdot 177 S \; ? $$

I got a large negative number. You are free to add or subtract any multiple of $801 \cdot 1729 = 1384929$ to get an answer that is positive and smaller than $1384929.$ Comes out clean and obviously intentional.

=================================================================

$$ \gcd( 1729, 801 ) = ??? $$

$$ \frac{ 1729 }{ 801 } = 2 + \frac{ 127 }{ 801 } $$ $$ \frac{ 801 }{ 127 } = 6 + \frac{ 39 }{ 127 } $$ $$ \frac{ 127 }{ 39 } = 3 + \frac{ 10 }{ 39 } $$ $$ \frac{ 39 }{ 10 } = 3 + \frac{ 9 }{ 10 } $$ $$ \frac{ 10 }{ 9 } = 1 + \frac{ 1 }{ 9 } $$ $$ \frac{ 9 }{ 1 } = 9 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccc} & & 2 & & 6 & & 3 & & 3 & & 1 & & 9 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 13 }{ 6 } & & \frac{ 41 }{ 19 } & & \frac{ 136 }{ 63 } & & \frac{ 177 }{ 82 } & & \frac{ 1729 }{ 801 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 2 \\ \frac{ 2 }{ 1 } & \mbox{digit} & 6 \\ \frac{ 13 }{ 6 } & \mbox{digit} & 3 \\ \frac{ 41 }{ 19 } & \mbox{digit} & 3 \\ \frac{ 136 }{ 63 } & \mbox{digit} & 1 \\ \frac{ 177 }{ 82 } & \mbox{digit} & 9 \\ \frac{ 1729 }{ 801 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 1729 \cdot 82 - 801 \cdot 177 = 1 $$

Answer 3

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}$.