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

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$$.

• Congruence modulo seven does not solve this problem completely? Aug 24, 2021 at 15:15
• @SMC - So I have to learn more about modulo calcules.
– Lehs
Aug 24, 2021 at 15:17
• Hint: First look for an exponent $n$ such that $7\mid 2^n+1$. Aug 24, 2021 at 15:19
• I suggest you calculate the remainders mod 7 of $2^1$,$2 ^2$, $2^3$,$2^4$. etc., multiplying by 2 to get each one from the one before. Spot the pattern. Aug 24, 2021 at 15:22
• For a "standard" proof of the $p\mid n$, $q\mid n+1$ question I recommend that you familiarize yourself with the Chinese Remainder Theorem. It really settles many elementary number theory questions. Aug 24, 2021 at 15:25

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.

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.

• Can anybody explain the reason for the downvote? Anything wrong with the answer? Aug 24, 2021 at 15:25
• I think, the only reason for the downvotes (and the later deletion) is that there is a much easier solution, namely that $7\mid 2^n+1$ is not possible at all. The method is therfore an overkill, but the answer nevertheless absolutely correct. Aug 29, 2021 at 10:00
• @Peter Yes, later when I saw the other answers, I understood that mine was an overkill. So, I agree with you on that. But, can you tell me a different thing... I am quite new to this site and I often don't understand its activities properly. From your comment, I guess my answer was deleted, but how did it come into existance again? As far as I remember, I saw a few downvotes on the day I posted it, and today suddenly, I'm again recieving activities on this post. I don't understand how it happened :( Aug 29, 2021 at 12:19
• The answer was undeleted and has now 2 upvotes. It seems this was not in your interest, but I thought an undeletion (and a later upvote) would make you happy. You can delete the answer , if you do not want its "revival". The theorem has its merit in similar situations, so I think the undeletion was justified. Aug 29, 2021 at 14:09
• @Peter no no, it's absolutely fine. In fact, I thank you for the undeleting it. I was just a little confused about how this site works. Now, I understand. So, thanks again :) Aug 29, 2021 at 15:05

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$$