# Thread: need help

1. ## need help

show that 2^45=57 mod 91

2. Originally Posted by mancillaj3
show that 2^45=57 mod 91
What have you tried so far? If it's the size of the numbers that is putting you off, notice that $91 = 7\times 13$. So start by finding 2^45 mod 7 (same problem, but easier arithmetic). Then find 2^45 mod 13.

Since $57\equiv1\!\!\!\pmod7$, you should find that $2^{45}\equiv1\!\!\!\pmod7$, and similarly $2^{45}\equiv5\!\!\!\pmod{13}$. Conversely (by the Chinese remainder theorem) if $x\equiv1\!\!\!\pmod7$ and $x\equiv5\!\!\!\pmod{13}$, then $x\equiv57\!\!\!\pmod{91}$.