# Find $n$ with $100<n<2000$ such that $2^n+2$ is divisible by $n$?

Find a number $n$ with $100<n<2000$ such that $2^n+2$ is divisible by $n$ ?

Its can easily be seen that $n=6$ is possible case but it does not satisfy the main constraint of being greater than $100$.

Can you tell me how to proceed with this problem?

• With PARI/GP , I found out that the only number in the given range satisfying the given property, is $946$. But surely, you want a proof without the help of a calculator. – Peter Jul 3 '16 at 9:39
• Solutions to this problem can be found in sequence A006517 of the On-Line Encyclopedia of Integer Sequences. On that page you can also find some references and a proof that all solutions $n$ greater than $1$ must be even. – Pjotr5 Jul 3 '16 at 9:45
• Comments are not for extended discussion; this conversation has been moved to chat. And, cool it, gentlemen. Take the discussion about site policies to meta where it belongs. – Jyrki Lahtonen Jul 3 '16 at 11:27
• Yes I would like a solution using tools of Number theory instead of a program that loops through all possible values... Is there some way approach it a mathematical perspective? – Syed Hashim Shah Hashmi Jul 12 '16 at 17:14

This answer just gives some comments and does not provide a reasonable way to find the solution to your problem with pen and paper. The sequence of numbers $n$ such that $2^n + 2 \equiv 0 \pmod{n}$ can be found in sequence A006517 of the On-Line Encyclopedia of Integer Sequences, the sequence starts as $$\mathbf{1,\ 2,\ 6,\ 66,\ 946,\ 8646,\dots}.$$ On that page it is shown that for $n>1$, $n$ must be divisible by $2$. Since for $n>1$ we have $2^n+2\equiv 2\pmod{4}$, we see that $n$ cannot be divisible by $4$. These things show that for $n>1$ we must have $n\equiv 2\pmod{4}$, which at least narrows down the numbers we have to check a bit. I haven't found any further possible optimizations. For a possible solution we can write $n=2k$ with $k$ odd. By the Chinese remainder theorem it is enough to check $2^n+2\equiv 0\pmod{2}$, which is always the case, and $2^n+2 \equiv 0 \pmod{k}$. This last equation can be written as $$2^{2k-1}+1 \equiv 0 \pmod{k}.$$ So to find all solutions with $100<n<2000$ we only have to loop through all odd numbers $50<k<1000$. In Mathematica this can be done for instance by

2*Select[Range[51, 1000, 2], PowerMod[2, 2*# - 1, #] + 1 == # &]

which yields {946}.

In for instance the solution to problem 323 in Mathematical Excalibur 14(2), 2009, p. 3 it is shown that, if an even integer $n$ has the properties that $2^n+2\equiv 0 \pmod{n}$ and $2^n+1 \equiv 0 \pmod{n-1}$, that then the number $m=2^n + 2$ will have these properties again. Since the number $2$ has these properties we see that we can find an infinite subsequence of A006517 generated by applying $n \mapsto 2^n + 2$. Starting with $2$ we get a sequence starting with $$\mathbf{2,\ 6,\ 66,\ 73786976294838206466, \dots}.$$ This is conjectured to be sequence A219037 and it provides a way to find solutions to $2^n+2\pmod{n}$. Unfortunately it misses the solution in your range, which it couldn't have hit since $2^{946}+1 \not \equiv 0 \pmod{945}$.

This problem was asked in APMO $1997$. You can find the solution here:

Or you can even refer to this Art of Problem Solving thread:

Number theoretical statement for the existance of infintly many such n:

Let $a_0$=2, define $a_{k+1}$=$2^{a_k}$+2 for every positive integer k.

Claim :

(*)first property $a_k$ | $a_{k+1}$

(**)second property ($a_k-1$) | ($a_{k+1}-1$)

Lemma : If a divides b and b/a is odd then:

$2^a+1$ divides $2^b+1$

Proof of the claim by induction:

Consider the claim is true for k=m, we show it is true for k=m+1 too.

We know that $a_m-1$ | $a_{m+1}-1$, by use of the lemma we get that

$2^{a_m-1}+1$ | $2^{a_{m+1}-1}+1$, multiplication by 2 yeilds $2^{a_m}+2$ | $2^{a_{m+1}}+2$, which is the first property for k=m+1.

On the otherhand we know that $a_m$ | $a_{m+1}$, by use of the lemma we get that

$2^{a_m}+1$ | $2^{a_{m+1}}+1$, which is the second property for k=m+1.

Now by the above procedure if x is a soloution(which means $x$ | $2^{x}+2$ and $(x-1)$ | $2^x+1$) then we can put $a_0$=x, then the sequence $a_{k+1}$=$2^{a_k}$+2 gets infinitely many soloutions. for example x=2.