5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Peter Jul 3 '16 at 9:39
  • 4
    $\begingroup$ 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. $\endgroup$ – Pjotr5 Jul 3 '16 at 9:45
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 3 '16 at 11:27
  • $\begingroup$ 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? $\endgroup$ – Syed Hashim Shah Hashmi Jul 12 '16 at 17:14
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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:

$\endgroup$
0
$\begingroup$

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.

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