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

2^k + n (mod p)

  1. Jan 14, 2008 #1


    User Avatar
    Science Advisor
    Homework Helper

    I was working on a problem with numbers of the form [itex]2^k+n[/itex] for k (potentially) large and n fixed. I pre-sieve candidate primes in the range by finding a value f such that whenever [itex]k=f\pmod{p-1}[/itex] it holds that [itex]p|2^k+n[/itex], and test a large range of k values.

    1. The search for such an f is computationally expensive, since I search in an essentially brute-force manner. Is there a number-theoretic way of getting this directly? I feel like there should be.
    2. Sometimes 'more is true': whenever [itex]k=f\pmod m[/itex] it holds that [itex]p|2^k+n[/itex], for some [itex]m|p-1[/itex]. Since I test the f values sequentially, this is not the case if 2f > p-1. When 2f < p-1, is there a good way to find values of m that work?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted