Results 1 to 2 of 2

Thread: need help

  1. #1
    Junior Member
    Joined
    Feb 2009
    Posts
    40

    need help

    show that 2^45=57 mod 91
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    10
    Quote Originally Posted by mancillaj3 View Post
    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 $\displaystyle 91 = 7\times 13$. So start by finding 2^45 mod 7 (same problem, but easier arithmetic). Then find 2^45 mod 13.

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


/mathhelpforum @mathhelpforum