Congruence for large modulus

Question

The idea it to find remainder $35^{32} + 51^{24} \bmod 1785$.

1785 is a composite number equal to 3 x 5 x 7 x 17.

35 is 0 mod 5 and mod 7.

51 is 0 mod 3 and mod 17.

Any help regarding steps from here?

I know that there are numbers having same remainder in composite case.

For example $a^c \cong d \bmod m$ and $a^c \cong d \bmod n$ $a^c \cong d \bmod mn$

It's something I cannot get using numbers as before.

Answer 1

Found a simpler solution

$x=35^{32}+51^{24}$

$x \equiv 1 \mod 3$

$x \equiv 1 \mod 5$

$x \equiv 1 \mod 7$

$x \equiv 1 \mod 17$

$x \equiv 1 \mod 1785 = lcm[3,5,7,17]$

Answer 2

Let $x=35^{32}$. $$ x\equiv1\mod 3,\quad x\equiv0\mod 5\\ x\equiv0\mod 7,\quad x\equiv1\mod 17 $$ Now that we have these congruences, view $x$ as a variable and let's try to solve for $x$. Chinese Remainder theorem says that the above a system has a solution $$ x= a\cdot5\cdot7\cdot17+c\cdot3\cdot7\cdot17+d\cdot3\cdot5\cdot17+b'\cdot3\cdot5\cdot7 $$ As $5|x$, $5|c$ and similarly $7|d$. Now letting $b=(c/5)\cdot17+(d/7)\cdot17+b'$ we have $x=5\cdot7(a\cdot17+b\cdot3)$. Letting $a=1,b=9$ makes sure all of the congruences are satisfied. $$ \therefore x=1225\\\implies 35^{32}\equiv1225\mod1785 $$ as CRT says any two solutions of the system are congruent modulo $3\cdot5\cdot7\cdot17=1785$ and we already know that $35^{32}$ is a solution. Similarly, $$ 51^{24}\equiv561\mod 1785\\ \implies 35^{32}+51^{24}\equiv1\mod1785 $$