Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number theory help

  1. Mar 6, 2006 #1
    I'm trying to show that 25 is a strong pseudoprime to the base 7 using millers test. Is there a better way to solve this than just brute force?
    Thanks
     
  2. jcsd
  3. Mar 6, 2006 #2

    CarlB

    User Avatar
    Science Advisor
    Homework Helper

    I'm not sure of the notation. I assume that you need to compute

    [tex]7^{25}\;\;\textrm{mod}\;(25).[/tex]

    The way to do is to avoid letting the power get all out of control. Consider:

    7*7 = 49 = 24 = -1 mod (25)

    so
    7*7*7*7 = 1 mod (25).

    so what is 7^{24}?

    Carl
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook