(2^n + 1)/n^2 is an integer (IMO 1990 Problem 3)

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3647 posts

orl

#1 h Nov 11, 2005, 6:46 PM • 11 Y

Y by Davi-8191, Amir Hossein, itslumi, centslordm, Adventure10, megarnie, HWenslawski, arinmath, RhinocerosHornbill, Mathlover_1, Mango247

Determine all integers $n > 1$ such that
$\frac {2^n + 1}{n^2}$ is an integer.

This post has been edited 2 times. Last edited by Amir Hossein, Mar 21, 2016, 12:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#2 h Aug 15, 2008, 4:23 PM • 12 Y

Y by Amir Hossein, veehz, myh2910, centslordm, megarnie, Adventure10, HWenslawski, arinmath, Mango247, and 3 other users

Approach by maxal:

Let $N = \{ n\in\mathbb{N} : 2^n\equiv - 1\pmod{n^2} \}$ be the set of all solutions and $P = \{ p\text{ is prime} : \exists n\in N, p|n \}$ be the set of all prime factors of the solutions.

It is clear that the smallest element of $P$ is 3.
Assume that $P\ne\{3\}$ and let's try to determine the second smallest element $q = \min (P\setminus\{3\})$ .

Let $n\in N$ be a multiple of $q$ . It is important to notice that $9\not|n$ (otherwise it is easy to get that any power of $3$ divides $n$ , a non-sense). Therefore, $n = 3^t n'$ where $t = 0$ or $1$ and $n'$ does not have prime divisors smaller than $q$ .
Since $2^{2n}\equiv 1\pmod{q}$ , the multiplicative order $r = ord_q(2)$ of 2 modulo $q$ divides $2n$ . Moreover, $r$ must be even, since otherwise we would have $2^n \equiv 1\pmod{q}$ , a contradiction to the required $2^n \equiv - 1\pmod{q}$ .
Since $r < q$ we must have $r = 2$ or $2\cdot 3 = 6$ . But the numbers $2^2 - 1 = 3$ and $2^6 - 1 = 63$ deliver only one new prime factor $7$ , implying that $q = 7$ . However, in this case $r = ord_7(2) = 3$ , a contradiction. This contradiction proves that $P = \{3\}$ and thus $N = \{1,3\}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ramakrishna

6 posts

ramakrishna

#3 h Aug 28, 2008, 5:18 PM • 4 Y

Y by centslordm, megarnie, Adventure10, ehuseyinyigit

Let us assume n > 1. Obviously n is odd. Let p ≥ 3 be the smallest
prime divisor of n. In this case (p − 1, n) = 1. Since 2n + 1 | 22n − 1, we
have that p | 22n − 1. Thus it follows from Fermat’s little theorem and
elementary number theory that p | (22n − 1, 2p−1 − 1) = 2(2n,p−1) − 1.
Since (2n, p − 1) ≤ 2, it follows that p | 3 and hence p = 3.
Let us assume now that n is of the form n = 3kd, where 2, 3 d. We first
prove that k = 1.
Lemma. If 2m − 1 is divisible by 3r, then m is divisible by 3r−1.
Proof. This is the lemma from (SL97-14) with p = 3, a = 22, k = m,
α = 1, and β = r.
Since 32k divides n2 | 22n − 1, we can apply the lemma to m = 2n and
r = 2k to conclude that 32k−1 | n = 3kd. Hence k = 1.
Finally, let us assume d > 1 and let q be the smallest prime factor of d.
Obviously q is odd, q ≥ 5, and (n, q−1) ∈ {1, 3}. We then have q | 22n−1
and q | 2q−1 − 1. Consequently, q | 2(2n,q−1) − 1 = 22(n,q−1) − 1, which
divides 26 −1 = 63 = 32 · 7, so we must have q = 7. However, in that case
we obtain 7 | n | 2n + 1, which is a contradiction, since powers of two can
only be congruent to 1,2 and 4 modulo 7. It thus follows that d = 1 and
n = 3. Hence n > 1 ⇒ n = 3.
It is easily verified that n = 1 and n = 3 are indeed solutions. Hence these
are the only solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Akashnil

736 posts

Akashnil

#4 h Aug 29, 2008, 12:22 PM • 2 Y

Y by centslordm, Adventure10

ramakrishna wrote:

$\cdots$ Since 2n + 1 | 22n − 1, $\cdots$

I don't understand this

perhaps you could use latex?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chengyuLi

33 posts

chengyuLi

#5 h May 3, 2009, 11:03 AM • 2 Y

Y by centslordm, Adventure10

thanks for such a nice solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

FelixD

588 posts

FelixD

#6 h May 3, 2009, 11:49 AM • 7 Y

Y by Kunihiko_Chikaya, veehz, tck_darkness, centslordm, MELSSATIMOV40, Adventure10, Mango247

That's the official solution (see the attachment). ramakrishna copied it and so the LaTeX formulas got lost.

Attachments:

IMO1990.3.pdf (79kb)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

grupyorum

1409 posts

grupyorum

#7 h Dec 10, 2009, 7:35 PM • 3 Y

Y by centslordm, Adventure10, ehuseyinyigit

Another approach:

Let $p$ be the smallest prime divisor of $n$ . It is easy to check that, $n=3$ is obviously solution. Let $p^{a} || n$ . $p | 2^{2n}-1$ and $p | 2^{p-1} - 1$ (By the fermat's theorem), we obtain that $p=3$ . It is also obvious that n is an odd number.
Lemma: For all $n$ positive integers, $2$ is a primitive root modulo $3^{n}$ .
$3^{2a} | 2^{2n} - 1$ . Using the lemma, we get that $\phi(3^{2a}) | 2n$ . Using the power of three, we obtain that $3^{2a-1} | 3^{a}$ . This is only possible when $a \geq 2a-1$ . So $a=1$ . Now $q$ be the second smallest prime divisor of $n$ . $(2n,q-1) = 2 , 6$ . If this equals to 2, we get $q=3$ which is a contradiction.If $(2n,q-1) = 6$ then $q|63$ . We know that $q$ is different from $3$ . Hence $q$ must be $7$ . But this is impossible since
$2^{n} +1\equiv 2\mod 7$ when $n$ is divisible by $3$ . Hence the answer is $n = 3$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

enndb0x

843 posts

enndb0x

#8 h Mar 28, 2010, 12:24 AM • 3 Y

Y by centslordm, Adventure10, Mango247

FelixD, where did you find the official solution ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

neergard

47 posts

neergard

#9 h May 29, 2010, 6:47 PM • 3 Y

Y by centslordm, Adventure10, Mango247

The "official" solution is that in the shortlist, http://www.artofproblemsolving.com/Forum/download/file.php?id=1042, pp. 45-46, which is somewhat different from those posted here.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Victory.US

230 posts

Victory.US

#10 h Nov 4, 2010, 4:21 AM • 4 Y

Y by centslordm, PianoPlayer111, Adventure10, Mango247

orl wrote:

Determine all integers $n > 1$ such that
$\frac {2^n + 1}{n^2}$
is an integer.

Click to reveal hidden text

because $n^2|2^n+1$ so $n$ is odd. then $n=\prod {{p_i}^{{\alpha _i}}}$ with $p_i$ odd

$n^2|2^n+1$ lead to $v_p(n^2)<v_p(2^n+1)$

but,use the lifting exponent we have $v_p(2^n+1)=v_p(2^n-(-1)^n)=v_p(3)+v_p(n)$

if $p_i \ge 5$ then $v_p(3)=0$ .

so that we have $v_p(n^2) \le v_p(n)$ wich $n=1$

if p=3 we have $v_3(n^2) \le 1+ v_3 (n)$ then $v_3(n)=0;1$ then $n=1,3$

summary,we have n=1,n=3

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

nnosipov

245 posts

nnosipov

#11 h Nov 4, 2010, 5:03 AM • 4 Y

Y by JRM1999, centslordm, Adventure10, Mango247

Generalisation: if $p$ is an odd prime, $n>1$ and $(p-1)^n+1$ is divisible by $n^{p-1}$ , then $p=n=3$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathmdmb

1547 posts

mathmdmb

#12 h Nov 6, 2010, 7:44 AM • 3 Y

Y by centslordm, Adventure10, Mango247

nnosipov,you missed the case $n=p=2$

It was a problem from Imo with the additional condition $n<2p$ .But we can even eliminate the case $n<2p$ and much more generally prove the fact.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Vikernes

77 posts

Vikernes

#13 h Jan 8, 2011, 12:43 AM • 3 Y

Y by centslordm, Adventure10, Mango247

Some approaches of the following generalisation?
Let $a,b>1$ positive integers such that $\dfrac{a^b+1}{b^a}$ is an integer. Find all $a,b$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Amir Hossein

5452 posts

Amir Hossein

#14 h Mar 11, 2011, 4:04 PM • 8 Y

Y by Dumboi01, chirita.andrei, Imayormaynotknowcalculus, centslordm, Adventure10, Mango247, ehuseyinyigit, NicoN9

Victory.US wrote:

...but,use the lifting exponent we have $v_p(2^n+1)=v_p(2^n-(-1)^n)=v_p(3)+v_p(n)$ ...

No, this is not true. If you want to use LTE you should make sure that $p|2+1=3,$ but this is not true for any prime $p,$ and so you can't use LTE here.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathmdmb

1547 posts

mathmdmb

#15 h Mar 11, 2011, 5:01 PM • 10 Y

Y by Navi_Makerloff, Congruentisogonal44, Pal702004, centslordm, ZHEKSHEN, JG666, Adventure10, Mango247, ehuseyinyigit, endless_abyss

Well let me post my solution
Lemma:
If $n|2^n+1,n=3^k$
Proof:
Obviously $n$ odd,let $p$ be the smallest prime factor of $n,$ then
$2^{2n}\equiv 1\mod p,2^{p-1}\equiv 1\mod p\implies 2^{gcd(2n,p-1)}\equiv 1\mod p$
Since $p$ is the smallest prime factor,no prime of $p-1$ will be shared with $n,$ so $gcd(2n,p-1)=2$
Therefore $2^2\equiv 1\mod p\implies p=3$ and so let $n=3^kl$ where $3\not| l,$ but if $l>1$ similarly the smallest prime factor of $l$ is $3,$ contradiction.
Thus $n=3^k$
Now get back to original problem and we shall use Lte,so
$v_3(n^2)=2k$ and
$v_3(2^n+1)=k+1$
If $n>1,k\ge 1$ and we get $2k\le k+1\implies k\le 1$ implying $k=1$
Then the only solutions $n=\boxed {1,3}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

793 posts

shendrew7

#102 h Mar 1, 2024, 9:38 PM

Y by

ddot1 wrote:

I think that's missing a little detail: How do you know that $3$ divides $n$ only once? Otherwise, you could have something like $\gcd(2n,p_2-1)=18.$

Follows from the LTE statement - $0 < v_3(n) \leq 1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ddot1

24391 posts

ddot1

#103 h Mar 2, 2024, 3:52 AM

Y by

Oh, duh - sorry, I didn't read it carefully enough.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BestAOPS

707 posts

BestAOPS

#104 h Jul 4, 2024, 2:49 PM

Y by

The answer is $n=1,3$ . We show that there are no other solutions. Since $n$ must be odd, assume $n \geq 5$ .
Let $p$ be the least prime factor of $n$ . We have $p > 2$ since $n$ is odd. Furthermore, $2^n + 1 \equiv 0 \implies 4^n \equiv 1 \pmod{p}$ .

We claim the order of $4$ mod $p$ is $1$ . This is because the order must divide $\gcd{n, p-1}$ , which must equal $1$ otherwise $\gcd{n, p-1}$ must have smaller prime factors which also divide $n$ , contradicting $p$ 's minimality. Thus, $4 \equiv 1 \pmod{p}$ , so $p = 3$ .

In order for $n^2$ to divide $2^n + 1$ , we must have $\nu_3(n^2) = 2\nu_3(n) \leq \nu_3(2^n + 1)$ . Since $3 \mid 2 + 1$ , using the lifting the exponent lemma yields $\nu_3(2^n + 1) = 1 + \nu_3(n)$ . We then conclude that $\nu_3(n) \leq 1$ , but since $3$ is the smallest prime factor of $n$ , we must have $\nu_3(n) = 1$ .

Now, we write $n = 3k$ for some $k$ not divisible by $2$ or $3$ . Since $n \geq 5$ , we have $k > 1$ and we can let $p$ be the smallest prime factor of $k$ . But similarly to before, we see that $2^{6k} \equiv 1 \pmod{p}$ and thus $64 \equiv 1 \pmod{p}$ . This means $p \mid 63$ . Since $p \geq 5$ , we must have $p = 7$ .

This tells us that $n^2$ is divisible by $7$ . However, $2^n + 1 \equiv 8^k + 1 \equiv 2 \pmod{7}$ , so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ATGY

2502 posts

ATGY

#105 h Jul 4, 2024, 6:34 PM

Y by

Say $p$ is the smallest prime dividing $n$ , so we have $2^n + 1 \equiv 0 \mod{p} \implies 2^{2n} \equiv 1\mod{p}$ . Clearly $p \neq 2$ . Let $k$ denote the order of $2 \mod{p}$ . Observe that $k \mid 2n$ , and since $2^{p - 1} \equiv 1 \mod{p}$ , we have $k \mid (2n, p - 1) \implies k = 1, 2$ . $k = 1$ is impossible, which means $k = 2 \implies 2^2 \equiv 1 \mod{p} \implies p = 3$ .

If $q$ is the next smallest prime dividing $2^n + 1$ , we have $\text{ord}_q(2) \mid (2n, q - 1) = 3, 6$ . $q = 7$ fails upon checking.

So $p = 3$ is the only prime dividing $n$ . We need $v_3(2^n + 1) \geq v_3(n^2) = 2v_3(n)$ , for $n^2 \mid 2^n + 1$ . By LTE, $v_3(2^n + 1) = v_3(3) + v_3(n) \implies 1 + v_3(n) \geq 2v_3(n) \implies v_3(n) \leq 1$ .

$v_3(n) = 0 \implies n = 1$ , which clearly works. $v_3(n) = 1 \implies n = 3$ , which works as well. So, we are done.

This post has been edited 3 times. Last edited by ATGY, Jul 13, 2024, 11:03 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SomeonesPenguin

124 posts

SomeonesPenguin

#106 h Sep 12, 2024, 1:29 PM

Y by

The problem is equivalent to $2^n\equiv -1\pmod{n^2}$ . This implies that $2^{2n}\equiv 1\pmod{n^2}$ . Also note that $n=1$ is a solution so suppose $n\neq 1$ . Now take the smallest prime factor of $n$ (notice that this can’t be $2$ ). We have that $ord_p(2)\mid 2n$ and also note that $ord_p(2) \le p-1$ so this order must be equal to $2$ . Hence $p$ =3.

Now let $n=3^ab$ where $a\ge 1$ and $b$ is an odd integer. We have: $\nu_3(n^2)\le \nu_3(2^n+1)$ But we clearly have $\nu_3(n^2)=2a$ and from LTE $\nu_3(2^n+1)=a+1$ hence $a$ must be qual to $1$ so we get that $n=3b$ .

Plugging this back in, we get that $9k^2\mid 2^{3k}+1$ . Now $k=1$ is a solution ( $n=3$ ) so suppose that $k\neq 1$ . Let $q$ be the smallest prime factor of $k$ and note that this isn’t $2$ or $3$ . We similarly get that $2^{6k}\equiv 1\pmod q$ so $ord_q(2)\mid 6k$ so from minimality this implies $ord_q(2)\mid 6$ . Hence $ord_q(2)\in \{3,6\}$ . In either case, we get that $q=7$ so $7\mid 2^n+1$ which isn’t possible. Therefore the only solutions are $n=1$ and $n=2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Eka01

204 posts

Eka01

#109 h Oct 29, 2024, 10:22 AM

Y by

Obviously $n$ is odd.
Consider the smallest prime $p$ dividing $n$ then order of $p$ modulo $2$ divides $2n$ but not $n$ and it also divides $p-1$ implying the order must be $3$ giving that the smallest prime must be the smallest prime.
However $LTE$ gives us that $\nu_3(2^n +1)$ = $\nu_3(n) +1$ which is greater than $2\nu_3(n)$ implying $n=3k$ where $k$ is an odd number not divisible by $3$ . Plugging this and using similar order arguments, we get that $7$ divides $2^n +1$ which is false implying $k=1$ .

Hence $\boxed{n=3}$ is the only solution.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pie854

243 posts

pie854

#110 h Nov 16, 2024, 7:47 PM

Y by

The answer is $n=1,3$ which clearly works.

Suppose $n>1$ and let $p_0$ be the smallest prime divisor of $n=p_0^{e_0} p_1^{e_1} \cdots p_k^{e_k}$ with $e_i\geq 0$ for $i>0$ . Let $a=\text{ord}_{p_0^2}(2)$ . Since $p_0^2\mid 2^n+1$ , it follows that $a\nmid n$ and $a\mid 2n$ . So $a=2p_0^{f_0}p_1^{f_1} \cdots p_k^{f_k}$ where $f_i\leq e_i$ for all $0\leq i\leq k$ . But $a\mid p_0(p_0-1)$ and thus $a\leq p_0(p_0-1)$ . From this it follows that $a\in \{2, 2p_0, 2p_i\}$ for some $1\leq i\leq k$ . If $a=2$ then $p_0^2\mid 2^2-1=3$ which is absurd. If $a=2p_i$ then from $2p_i\mid p_0(p_0-1)$ it follows that $p_i\mid p_0-1$ which is absurd as well.

Thus $a=2p_0$ and $2^{2p_0}\equiv 1\pmod{p_0^2}$ . From here it's easy to get that $p_0=3$ . So $n=3m$ (by LTE $2v_3(n)\leq v_3(2^n+1)=v_3(2+1)+v_3(n)$ and thus $v_3(n)\leq 1$ and so $3\nmid m$ ) and $m^2\mid 8^m+1$ . We have $m=p_1^{e_1} p_2^{e_2}\cdots p_k^{e_k}$ and let's assume $m>1$ and that $p_1$ is the smallest prime divisor. Let $b=\text{ord}_{p_1^2}(8)$ and as before we get $b\in \{2,2p_1\}$ ( $b$ cannot be $2p_i$ because of the same reason as before). If $b=2$ then $p_1^2\mid 8^2-1=3^2\cdot 7$ but this is impossible. So $b=2p_1$ and $p_1^2\mid 8^{2p_1}-1$ . From this we get $p_1\mid 8^2-1=3^2\cdot 7$ and so $p_1=7$ . Note that $7^2\mid 42799\cdot 7^2=8^7-1$ , so $b\leq 7$ but this is a contradiction since $b=2\cdot 7=14$ . From this contradiction it follows that $m=1$ and we get the desired solution set.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EVKV

43 posts

EVKV

#111 h Dec 9, 2024, 9:49 AM

Y by

For min prime p|n
p≠3
2^2n = 1 mod p
Ord2 mod p | 2n

ord 2 mod p = 2,,2n,n,d,2d
Here d|n d>1
So it can only be 2,2d

As ord2 mod p ≤ p-1
d≥p
2d≥ 2p> p-1
Thus ord 2 mod p ≠ 2d for any d>1
Thus ord 2 mod p = 2

4= 1 mod p
So p = 3

Thus 3| n

Let q be second smallest prime
Ord 2 mod q = 2,2d,6,2n,n,3d
Where d|n
If d>3
3d>q-1
So d≤3
Now 3 cases
d= 3 X
d=2 X
d= 1 works
So ord 2 mod q = 3

Same reasoning with 2d gives
ord 2 mod q = 6

Implies q=7

Which is not possible

Hence no such q exists
Thus only 3|n
So
2vp(n) ≤ vp(3) + vp(n)
n = 3

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

972 posts

AshAuktober

#112 h Dec 11, 2024, 5:39 AM

Y by

We claim the only solution is $n = 3$ , which clearly works.

Note that $2^{2n} \equiv 1 \pmod{p}$ , where $p$ is the smallest prime factor of $n$ . But $2^{p-1} \equiv 1 \pmod p$ , and thus $2^2 = 2^{\gcd(2n, p-1)} \equiv 1 \pmod{p} \implies \boxed{p = 3}.$

Now note that we have from LTE and $\nu_p$ stuff that

$2\nu_p(n) \le \nu_p(2^n + 1) = \nu_p(3) + \nu_p(n) = 1 + \nu_p(n) \implies \nu_p(n) = 3.$ Now let $n = 2m$ where $\gcd(m, 3) = 1$ .
Then we have $m^2 \mid 8^m + 1 \implies 8^{2m} \equiv 1 \pmod{q}$ where $q$ is the smallest prime divisor of $m$ .
But $8^{q-1} \equiv 1 \pmod{q} \implies 8^2 \equiv 1 \pmod{q} \implies q \in \{3, 7\}$ .
$q = 3$ is impossible because then $\nu_p(n) \ge 2$ , and $q = 7$ is impossible because $8^m + 1 \equiv 2 \pmod{7}$ , and so $7$ can never divide the numerator. Thus in fact no such prime exists, and $m = 1 \implies \boxed{n = 3}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ItsBesi

139 posts

ItsBesi

#116 h Jan 22, 2025, 1:16 PM

Y by

Solution:

$\frac{2^n+1}{n^2}$ is an integer $\implies n^2 \mid 2^n+1$

Let $p$ be the smallest prime divisor of $n$ (such a prime exists because $n > 1$ ).

Note that $p \neq 2$ because RHS $=2^n+1 \equiv 1 \pmod 2$

So $p \mid n^2 \mid 2^n+1 \implies p \mid 2^n+1 \iff 2^n+1 \equiv 0 \pmod p \implies 2^n \equiv -1 \pmod p \implies$ $\boxed{2^{2n} \equiv 1 \pmod p}$
Also by Fermat's Little Theorem we have that : $\boxed{2^{p-1} \equiv 1 \pmod p} (\because p \neq 2 \implies gcd(2,p)=1)$
Hence $2^{\gcd(2n,p-1)} \equiv 1 \pmod p$
Note that since $p$ is the smallest prime divisor of $n$ we get that $\gcd(n,p-1)=1$ so $\gcd(2n,p-1)=1 \vee 2$

Note that since $2n \equiv 0 \pmod 2$ and $p-1 \equiv 0 \pmod 2$ we get:

$\gcd(2n,p-1)=2 \implies 2^2 \equiv 1 \pmod p \implies p \mid 3 \implies p=3 (\because p$ -prime)

Hence $3=p \mid n \implies n=3k \implies 9k^2 \mid 8^k+1$

Now suppose that $k >1$ so simmilarly as before let $q$ be the smallest prime divisor of $k$ hence we find that $8^{\gcd(2k,q-1)} \equiv 1 \pmod q$
$\gcd(2k,q-1)=2 \implies 8^2 \equiv 1 \pmod q \implies q \mid 63=7 \cdot 3^2 \implies q=3 \vee q=7$ however if $q=7$ then:
$7=q \mid 9k^2 \mid 8^k+1 \implies 7 \mid 8^k+1$ but RHS $=8^k+1 \equiv 1+1=2 \pmod 7$ so $7 \nmid RHS \rightarrow \leftarrow$

So $3=q \mid k \implies k=3 \ell \implies$ $81 \ell^2 \mid 8^{3 \ell}+1$
Now by taking $\nu_3$ we get:

$4+2 \cdot \nu_3(\ell)=\nu_3(81 \ell^2) \leq \nu_3(8^{3 \ell}+1) \stackrel{LTE}{=} \nu_3(8+1)+\nu_3(3 \cdot \ell)=3+\nu_3(\ell) \implies 4+2 \cdot \nu_3(\ell) \leq 3+\nu_3(\ell) \implies$ $\nu_3(\ell) \leq -1 \rightarrow \leftarrow$
Hence there doesn't exist a prime $q$ such that $q \mid k$ hence $k=1 \implies n=3$ which obviously works $\blacksquare$

This post has been edited 2 times. Last edited by ItsBesi, Jan 22, 2025, 2:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathfortaleza23

1 post

mathfortaleza23

#117 h Jan 27, 2025, 8:42 PM

Y by

what is r ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#118 h Feb 18, 2025, 2:12 AM

Y by

Observe that $n$ must be odd, and suppose that $n>1$ . Letting $p$ be the minimal prime divisor of $n$ , we have $2^n\equiv-1\pmod p$ and thus $4^n\equiv1\pmod p$ . We also have $4^{p-1}\equiv1\pmod p$ . By minimality $\gcd(n,p-1)=1$ , so it follows that $p=3$ .

Let $k=\nu_3(n)$ and $m=\frac{n}{3^k}$ . Then $\nu_3(2^n+1)=\nu_3(2^{3^km}-(-1)^{3^km})=v_3(3^km)+v_3(3)=k+1$ from exponent lifting, giving $2k=\nu_3(n^2)\le\nu_3(2^n+1)=k+1$ . Thus $k=1$ .

Hence, write $n=3m$ for $3\nmid m$ , so that $n^2\mid 2^n+1$ occurs if and only if $m^2\mid 8^m+1$ . Let $q$ be the smallest prime factor of $m$ . Then similarly $64\equiv64^{\gcd(m,q-1)}\equiv1\pmod q$ . Hence $q\in\{3,7\}$ , but $q\neq 3$ as $3\nmid m$ . and $q\neq 7$ as $8^m\equiv-1\pmod q$ . Thus $q$ cannot exist; in other words, we have $m=1$ .

Our solution set for $n$ is thus $\boxed{\{1,3\}}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

John_Mgr

62 posts

John_Mgr

#119 h Mar 29, 2025, 12:40 PM

Y by

smileapple wrote:

Observe that $n$ must be odd, and suppose that $n>1$ . Letting $p$ be the minimal prime divisor of $n$ , we have $2^n\equiv-1\pmod p$ and thus $4^n\equiv1\pmod p$ . We also have $4^{p-1}\equiv1\pmod p$ . By minimality $\gcd(n,p-1)=1$ , so it follows that $p=3$ .

Let $k=\nu_3(n)$ and $m=\frac{n}{3^k}$ . Then $\nu_3(2^n+1)=\nu_3(2^{3^km}-(-1)^{3^km})=v_3(3^km)+v_3(3)=k+1$ from exponent lifting, giving $2k=\nu_3(n^2)\le\nu_3(2^n+1)=k+1$ . Thus $k=1$ .

Hence, write $n=3m$ for $3\nmid m$ , so that $n^2\mid 2^n+1$ occurs if and only if $m^2\mid 8^m+1$ . Let $q$ be the smallest prime factor of $m$ . Then similarly $64\equiv64^{\gcd(m,q-1)}\equiv1\pmod q$ . Hence $q\in\{3,7\}$ , but $q\neq 3$ as $3\nmid m$ . and $q\neq 7$ as $8^m\equiv-1\pmod q$ . Thus $q$ cannot exist; in other words, we have $m=1$ .

Our solution set for $n$ is thus $\boxed{\{1,3\}}$ . $\blacksquare$

$n>1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

John_Mgr

62 posts

John_Mgr

#120 h Mar 29, 2025, 1:58 PM

Y by

I too posted it.

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

576 posts

cursed_tangent1434

#121 h Apr 6, 2025, 6:55 AM

Y by

We claim that the only positive integers $n$ which satisfy the given condition are $n=1$ and $n=3$ . It is clear that these solutions work, so we shall now show that they are the only ones.

Since $n=1$ clearly works, we consider $n>1$ in what follows. Further, the left hand side is clearly odd for all $n \ge 1$ so we must have $n$ being odd. We first show the following.

Claim : For any positive integer $n$ which satisfies the given divisibility, $3$ must be the smallest prime divisor of $n$ .

Proof : Let $q$ denote the smallest prime divisor of $n$ . Since $q \mid n^2 \mid 2^n+1$ it follows that $2^{2n} \equiv 1 \pmod{q}$ . Thus, $\text{ord}_q(2) \mid 2n$ . Also, $\text{ord}_q(2) \mid q-1$ so if there exists an odd prime $r \mid \text{ord}_q(2)$ we have $r \mid 2n$ so $r \mid n$ . But, $r \mid q-1$ so $r \le q-1 <q$ which contradicts the minimality of $q$ . Thus, $\text{ord}_q(2)$ is a perfect power of two. Now, since $\nu_2(2n)=1$ as $n$ is odd we must have $\text{ord}_q(2) =2$ . Thus,
$0 \equiv 2^n+1 \equiv 2 +1 \equiv 3 \pmod{q}$ which holds if and only if $q=3$ as desired.

Now note,
$2\nu_3(n)=\nu_3(n^2) \le \nu_3(2^n+1) = \nu_3(2+1)+\nu_3(n)=\nu_3(n)+1$ which implies that $\nu_3(n)=1$ . Thus, if $n$ is a power of $3$ it must be $3$ itself, which works. Next, we consider $n>3$ and hence, there exists a second smallest prime divisor $s>3$ of $n$ . As before note that if $\text{ord}_s(2)$ is not a power of two, $n$ must have a smaller prime divisor than $s$ . Thus, $\text{ord}_s(2)$ can only have factors of $2$ and $3$ in it's prime factorization. However, as noted before, $\nu_2(2n) =1$ and $\nu_3(2n)=1$ so the only possibilities are $\text{ord}_s(2)=2$ and $\text{ord}_s(2)=6$ . The former implies that $s=3$ which is a contradiction while the second implies $2^6 \equiv 1 \pmod{s}$ which requires $s \mid 63$ . Thus we must have $s=7$ . But it is not hard to check that $2^n+1 \not \equiv 0 \pmod{7}$ over all positive integers $n$ so this is a contradiction and we are done.

Z K Y