2^k + n (mod p)

1. Jan 14, 2008

CRGreathouse

I was working on a problem with numbers of the form $2^k+n$ for k (potentially) large and n fixed. I pre-sieve candidate primes in the range by finding a value f such that whenever $k=f\pmod{p-1}$ it holds that $p|2^k+n$, 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 $k=f\pmod m$ it holds that $p|2^k+n$, for some $m|p-1$. 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?