- Thread starter
- #1

#### Albert

##### Well-known member

- Jan 25, 2013

- 1,225

$n\in N$

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n

- Thread starter Albert
- Start date

- Thread starter
- #1

- Jan 25, 2013

- 1,225

$n\in N$

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n

- Admin
- #2

- Mar 5, 2012

- 9,593

I know! I know!$n\in N$

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n

Please see my avatar for the method to find n.

- Admin
- #3

- Mar 5, 2012

- 9,593

Code:

```
perl -e "use bigint; foreach $n (100..1997) { print $n if ((2**$n+2) % $n == 0); }"
946
```

- Admin
- #4

- Jan 26, 2012

- 4,202

Agh! I wanted to do that first on my HP-50g calculator. Alas, I am not familiar enough with programming it.

Code:`perl -e "use bigint; foreach $n (100..1997) { print $n if ((2**$n+2) % $n == 0); }" 946`

- Thread starter
- #5

- Jan 25, 2013

- 1,225

Can this be done without using computer program ?

I mean using mathematical analysis only

I mean using mathematical analysis only

- Mar 22, 2013

- 573

Same thing I am thinking. The problem can be rephrased asAlbert.Teng said:Can this be done without using computer program ?

\(\displaystyle 2^n = -2 \pmod{n}\)

Hence, n isn't prime. In fact, n is also not odd since if it's the case, n would be even and hence, creating a contradiction. See A006517, for example.

I don't there is any analytic way to prove it, the only thing would be brute-force search.

- Moderator
- #7

- Feb 7, 2012

- 2,799

I don't see an analytic way to derive this result, but there is a fairly easy way to verify that it is correct.Can this be done without using computer program ?

I mean using mathematical analysis only

We want to show that $2^{946} + 2$ is a multiple of $946$. Dividing through by $2$, that is equivalent to showing that $2^{945} + 1$ is a multiple of $473.$ Since $473 = 11\times 43$, it will be enough to show that $2^{945} + 1$ is a multiple of $11$ and also a multiple of $43.$

In the language of congruencies, we need to check that $2^{945}\cong -1\pmod{11}$ and $2^{945}\cong -1\pmod{43}$. But $2^5\cong-1\pmod{11}$ and so $2^k\cong-1\pmod{11}$ whenever $k$ is an odd multiple of $5$. Clearly $945$ is an odd multiple of $5$, and so $2^{945}\cong -1\pmod{11}$. Similarly, $2^7\cong-1\pmod{43}$, and $945$ is an odd multiple of $7$, hence $2^{945}\cong -1\pmod{43}$.

Maybe by looking at that argument more carefully, you could deduce the conditions needed for $2^k+1$ to be a multiple of $k$, and thereby find that $k=473$ is the only solution in the given range.

- Thread starter
- #8

- Jan 25, 2013

- 1,225

but how to get the correct answer n=946 is a challenge

Further more is there any other positive integers will also satisfy our needs ?

- Mar 22, 2013

- 573

As I said before, there is a great possibility that there are no other analytical method rather than brute-force.Albert.Teng said:but how to get the correct answer n=946 is a challenge

In the given interval, no. But in \(\displaystyle \mathbb{Z}\), infinitely many and perhaps density as much as \(\displaystyle \mathcal{O}(\log n)\).Albert.Teng said:Further more is there any other positive integers will also satisfy our needs ?

Last edited:

- Jan 26, 2012

- 644

I have been watching this thread and am assuming Albert has an analytical solution (given this was posted in the Challenges subforum). I would be interested in the solution too, I've been playing around with the problem and am no closer to finding a solution.As I said before, there is a great possibility that there are no other analytical method rather than brute-force.

- Thread starter
- #11

- Jan 25, 2013

- 1,225

in fact we may follow the procedure to find n=946:$n\in N$

$100\leq n\leq 1997$

$\dfrac{2^n+2}{n} $ also is an integer

please find n

(1) at first suppose n is even :

$\dfrac{2^n+2}{n}=2(\dfrac{2^{(n-1)}+1}{2\times a\times b})=\dfrac{2^{(n-1)}+1}{a\times b}$

(here a,b must be odd positive integers)

$=\dfrac {(2^k)^{n-1/k} +1}{ab}-----(*)$ (here k=5,6,7,8 for the last digit of $2^n$ is 2,4,8,6 then repeat )

put k=5 to (*) we get :

$\dfrac {32^{(n-1)/5}+1}{ab}= \dfrac{33\times p}{ab}=m$ (here p is a positive integer )

since $\dfrac {n-1}{5}$ is a positive integer so the last digit of n must be 6 (1 impossible)

if m is an integer then a=11 and p is a multiple of b ,or b=11 and p is a multiple of a

up to now we can conclude that if n is the possible number we need ,and n is even

then the last digit of n is 6 and n is a multiple of 11

