1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted

Similar Discussions: 2^k + n (mod p)
  1. 2^k = n in Z/p (Replies: 2)