# Chinese Remainder Theorem

Printable View

• March 23rd 2009, 10:08 AM
knguyen2005
Chinese Remainder Theorem
I forgot how to do the Chinese Remainder Theorem which applied for this question:

Calculate 45^35 modulo 13 given that
y === 3 mod 13
and y === 4 mod 45

Thanks
• March 23rd 2009, 08:26 PM
ThePerfectHacker
Quote:

Originally Posted by knguyen2005
y === 3 mod 13
and y === 4 mod 45

This is equivalent to, $y\equiv 3 + 7\cdot 13(\bmod 13)$ and $y\equiv 4 + 2\cdot 45(\bmod 45)$.
Therefore, $y\equiv 94(\bmod 13)$ and $y\equiv 94(\bmod 45)$. Thus, $y\equiv 94(\bmod 585)$.