show that 2^45=57 mod 91

Results 1 to 2 of 2

- Mar 24th 2009, 04:11 PM #1

- Joined
- Feb 2009
- Posts
- 40

- Mar 25th 2009, 01:07 AM #2
What have you tried so far? If it's the size of the numbers that is putting you off, notice that . So start by finding 2^45 mod 7 (same problem, but easier arithmetic). Then find 2^45 mod 13.

Since , you should find that , and similarly . Conversely (by the Chinese remainder theorem) if and , then .