1
$\begingroup$

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

$\endgroup$
9
  • 10
    $\begingroup$ Congruence modulo seven does not solve this problem completely? $\endgroup$ Aug 24, 2021 at 15:15
  • $\begingroup$ @SMC - So I have to learn more about modulo calcules. $\endgroup$
    – Lehs
    Aug 24, 2021 at 15:17
  • 3
    $\begingroup$ Hint: First look for an exponent $n$ such that $7\mid 2^n+1$. $\endgroup$ Aug 24, 2021 at 15:19
  • 10
    $\begingroup$ 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. $\endgroup$ Aug 24, 2021 at 15:22
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 24, 2021 at 15:25

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Can anybody explain the reason for the downvote? Anything wrong with the answer? $\endgroup$ Aug 24, 2021 at 15:25
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Aug 29, 2021 at 10:00
  • $\begingroup$ @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 :( $\endgroup$ Aug 29, 2021 at 12:19
  • $\begingroup$ 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. $\endgroup$
    – Peter
    Aug 29, 2021 at 14:09
  • $\begingroup$ @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 :) $\endgroup$ Aug 29, 2021 at 15:05
1
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .