# Find n

#### Albert

##### Well-known member
$n\in N$

$100\leq n\leq 1997$

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

#### Klaas van Aarsen

##### MHB Seeker
Staff member
$n\in N$

$100\leq n\leq 1997$

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

I know! I know! Please see my avatar for the method to find n. #### Klaas van Aarsen

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

#### Ackbach

##### Indicium Physicus
Staff member
Alternatively:
Code:
perl -e "use bigint; foreach $n (100..1997) { print$n if ((2**$n+2) %$n == 0); }"
946
Agh! I wanted to do that first on my HP-50g calculator. Alas, I am not familiar enough with programming it.

#### Albert

##### Well-known member
Can this be done without using computer program ?

I mean using mathematical analysis only

#### mathbalarka

##### Well-known member
MHB Math Helper
Albert.Teng said:
Can this be done without using computer program ?
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.

#### Opalg

##### MHB Oldtimer
Staff member
Can this be done without using computer program ?

I mean using mathematical analysis only
I don't see an analytic way to derive this result, but there is a fairly easy way to verify that it is correct.

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.

#### Albert

##### Well-known member
given n=946 and trace back to prove it meets the restriction ,it is easy

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 ?

#### mathbalarka

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

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

Last edited:

#### Bacterius

##### Well-known member
MHB Math Helper
As I said before, there is a great possibility that there are no other analytical method rather than brute-force.
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.

#### Albert

##### Well-known member
$n\in N$

$100\leq n\leq 1997$

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

in fact we may follow the procedure to find n=946:
(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:

#### mathbalarka

##### Well-known member
MHB Math Helper
You can exclude the possibility that n is odd and hence, reducing your work a bit.

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

#### Albert

##### Well-known member
You can exclude the possibility that n is odd and hence, reducing your work a bit. Originally Posted by Albert.Teng
(1 impossible)

How does that follow? I don't understand.
take the last digit of $2^n$ into consideration 1 cannot appear

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:

#### mathmaniac

##### Active member
What answers do the computer programme give?

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

n/2 is also odd.

#### mathmaniac

##### Active member
$3^5$+1=33 is a multiple of 11
and $3^7$+1=129 is a multiple of 43 ,
Isn't it "2" instead of 3?

#### Albert

##### Well-known member
Isn't it "2" instead of 3?

thanks ! yes it is "2" instead of 3

a typo

it has been edited

#### mathbalarka

##### Well-known member
MHB Math Helper
What answers do the computer programme give?
946. You didn't saw page 1 did you? n/2 is also odd.

#### mathmaniac

##### Active member
So we have to look only numbers of the form 2(mod 4).So our work is reduced further.

#### Klaas van Aarsen

##### MHB Seeker
Staff member
What answers do the computer programme give?
The first 6 solutions the computer program gives, are:
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:

#### mathbalarka

##### Well-known member
MHB Math Helper
I already gave a link to the sequence in case anyone wants a number of terms to see satisfying everything in the OP except the upper and lower bounds.

mathmaniac said:
So we have to look only numbers of the form 2(mod 4)...
... 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

##### Active member
... Which is equivalent to 0 (mod 2) which is not true. Even numbers cannot satisfy the conditions in OP as I noted before.
No.You said odd numbers can't satisfy the condition.
And if you say even numbers can't then what is 6,66,946...etc?Are they odd?

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.
I can say.Here is my reasoning.

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:

#### caffeinemachine

##### Well-known member
MHB Math Scholar
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.
Hello mathbalarka.
I don't see how it follows that $n$ is not odd. Can you please elaborate.

#### mathmaniac

##### Active member
Hello mathbalarka.
I don't see how it follows that $n$ is not odd. Can you please elaborate.
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

#### Bacterius

##### Well-known member
MHB Math Helper
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
[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]

#### mathmaniac

##### Active member
Looks like I got the fraction upside down in my mind.
Now I am in trouble.Everything seems to be slipping out of my hands.
Let me think...