$\therefore n=2\times 11 \times (10y+3)$

the last step we must determine the value of y (y may take value 1,2,3,4,5,6,7,8 )

and this is the crucial part how to make sure that y=4

if we put k=7 to (*) we can find b (if a=11) will be 43

for $ 2^5$+1=33 is a multiple of 11

and $2^7$+1=129 is a multiple of 43 ,

$ \therefore $ y=4

that is n is even and n is a multiple of 11 also n is a multiple of 43

and we get $n=2\times 11 \times 43=946$

(2) if n is an odd number

this is impossible as "mathbalarka" wrote

Last edited:

- Mar 22, 2013

- 573

How does that follow? I don't understand.Albert.Teng said:(1 impossible)

- Thread starter
- #13

- Jan 25, 2013

- 1,225

take the last digit of $2^n$ into consideration 1 cannot appearYou can exclude the possibility that n is odd and hence, reducing your work a bit.

Originally Posted byAlbert.Teng

(1 impossible)

How does that follow? I don't understand.

besides n must be even , the last digit of n can not be "1"

so the last digit of n must be "6"

Last edited:

- Mar 4, 2013

- 188

mathbalarka said:You can exclude the possibility that n is odd and hence, reducing your work a bit.

n/2 is also odd.

- Mar 4, 2013

- 188

Isn't it "2" instead of 3?$ 3^5$+1=33 is a multiple of 11

and $3^7$+1=129 is a multiple of 43 ,

- Thread starter
- #16

- Jan 25, 2013

- 1,225

Isn't it "2" instead of 3?

thanks ! yes it is "2" instead of 3

a typo

it has been edited

- Mar 22, 2013

- 573

946. You didn't saw page 1 did you?What answers do the computer programme give?

So? Please elaborate.n/2 is also odd.

- Mar 4, 2013

- 188

So we have to look only numbers of the form 2(mod 4).So our work is reduced further.So? Please elaborate.

- Admin
- #19

- Mar 5, 2012

- 9,593

The first 6 solutions the computer program gives, are:What answers do the computer programme give?

1

2

6

66

946

8646

(For bigger numbers we will need to improve the algorithm.)

Btw, n can be odd and n can be prime... but only in the first 2 solutions (1 and 2).

Last edited:

- Mar 22, 2013

- 573

... Which is equivalent to 0 (mod 2) which is not true. Even numbers cannot satisfy the conditions in OP as I noted before. You can't say whether n/2 is odd or even since n/2 isn't really an integer. Hence, your claim that n/2 is odd is false.mathmaniac said:So we have to look only numbers of the form 2(mod 4)...

- Mar 4, 2013

- 188

No.You said odd numbers can't satisfy the condition.... Which is equivalent to 0 (mod 2) which is not true. Even numbers cannot satisfy the conditions in OP as I noted before.

And if you say even numbers can't then what is 6,66,946...etc?Are they odd?

I can say.Here is my reasoning.You can't say whether n/2 is odd or even since n/2 isn't really an integer. Hence, your claim that n/2 is odd is false.

Edit:I realize it is wrong.

I think I don't even understand how n is not odd....

But my claim that n is of the form 2(mod 4) seems to be true for all n.

Coincidence?

Last edited:

- Mar 10, 2012

- 835

Hello mathbalarka.Same thing I am thinking. The problem can be rephrased as

\(\displaystyle 2^n = -2 \pmod{n}\)

Hence, n isn't prime. In fact, n is also not odd since if it's the case, n would be even and hence, creating a contradiction. See A006517, for example.

I don't there is any analytic way to prove it, the only thing would be brute-force search.

I don't see how it follows that $n$ is not odd. Can you please elaborate.

- Mar 4, 2013

- 188

May I ?Hello mathbalarka.

I don't see how it follows that $n$ is not odd. Can you please elaborate.

2^n+2 is always even.If n is odd, \(\displaystyle \frac {2^n+2}{n}\) is not an integer and the question is to find n that satisfies \(\displaystyle \frac {2^n+2}{n}\) is an integer.

So n is not odd.

-mathmaniac

- Jan 26, 2012

- 644

[JUSTIFY]The argument does not follow. For instance, 14 is even, yet 7 (an odd number) divides it. What you are essentially saying is that no odd number divides an even number, which is clearly incorrect. This argument is only valid for powers of two, and unfortunately, $2^n + 2$ is never a power of two, except for the case $n = 1$.[/JUSTIFY]May I ?

2^n+2 is always even.If n is odd, \(\displaystyle \frac {2^n+2}{n}\) is not an integer and the question is to find n that satisfies \(\displaystyle \frac {2^n+2}{n}\) is an integer.

So n is not odd.

-mathmaniac

- Mar 4, 2013

- 188

Now I am in trouble.Everything seems to be slipping out of my hands.

Let me think...