Is $7$ the greatest prime factor of some $2^n+1$?

Question

I'm looking for theorems that say something about relations of factors between consecutive numbers. In this case relations between greatest primefactors of consecutive numbers. I've tested for $n<10,000$ but find no $n$ such that $7$ is the greatest prime factor of $2^n+1$.

I've found out that given two different primes $p,q$ there is always a natural number $n$ such that $p|n$ and $q|n+1$.

So I would like to find a number $n$ so that $7$ is the greatest prime factor of $2^n+1$ or a proof that there is no such $n$.

Answer 1

As Jykri Lahtonen says, the most natural thing to do is to look at the congruence $2^n\equiv -1\pmod{7}$.

If you know a bit more about elementary number theory and know things like Fermat's little theorem, primitive generator of $\mathbb{F}_p^*$ or quadratic residues/nonresidues, you can probably interpret the following problem in a more enlightening perspective.

But assuming you don't, you can observe that $2^n$ is only ever $2, 4$ or $1\pmod{7}$ just by listing out the first few exponents. That should tell you what are the possible values of $2^n+1\pmod{7}$ and conclude no such $n$ exists.

Answer 2

It can be proved using Zsigmondy's theorem that given any $n$, the number $2^n+1$ has a prime factor of the form $2nk+1$ for some $k\in \mathbb N$. So, for your question, you only need to check the cases $n=1,2,3$ by hand. You can find the proof here.

This completes the proof I guess.

Answer 3

To elaborate on daruma's answer,

First observe that any number is in one of the forms: $3n,3n+1$ or $3n+2$. Now $2^3 \equiv 1 \mod 7$ implies $$2^{3n} \equiv 1 \mod 7$$ so that we also have $$2^{3n+1} \equiv 2 \mod 7 $$ and $$ 2^{3n+2} \equiv 4\mod 7$$. So for any $k$ we have $2^k \equiv 1,2,4 \mod 7$

Finally observe that $2^n + 1 \equiv 0\mod 7 $ is same as $2^n \equiv 6\mod 7 $

Note : $2^n \equiv r \mod 7$ is same as the statement $7$ divides $2^n - r$