shobber wrote: Find an integer $n$, where $100 \leq n \leq 1997$, such that \[ \frac{2^n+2}{n} \] is also an integer. Find all such integers or at least one?

Let $f(n)=\frac{2^n+2}{n}=\frac{2(2^{n-1}+1)}{n}$ is integer number. Known, that $2^{p-1}=1(mod p^2)\Longrightarrow p=1093 \ or \ p=3511 \ or \ p>3000000000$. Therefore $n=p_1*p_2*\dots*p_k$, were $p_1<p_2<\dots <p_k$ are distinct prims (because (n-1,n)=1). If k=1 we have n=2. Let $d_i \ or \ d(p)$ is minimal with satisfyed $2^{d_i}=-1(mod \ p_i)$. If $p=7(mod \ 8)$, then d(p) is not define, because has not d: $2^d=-1(mod \ p)$. Therefore $p_i\not =7(mod \ 8)$. We have $d_i|(n-1)$ and $\frac{n-1}{d_i}$ is odd for all i (d(2)=1). Therefore $ord_2(d_1)=ord_2(d_2)=\dots =ord_2(d_k)$. Because n<1998 and k>1, one of prime divisors is 2 or 3 or 5 or 11 or 13 or 17 or 19 or 29 or 37 or 41 or 43 and behaps one prime divisor p>43. We have $d(2)=1,d(3)=1,d(5)=2,d(11)=5,d(13)=6,d(17)=4,d(19)=9,d(29)=14,d(37)=18,d(41)=10,d(43)=7$. If k=2 and n is odd we have $d_1|(p_2-1),d_2|(p_1-1)$. If k=3 and $p_1=2$ then $d_2|(2p_3-1),d_3|(2p_2-1)$. It give easy property to chek: If 43|n then 86|n (because (d(43) is odd) and 7|(n-1). It give n=86*11=946. If 41|n then n=11(mod 20). It give n=41*11 or 41*31. Because d(11) is odd, d(31) is not defined in this case have not solution. If 37|n then n=19(mod 36). It give n=37*19 or n=37*55 - have not solution. If 29|n then n=15(mod 28). It give n=29*15 or n=29*43 - have not solution. If 19|n then 38|n and n=1(mod 9). It give n=38(5+9k)=38*5,38*14,38*23,38*32,38*41,38*50 -have not solution. If 17|n then n=5(mod 8). It give n=17*(5+8k) - have not solution. If 13|n then n=7(mod 12). It give n=n=13*(7+12k) - have not solution. If 11|n then 22|n and n=1(mod 5). It give n=22(3+10k). We have solution n=66. If 5|n then n=3(mod 4). It give n=5(3+4k). It give that n have prime divisor p=3(mod 4). Then d(p) is odd or not define. It give contradition with $ord_2(d(p))=ord_2(d(5))=1$. If 3|n then 6|n. If $\frac n6 =p$ is prime we have contradition with $d(p)|5=2p_2-1$. Else it have prime divisor p<43, and we consider all cases. Therefore, if f(n) is integer and n<2000, then $n=2 \ or \ n=6 \ or \ n=66 \ or \ n=946$.

pavel kozlov wrote: shobber wrote: Find an integer $n$, where $100 \leq n \leq 1997$, such that \[ \frac{2^n+2}{n} \] is also an integer. Find all such integers or at least one? It seems just one......

Rust wrote: $ 2^{p - 1} = 1(mod p^2)\Longrightarrow p = 1093 \ or \ p = 3511 \ or \ p > 3000000000$ I didn't understand why are we using this. Shouldn't be $ 2^{p - 1} =- 1(mod p^2)$???Explain it please!

Rust wrote: Let $ f(n) = \frac {2^n + 2}{n} = \frac {2(2^{n - 1} + 1)}{n}$ is integer number. Known, that $ 2^{p - 1} = 1(mod p^2)\Longrightarrow p = 1093 \ or \ p = 3511 \ or \ p > 3000000000$. Therefore $ n = p_1*p_2*\dots*p_k$, were $ p_1 < p_2 < \dots < p_k$ are distinct prims (because (n-1,n)=1). . why $ n = p_1*p_2*\dots*p_k$ and not $ n = p_1^{a_1}*p_2^{a_2}*\dots*p_k^{a_k}$ !!!!!!!

The number $n = 946 = 2 \cdot 11 \cdot 43$ works. The way you construct is: we try to look for examples of the form $n = 2pq$, where $p$ and $q$ are distinct odd primes. This amounts to $p \mid 2^{2q-1}+1$ and $q \mid 2^{2p-1}+1$. Looking at orders, it would suffices to have $q = 4p-1$ and $\left( \frac2q \right) = -1$, but the latter follows anyways by quadratic reciprocity (since $q \equiv 3 \pmod 8$). In the first equality, this means $p \mid 2^{8p-3}+1 \implies p \mid 2^5+1=33$. So we get the solutions $(p,q)=(3,11)$ and $(p,q)=(11,43)$. These gives $n = 66$ and $n = 946$ as candidates; the latter works.

What is the motivation for your solution? Thanks!

Could someone please tell me the motivation for v_Enhance's solution too? Thanks!

The problem only asks to construct a single $n$, you can show (or guess) that $n$ should be even. If $n = 2p$ then the only solution is $n = 6$, so you do the next best thing and guess $n = 2pq$. Everything past that point is routine application of orders.

@v_Enhance could you please elaborate on how you got $p \mid 2^{2q-1}+1$, since I got $p \mid 2^{4q-2}-1$ but this does not imply your result. Also, could you explain the latter part when you say: Quote: Looking at orders, it would suffices to have $q = 4p-1$ and $\left( \frac2q \right) = -1$, . Thanks in advance.

For the first bit: if $p \mid 2^{n-1}+1$, then $0 \equiv 2^{n-1}+1 \equiv 2^{2pq-1}+1 \equiv 2^{2q-1}+1 \pmod p$, since $2^p \equiv 2 \pmod p$ by Fermat. For the second part, I meant the second divisibility only when I said "it suffices to have" (that is unclear on my part, sorry). Since if $q = 4p-1$, then $2p-1 = \tfrac12(q-1)$, and $(2/q) \equiv 2^{\frac12(q-1)} \pmod q$.

Hey, this kind of reminded me of IMO 1990 P3... anyways does anyone know of a nice elegant solution to this one? The way I did it was very bashy... first tried $pq$, then $pqr$, somehow stumbled across $2pq$, figured $p \equiv q \equiv 3 \pmod{4}$, took $p$ to be the smaller one, took the case when $p=7$, got no solutions, then tried $p=11$ to first try $q=23$ because $q \equiv 3 \pmod{5}$ and finally got $q=43$ to work (if you're wondering how I got these relations, it's just basic orders and $gcd$ bashing)... the problem with this method, I feel, aside from being unnecessarily long, is that it's very easy to just give up during a real exam, especially after 20-25 minutes of trying out numbers with no progress... so does anyone have a different solution, or even a way to shorten this approach?

This problem is such a troll; the number $n=946$ works. This is clear as $2^{946} \equiv 2^6 \equiv -2 \pmod {11}$ and $2^{946} \equiv 2^{22} \equiv -2 \pmod {43}$, as desired. Remarks: The way I constructed $n$ is similar to the above solutions. First we can note that $n$ has to be even, for obvious reasons. It would be pretty unexpected if a lot of different primes divided $n$, since then we get a lot of different conditions on $n$. So we try $n=2p$, $n=2p^2$, then $n=2pq$ to gradually add more conditions. The first one yields $n=6$, too small, while the second one yields no value of $n$ less than or equal to $1997$. Now we try $n=2pq$, and using simple orders we find that $q=4p-1$ satisfies $p \mid 2^{2q-1}+1$. We can guess that the primes $p,q$ must be of that form, and trial and error shows one that works.

mathlogician wrote: This problem is such a troll; the number $n=946$ works. This is clear as $2^{946} \equiv 2^6 \equiv -2 \pmod {11}$ and $2^{946} \equiv 2^{22} \equiv -2 \pmod {43}$, as desired. Remarks: The way I constructed $n$ is similar to the above solutions. First we can note that $n$ has to be even, for obvious reasons. It would be pretty unexpected if a lot of different primes divided $n$, since then we get a lot of different conditions on $n$. So we try $n=2p$, $n=2p^2$, then $n=2pq$ to gradually add more conditions. The first one yields $n=6$, too small, while the second one yields no value of $n$ less than or equal to $1997$. Now we try $n=2pq$, from which simple orders tells us that $q=4p-1$, the end. Hello, how do you get q=4p-1?

Mathloops wrote: mathlogician wrote: This problem is such a troll; the number $n=946$ works. This is clear as $2^{946} \equiv 2^6 \equiv -2 \pmod {11}$ and $2^{946} \equiv 2^{22} \equiv -2 \pmod {43}$, as desired. Remarks: The way I constructed $n$ is similar to the above solutions. First we can note that $n$ has to be even, for obvious reasons. It would be pretty unexpected if a lot of different primes divided $n$, since then we get a lot of different conditions on $n$. So we try $n=2p$, $n=2p^2$, then $n=2pq$ to gradually add more conditions. The first one yields $n=6$, too small, while the second one yields no value of $n$ less than or equal to $1997$. Now we try $n=2pq$, from which simple orders tells us that $q=4p-1$, the end. Hello, how do you get q=4p-1? I misphrased it, sorry. We want to solve both conditions $p \mid 2^{2q-1}+1$ and $q \mid 2^{2p-1}+1$. We can derive this by seeing that $2$ has order $4p-2$ mod $q$, so if we assume that $2$ is a primitive root we get $q=4p-1$. I didn't know how to show the second condition works, but there's only a small amount of primes to check so I just checked all the pairs of primes $(p,q) = (p,4p-1)$ and found one that worked. tumbleweed wrote:

I don't understand the question, the problem asks to find an $n$ and we found an $n$, it's not necessary to find all $n$.

This is official solution, but I don't know... how did they get p-1l4pq-2 and q-1l4pq-2?

$946=2 \cdot 11 \cdot 43$ clearly works. Also, $6$ and $66$ work but unluckily doesn’t lie in the desired range. Now, we illustrate the process of construction of this number. First of all, we show some results which reduces the search space of such $n$. Lemma 1: If $x^\gamma \equiv -1 \pmod p$ and $\gamma$ is a power of 2, then $\text{ord}_p(x)=2\gamma$. Proof: Let $\text{ord}_p(x)=d$. Now $d \mid 2\gamma$ as $x^{2\gamma} \equiv 1 \pmod p$. Also, $d \nmid \gamma$ because if the contrary were true, then $x^\gamma \equiv 1 \pmod p$ which is a contradiction. Combining $d \mid 2\gamma$ and $d \nmid \gamma$ we get $d=2\gamma$. $\square$ We will now show another lemma with the above result. Lemma 2: If $p \mid a^\beta +b^\beta$ where $\beta =2^k$ for some $k \in \mathbb{N}$ and $p$ is some prime then $p \equiv 1 \pmod{2^{k+1}}$. Proof: From the divisibility condition, we have \[a^\beta +b^\beta \equiv 0 \pmod p \implies \left(\frac{a}{b}\right)^{\beta} \equiv -1 \pmod p \]Applying Lemma 1, we get to know $2^{k+1} \mid p-1$. $\square$ Coming back to the problem, the following claim discards the possibility of odd $n$. Claim: Any odd $n>1$ does not work. Proof: Assume that $n$ is odd. The proof will be by infinite descent on $\nu_2(n-1)$ to show that $n-1=0$. As $n$ is odd, $n-1$ will be even. Pick a prime $q$ dividing $n$, which gives $q \mid 2^{n-1}+1$. By Fermat's Christmas Theorem, we have that $q \equiv 1 \pmod 4$ which in fact gives $n \equiv 1 \pmod 4 \iff 4 \mid n-1$. Notice that $2^{n-1}+1=2^{4a}+1$ for some integer $a$. By Lemma 2, we have that $8 \mid q-1$ which gives $8 \mid n-1$. Upon simple induction, we can show that $2^\alpha \mid n-1$ for arbitrarily large $\alpha \in \mathbb{N}$. This forces $n-1=0$ as desired. $\square$ Now $n$ can only be even and it is easy to see that $\nu_2(n)=1$. We will show that we do have a solution if $n=2pq$ where $p$ and $q$ are primes. If $n=2pq$ then we have $pq \mid 2^{2pq-1}+1$. This can be simplified like this \[p \mid 2^{2pq-1}+1 \implies p \mid 2^{2q-1}+1\]Similarly, we get $q \mid 2^{2p-1} +1$. Another wild try could be to consider the case to consider the case when $p=q$ which gives that both primes must be equal to 5. Sadly this doesn't work. So, from here on assume $p>q$. $p \mid 2^{2p-1}+1 \implies 2^{2p} \equiv -2$. So we want $-2$ to be a quadratic residue. We now wish $\displaystyle \left(\frac{-2}{p}\right)=1$ where we used the Legendre's Symbol. Now \begin{align*} 1=\left( \frac{-2}{p} \right) &= \left(\frac{-1}{p}\right) \times \left(\frac{2}{p}\right) \\ &= (-1)^{\frac{p-1}{2}} \cdot (-1)^{\frac{p^2-1}{8}} \end{align*}Set $\displaystyle \frac{p-1}{2} \cdot {\frac{p^2-1}{8}}=2f$ for some integer $f$. We can easily get that this is possible iff $p \equiv 1,3 \pmod 8$. Now we can finally go for hit and trial. This was lengthy on paper as I personally tried too much for $p \equiv 1 \pmod 8$. If we try $p\equiv 3 \pmod 8$ then we get $(p,q)=(11,3)$ and $(11,43)$ where the value of $q$ can be found out very easily from $q \mid 2^{2p-1}$ when you put $p=11$. We are finally done. $\blacksquare$

$2|2^n+2 ~~~\forall n.$ $11|2^n+2 \iff n\equiv 6 \pmod{10}.$ $43|2^2+2 \iff n\equiv 8 \pmod{14}.$ We find $n=946=2\cdot 11 \cdot 43$ satisfying. $\square$

v_Enhance wrote: The problem only asks to construct a single $n$, you can show (or guess) that $n$ should be even. If $n = 2p$ then the only solution is $n = 6$, so you do the next best thing and guess $n = 2pq$. Everything past that point is routine application of orders. How did would one prove that $n$ is even?

$946$ works since it is $2 \cdot 11 \cdot 43$ and letting $11=p$ and $43=q$ we see $\tfrac{p-1}{2} \mid 2q-1$ and $\tfrac{q-1}{2} \mid 2p-1$ so $\tfrac{p-1}{2} \mid 2q(p-1)+2q-1=2pq-1$ and we can check $2$ is a primitive root $\pmod p$ and $2pq-1$ is odd so we get $2^{2pq-1} \equiv -1 \pmod p$ so $p \mid 2^{2pq}+2$ and similarly for $q.$

Suppose $n$ is of the form $2pq$. From FLT, we have \[pq \mid 2^{\frac{(p-1)(q-1)}{2}}-1\]and we require \[2pq \mid 2^{2pq}+2 \implies pq \mid 2^{2pq-1}+1 \mid 2^{4pq-2}-1.\](Note that we must check afterwards that $pq \nmid 2^{2pq-1}-1$.) Thus it suffices to find a solution to \[9 \cdot \frac{(p-1)(q-1)}{2} = 4pq-2\]\[(p-9)(q-9)=68\]\[p=11, \quad q=43,\]and since $11 \cdot 43 \nmid 2^{945}-1$, we get our possible value of $n$ as $n = 2 \cdot 11 \cdot 43 = \boxed{946}.$

It is clear that $4 \nmid n$, so we consider some formatting of the desired number. Working case by case, we see that $n=p$, $n=2p$, and $n=pq$ all do not produce valid solutions in the desired range. Hence, we move to $n=2pq$: We require \[2pq \mid 2^{2pq}+2 \implies pq \mid 2^{2pq-1}+1 \mid 2^{4pq-2}-1,\] as long as $pq \nmid 2^{2pq-1}-1$. This essentially reads \[2^{4pq-2}\equiv1\pmod{p,q},\] implying $(p-1)\mid(4q-2)$ and $(q-1)\mid(4p-2)$, if $(p-1)\nmid(2q-1)$ and $(q-1)\nmid(2p-1)$. It is clear that $p,q \equiv 3 \pmod{4}$ so some experimenting shows us our answer of $2 \cdot 11 \cdot 43 = \boxed{946}$, which works.

Groupsolved with cursed_tangent1434. Our answer is $2 \cdot 11 \cdot 43 = 946$ \[2^{946} + 2 = 2(2^{945} + 1)\]Clearly this is divisible by $2$. \[2^{945} + 1 \equiv 2^{5} + 1 \equiv 33 \equiv 0\pmod{11}\]So it is divisible by $11$. \[2^{945} + 1 \equiv 2^{21} + 1 \equiv 2097153 \equiv 0\pmod{43}\]so $946$ works.

$n=2\cdot 11 \cdot 43$ works. The intuition comes after noticing that $n \equiv 2 \pmod{4}$ , then trying $n=2pq$ with $p,q$ primes and working with orders gives us the desired result. $$\mathbb{Q.E.D.}$$

Wow, found the same exact construction as everyone else! We claim $n = 2 \cdot 11 \cdot 43 = 946$ works. It is easy to verify that $$2^{945} \equiv (2^5)^{189} \equiv (-1)^{189} \equiv -1 \pmod{11},$$$$2^{945} \equiv (2^{42})^{22} \cdot 2^{21} \equiv 2^{21} \equiv 2 \cdot 1024^2 \equiv 2 \cdot (-8)^2 \equiv -1 \pmod{43}$$which readily implies the conclusion. My motivation was that I found $n = 2, 6$ worked so I allowed $n$ to be even. If $n = 2k$, we want $2^{2k - 1} \equiv -1 \pmod{k},$ or $2^{4k - 2} \equiv 1 \pmod{k}$. Now I then used some wishful thinking that $n$ is squarefree, as it is significantly easier to attack with orders on these types of integers. I found that $k$ could not just be $2$ times some prime, and could possibly be written in the form $2pq$ where $p, q$ are primes. The idea is to consider a stronger statement, that even $p - 1, q - 1$ could divide $4pq - 1$ which readily implies the latter statement. (It is still left to check that $2^{2k - 1}$ itself is $-1 \pmod{k}$, however.) Then it is equivalent to $p - 1 \mid 4q - 1, q - 1 \mid 4p - 1$ which gives $p, q \equiv 3 \pmod{4}$. Caseworking on $p$ upwards, it is easy to find the solution $p = 11, q = 43$, which gave the earlier construction.