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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.