IMO ShortList 1998, number theory problem 5

The post below has been deleted. Click to close.

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

orl

3647 posts

orl

#1 h Oct 22, 2004, 3:08 PM • 11 Y

Y by Davi-8191, pog, HWenslawski, rg_ryse, Adventure10, jhu08, megarnie, mathmax12, Mango247, WiseTigerJ1, cubres

Determine all positive integers $n$ for which there exists an integer $m$ such that ${2^{n}-1}$ is a divisor of ${m^{2}+9}$ .

Attachments:

This post has been edited 1 time. Last edited by orl, Oct 23, 2004, 12:41 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 Oct 22, 2004, 3:08 PM • 7 Y

Y by pog, Adventure10, rg_ryse, jhu08, Mango247, WiseTigerJ1, cubres

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

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

grobber

7849 posts

grobber

#3 h Oct 22, 2004, 4:55 PM • 19 Y

Y by numbertheorist17, SupermemberVN, randomasdf97, baopbc, hmida99, Polynom_Efendi, Williamgolly, pog, Adventure10, rg_ryse, jhu08, Mango247, MarioLuigi8972, WiseTigerJ1, Stuffybear, ehuseyinyigit, cubres, and 2 other users

Assume $n$ is not a power of $2$ . In this case there is an odd number $k\ge 3$ s.t. $2^k-1|2^n-1|m^2+9$ . $2^k-1$ is of the form $4t+3$ , so it has a prime factor of the form $4t+3$ and $\ne 3$ , because $3\not |\ 2^k-1$ , so it can't divide $m^2+9$ because if a prime of the form $4t+3$ divides $a^2+b^2$ , then it divides $a,b$ . This means that $n$ must be a power of $2$ .

On the other hand, assume $n=2^k$ . In this case, the only prime of the form $4t+3$ which divides $2^n-1$ is $3$ . Indeed, let $p$ be such a prime. We then have $p|(2^{2^k}-1,2^{p-1}-1)=2^{(2^k,p-1)}-1=2^2-1=3$ (because $p-1=4t+2$ ). At the same time, $9\not |2^n-1$ (because $9|2^n-1\iff 6|n$ ), so $2^n-1$ is of the form $3\alpha$ , where $\alpha$ has only divisors of the form $4t+1$ , so there is some $m'$ s.t. $\alpha|m'^2+1$ . All we need to do now is to take $m=3m'$ , and we have found $m$ s.t. $2^n-1|m^2+9$ .

Z K Y

The post below has been deleted. Click to close.

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

abdurashidjon

119 posts

abdurashidjon

#4 h Jun 12, 2006, 2:12 AM • 6 Y

Y by pog, Adventure10, jhu08, WiseTigerJ1, cubres, and 1 other user

grobber wrote:

Assume $n$ is not a power of $2$ . In this case there is an odd number $k\ge 3$ s.t. $2^k-1|2^n-1|m^2+9$ . $2^k-1$ is of the form $4k+3$ , so it has a prime factor of the form $4t+3$ and $\ne 3$ , because $3\not |\ 2^k-1$ , so it can't divide $m^2+9$ because if a prime of the form $4t+3$ divides $a^2+b^2$ , then it divides $a,b$ .

Hi here grobber has used that if an number is of the form $4k+3$ then it will a prime divisor of the same form, and also, if a number of the form $4k+3$ divides $a^2+b^2$ then it have to divide $a, b$
Abdurashid

Z K Y

The post below has been deleted. Click to close.

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

ZetaX

7579 posts

ZetaX

#5 h Jun 13, 2006, 8:57 PM • 6 Y

Y by pog, Adventure10, jhu08, WiseTigerJ1, cubres, and 1 other user

And what do you want to tell us by this¿

Z K Y

The post below has been deleted. Click to close.

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

Davron

484 posts

Davron

#6 h Jun 15, 2006, 3:24 PM • 6 Y

Y by pog, Adventure10, jhu08, Mango247, WiseTigerJ1, cubres

i think he wants the proofs for this facts

davron

Z K Y

The post below has been deleted. Click to close.

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

Yimin Ge

253 posts

Yimin Ge

#7 h Jun 20, 2006, 1:21 AM • 8 Y

Y by pog, Adventure10, jhu08, looosp, Hexagrammum16, Mango247, WiseTigerJ1, cubres

Hm...my solution is much much longer and uglier than grobbers but since ML is a kind of archieve of solutions I've found (and they are precious few), I think I'll post it:

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

KingSmasher3

1399 posts

KingSmasher3

#8 h Jul 22, 2013, 4:08 PM • 6 Y

Y by pog, jhu08, TomMae10, Adventure10, WiseTigerJ1, cubres

abdurashidjon wrote:

grobber wrote:

Assume $n$ is not a power of $2$ . In this case there is an odd number $k\ge 3$ s.t. $2^k-1|2^n-1|m^2+9$ . $2^k-1$ is of the form $4k+3$ , so it has a prime factor of the form $4t+3$ and $\ne 3$ , because $3\not |\ 2^k-1$ , so it can't divide $m^2+9$ because if a prime of the form $4t+3$ divides $a^2+b^2$ , then it divides $a,b$ .

Hi here grobber has used that if an number is of the form $4k+3$ then it will a prime divisor of the same form, and also, if a number of the form $4k+3$ divides $a^2+b^2$ then it have to divide $a, b$
Abdurashid

Seven years ago, but for future reference, here is the proof. Consider a number of the form $4k+3.$ Clearly, all its prime factors must be of the form $4m+1$ or $4m+3.$ Since $4k+3 \equiv 3\pmod 4,$ the factors cannot all be $1\pmod 4,$ so there must be at least one prime factor of the form $4m+3.$

Now suppose that a prime $4m+3$ divides $a^2+b^2.$ Let $a^2 \equiv j\pmod{4m+3}.$ Assume for sake of contradiction that $j \neq 0.$ Then $b^2 \equiv -j\pmod{4m+3}.$ So we obtain $a^{4m+2} \equiv j^{2m+1}\pmod{4m+3}$ and $b^{4m+2} \equiv -j^{2m+1}\pmod{4m+3}.$ However, by FLT, we must have $j^{2m+1}=-j^{2m+1}=1,$ a contradiction. Therefore, $a \equiv b \equiv 0\pmod{4m+3}.$

Z K Y

The post below has been deleted. Click to close.

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

iarnab_kundu

866 posts

iarnab_kundu

#9 h Oct 10, 2013, 2:19 PM • 6 Y

Y by pog, jhu08, Adventure10, Mango247, WiseTigerJ1, cubres

I shall be using the fact that if any prime $p$ of the form $4k-1$ divides $m^2+9$ then $p=3$ .
Firstly as $2^n-1\equiv -1\pmod{4}$ for $n>1$ we have $n=2s$ for some integer $s$ , otherwise $3\nmid 2^n-1$ .

If $n$ has any prime factor $q\neq 2$ , then $2^q-1\nmid 2^s-1$ . But $2^q-1$ has a prime factor of the form $4k-1$ which is greater than $3$ . Hence $n=2^t$ for some integer $t$ .

The rest is easy, let $2^{2^t}-1=3p_1^{\alpha_1}\cdots p_n^{\alpha_n}$ .
By Chinese Remainder Theorem there exists a solution to
$\begin{cases}X\equiv x_1\pmod{p_1^{\alpha_1}}\\ \cdots\\X\equiv x_n\pmod{p_n^{\alpha_n}}\end{cases}$ Where $p_i^{\alpha_i}\mid x_i^2+1$ . Easy to see such $x_i$ exists.
Now $3X$ suffices.

SO the answer is $\boxed{n=2^t}$ for some non-negative integer $t$ .

Z K Y

The post below has been deleted. Click to close.

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

KingSmasher3

1399 posts

KingSmasher3

#10 h Jan 11, 2014, 7:06 AM • 5 Y

Y by pog, jhu08, Adventure10, WiseTigerJ1, cubres

Alternative Solution with Legendre's Symbol

Z K Y

The post below has been deleted. Click to close.

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

Eray

381 posts

Eray

#11 h Oct 9, 2014, 10:33 AM • 7 Y

Y by pog, jhu08, joseph02, Adventure10, Mango247, WiseTigerJ1, cubres

$2^n - 1 \mid m^2 + 9$

Let's assume $n$ has a prime divisor $p$ different than $2$

Therefore $2^p-1\mid2^n-1$ , and $2^p-1$ has a prime divisor which is different than $3$ , and it's equivalent $3$ in $\mod4$ . Assume it's $q$

Since $q\mid 2^p-1\mid m^2+9$ , $-9$ is a quadratic residue in $\mod q$

By Legendre's Symbol, we have

$1=\left(\dfrac{-9}{q}\right)=\left(\dfrac{-1}{q}\right) \cdot \left(\dfrac{9}{q}\right)$

Since $\left(\dfrac{9}{q}\right)$ is always equal to $1$ , $\left(\dfrac{-1}{q}\right)$ must also be equal to $1$

Hence, $q \not\equiv 3 \mod4$ . Contradiction.

Therefore, $n$ can't have a prime divisor different than $2$ . So $n=2^k$

Now, we will use induction to prove $n=2^k$ always satisfies.

We will be done if $2^n-1$ doesn't have any prime divisor different than $3$ , and equivalent $3$ in $\mod4$ . Because if it really doesn't, $-1$ and so $-9$ will be a quadratic residue in all of it's prime divisors modulo, so it also will be in modulo $2^n-1$ . And that's what we want.

For $k=1$ , $2^n-1=3$ satisfies the condition. Assume also $2^{2^k}-1$ satisfies.

$2^{2^{k+1}}-1=\left(2^{2^k}+1\right)\left(2^{2^k}-1\right)$ . We know the second factor satisfies. So we have to show $2^{2^k}+1$ also satisfies.

$r\mid 2^{2^k}+1 \Longrightarrow 2^{2^k} \equiv -1 (\mod r)$ . So $-1$ is a quadratic residue in $\mod r$ . Hence $r$ can't be equivalent $3$ in $\mod 4$ . Therefore, we're done.

This post has been edited 1 time. Last edited by Eray, Oct 10, 2014, 8:44 AM

Z K Y

The post below has been deleted. Click to close.

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

TheOverlord

97 posts

TheOverlord

#12 h Oct 9, 2014, 10:38 AM • 6 Y

Y by pog, jhu08, Adventure10, Mango247, WiseTigerJ1, cubres

Eray wrote:

For $k\ge3$ , $2^{2^3}-1\mid 2^{2^k}-1$ . So $127\mid 2^{2^k}-1$

But $2^{2^3}-1=255$ !!!

Z K Y

The post below has been deleted. Click to close.

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

Eray

381 posts

Eray

#13 h Oct 10, 2014, 8:46 AM • 5 Y

Y by pog, jhu08, Adventure10, WiseTigerJ1, cubres

I have corrcted my solution. Thank you @TheOverlord

Z K Y

The post below has been deleted. Click to close.

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

sayantanchakraborty

505 posts

sayantanchakraborty

#14 h Oct 13, 2014, 5:41 PM • 5 Y

Y by pog, jhu08, Adventure10, WiseTigerJ1, cubres

First of all note that if $2^n-1$ has a prime divisor $p \equiv 3\pmod{4}$ other than $3$ then $-9$ is not a quadratic residue modulo $2^n-1$ ,because $(-9)^{\frac{p-1}{2}}=-3^{p-1} \equiv -1\pmod{p}$ and this follows at once by Euler's criterion and composite quadratic residue law.

Now if $n$ has an odd prime divisor $j$ then $2^j-1$ is a factor of $2^n-1$ so the latter has a prime divisor $p \equiv 3\pmod{4}$ (other than $3$ since $j$ is odd) so our condition is not satisfied.

So it remains to check for $n=2^k$ ( $n=1$ case is obvious).

The crucial fact is that if an odd prime $p \equiv 3\pmod{p}$ other than $3$ divides $2^{2^k}-1$ then since it also divides $2^{p-1}-1$ it must also divide $2^{\text{gcd}(2^k,p-1)}-1=2^2-1=3$ .This is a contradiction.

Also see that $2^{2^k}-1=(2^{2^{k-1}}-1)(2^{2^{k-1}}+1)$ inducting backwards we see that the highest power of $3$ dividing it cannot exceed the highest power of $3$ dividing $2^8-1=255$ ,i.e, $2$ .(note that the latter factor is not divisible by $3$ for $k \ge 2$ )

Finally we see that all the primes of $2^{2^k}-1$ other than $3$ are $\equiv 1\pmod{4}$ hence $-9$ is a quadratic residue of each of them(one may see this by applying Euler's criterion: $(-9)^{\frac{p-1}{2}}=3^{p-1} \equiv 1\pmod{p}$ ).Also we may choose $l$ so that the highest power of $3$ in $2^{2^k}-1$ divides $l^2+9$ .Now applying CRT we may find $m$ .

Thus the answer to our problem is $n=1,2^k \forall k \in \mathbb{Z^+}$

Z K Y

The post below has been deleted. Click to close.

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

cobbler

2180 posts

cobbler

#15 h Mar 25, 2015, 10:48 PM • 5 Y

Y by pog, jhu08, Adventure10, WiseTigerJ1, cubres

An easy proof that $n$ is a power of $2$ .

Let $n=2^a b$ where $a\ge 0$ and $b$ is odd and let $p$ be a prime factor of $2^b-1$ , hence $p\mid 2^b-1\mid 2^n-1\mid m^2+9$ and so $m^2\equiv -3^2\pmod p$ . Since $b$ is odd we have $3\nmid 2^b-1$ giving $p\ne 3$ , therefore the last congruence implies that $-1$ is a quadratic residue of $p$ , implying that $p\equiv 1\pmod 4$ . It follows that $2^b-1\equiv 1\pmod 4$ , thus $b=1$ . So $n=2^a$ .

This post has been edited 1 time. Last edited by cobbler, Mar 25, 2015, 10:50 PM
Reason: A silly

Z K Y

The post below has been deleted. Click to close.

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

lnzhonglp

120 posts

lnzhonglp

#55 h Dec 26, 2023, 5:15 AM • 1 Y

Y by cubres

The answer is when $n$ is a power of $2$ , including $n = 1$ .

Proof n must be a power of 2:
Assume $n \geq 3$ is not a power of $2$ . Then there exists an odd integer $k$ such that $2^k-1 \mid 2^n - 1 \mid m^2 + 3^2.$ Since $2^k -1 \equiv 3 \pmod 4$ , $2^k -1$ must have a $3 \pmod 4$ prime factor. From Fermat's Christmas Theorem, $2^k -1$ cannot have any $3 \bmod 4$ prime factors other than $3$ . However, $2^k-1 \equiv (-1)^k -1 \equiv 1 \pmod 3,$ so this is impossible. Therefore, $n$ must be a power of $2$ .

Proof n is a power of 2 works:
Let $n = 2^k$ , and $p$ be a prime such that $p \mid 2^{2^k} - 1$ . Let the $a$ be the order of $2 \pmod p$ . Then $a \mid \gcd(2^k, p-1).$ If $p \equiv 3 \pmod 4$ , we must have $a = 2$ , so $p = 3$ . Therefore, $3$ is the only $3 \pmod 4$ prime factor of $2^{2^k} -1$ , and all other prime factors are $1\pmod 4$ . If $3^2 \mid 2^{2^k} - 1$ , then we get $6 \mid 2^k$ , since the order of $2 \pmod 9$ is $6$ . This is clearly impossible, therefore $9 \nmid 2^{2^k}$ . Thus, from Fermat's Christmas Theorem, there exists $m$ such that $2^{2^k} - 1 \mid m^2 + 9$ .

Z K Y

The post below has been deleted. Click to close.

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

AlanLG

241 posts

AlanLG

#56 h Jan 30, 2024, 7:23 PM • 1 Y

Y by cubres

nice

$\boxed{\text{The answer are all powers of 2.} }$ Claim. $n$ must be a power of $2$
take a odd divisor $k>1$ of $n$ , then $2^k-1\mid 2^n-1\mid m^2+9$ by Fermat Christmas Theorem all prime divisors of $m^2+9$ are $1\pmod 4$ or $3$ , but $2^k-1\not\equiv 3\pmod 3$ as $k$ odd, nor $2^k-1\equiv 1 \pmod 4$ , a contradiction.

Claim. all powers of $2$ work.
Let $n=2^k$ , write $2^{2^k}-1=(2+1)(2^2+1)(2^{2^2}+1)\cdots (2^{2^{k-1}}+1)$ Note that each term except for the first one, by Fermat Christmas Theorem have only $1\pmod 4$ prime divisors, so choose $g$ a primitive root $\pmod {p^\theta}$ then by Chinese Remainder Theorem exists $m$ such that $m\equiv 3 g^{\frac{\phi({p^\theta})}{4}}\pmod {p^\theta} \hspace{0.4cm}\forall\hspace{0.2cm} p\mid 2^{2^j}+1 \hspace{0.5cm}\text{and} \hspace{0.5cm} m\equiv 0\pmod 3$ then $p^\theta\mid m^2+9$ , and $3\mid m^2+9$ , as $\text{Fermat numbers}$ are relative primes we would have that $2^{2^n}-1\mid m^2+9$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

joshualiu315

2513 posts

joshualiu315

#57 h Feb 12, 2024, 8:17 PM • 1 Y

Y by cubres

The answer is $\boxed{\text{powers of 2}}$ .

Let $d$ be the largest odd prime divisor of $n$ . For the sake of contradiction, assume $d>1$ . Fermat's Christmas Theorem states that the factors of $m^2+9$ are either $1 \pmod{4}$ or $3$ . Since $2^d-1$ divides $2^n-1$ , all the factors of $2^d-1$ are either $1 \pmod{4}$ or $3$ . Then, as

$2^d-1 \equiv 3 \pmod{4},$
it must contain a factor that is $3 \pmod{4}$ , contradicting our assumption that $d>1$ .

To prove the powers of $2$ work, induction with difference of squares easily works.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

794 posts

shendrew7

#58 h Feb 29, 2024, 4:31 AM • 1 Y

Y by cubres

Our answer is $\boxed{n=2^b, b \ge 0}$ . The most convenient method to show each works is by setting $m=3a$ . Our condition is reduced to proving there exists such an $a$ with
$2^{2^b}-1 = 3\left(2^2+1\right)\left(2^{2^2}+1\right) \ldots \left(2^{2^{b-1}}-1\right) \mid 3(a^2+1) \mid (3a)^2+9.$
Since the Fermat primes are pairwise relatively prime, and we have the solution $a \equiv 2^{2^{t-1}} \pmod{2^{2^t}+1}$ for each $t$ , there must exist such an $a$ .

Otherwise, suppose $p>1$ is an odd prime divisor of $n$ . Then neither 2 or 3 are factors of $2^p-1 \equiv 3 \pmod 4$ , so Fermat's Christmas Theorem tells us we must have $p \equiv 1 \pmod 4$ for all prime divisors of $n$ , contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

peppapig_

280 posts

peppapig_

#60 h Mar 14, 2024, 12:47 AM • 1 Y

Y by cubres

Since it's not specified that $m$ has to be an integer, the answer is obviously all positive integers $n$ ! (Just kidding! Real solution below)

I claim that the answer is all $n$ that can be expressed in the form of $2^k$ for some nonnegative integer $k$ .

First, note that by Fermat's Christmas Theorem, if a prime $p$ divides $m^2+3^2$ , then it is either $1$ mod $4$ or it divides $\gcd(m,3)$ . Using this, I now claim that $n$ cannot have any prime factor $p$ that is larger than $2$ . FTSOC, assume that $p\mid n$ , where $p>2$ . This then implies that
$2^p-1\mid 2^n-1,$ and since $p>2$ , we have that $2^p-1$ must be $3$ mod $4$ . Additionally, since $p$ is a prime $>2$ , this means that $p$ is odd, implying that
$2^p-1 \equiv 2-1\equiv 1\mod 3,$ so if $2^p-1$ is $3$ mod $4$ , some other prime $q\neq 3$ divides $2^p-1$ , a contradiction to the Christmas Theorem statement. Therefore $n$ cannot have any prime factor $p>2$ , meaning that $n$ must be in the form of $2^k$ in order for $2^n-1$ to have a multiple in the form of $m^2+9$ .

I now claim that for all $n=2^k$ , $2^n-1$ has a multiple of the form $m^2+9$ . I will prove this using induction. Suppose that $2^{2^k}-1$ for $k\geq 1$ has a multiple of the form $m^2+9$ . This implies that $-9$ is a quadratic residue mod $2^{2^k}-1$ . Now, note that
$2^{2^{k+1}}-1=(2^{2^k}-1)(2^{2^k}+1),$ and that $\gcd(2^{2^k}-1,2^{2^k}+1)=1$ . Therefore, since we already know that $-9$ is a quadratic residue mod $2^{2^k}-1$ , we just need to prove that $-9$ is also a quadratic residue mod $2^{2^k}-1$ . Since the two modulos are relatively prime, by CRT, this will also prove that $-9$ is a quadratic residue mod $2^{2^{k+1}}-1$ , meaning that a multiple of $2^{2^{k+1}}-1$ in the form of $m^2+9$ .

Using this, notice that,
$(2^{2^{k-1}})^2 \equiv -1 \mod (2^{2^{k}}+1) \iff (3*2^{2^{k-1}})^2 \equiv -9 \mod (2^{2^{k}}+1),$ which proves that $-9$ is indeed a quadratic residue mod $2^{2^{k}}+1$ . Therefore, if there exists a multiple of $2^{2^{k}}+1$ in the form of $m_1^2+9$ , then there exists a multiple of $2^{2^{k+1}}+1$ in the form of $m_2^2+9$ !

Finally, to complete our induction, we need to cover the base case of $n=2$ and the external case $n=1$ . The latter is covered by $m=0$ and the former also by $m=0$ . Therefore, there exists a multiple of $2^n-1$ in the form of $m^2+9$ if and only if $n$ is a power of $2$ , finishing the problem.

This post has been edited 2 times. Last edited by peppapig_, Mar 14, 2024, 12:48 AM
Reason: Parentheses

Z K Y

The post below has been deleted. Click to close.

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

SenorSloth

37 posts

SenorSloth

#61 h Jun 14, 2024, 3:52 PM • 2 Y

Y by OronSH, cubres

We claim that the answer is $n=2^x$ for some nonnegative integer $x$ .

We start by proving that all other numbers fail. For any odd integer $n>1$ , we have that $3\nmid 2^n-1$ . We also have that $2^n-1\equiv 3\pmod{4}$ , which implies that $2^n-1$ must have some prime divisor $p\equiv 3\pmod{4}$ , and $p\neq3$ . Since we require $2^n-1\mid m^2+9$ , this prime must also divide $m^2+9$ . However, we can then apply Fermat's Christmas theorem on $m^2+9$ to show that any prime $p$ dividing $m^2+3^2$ is either $p\equiv 1\pmod{4}$ or $p=3$ , contradiction. Any even $n$ that is not a power of $2$ will have some odd factor $x>1$ , and since $2^x-1\mid 2^n-1$ we get the same contradiction.

Now we prove that $n=2^k$ works. $k=0$ gives $2^n-1=1$ , which clearly works. We will now prove that for positive $k$ , $2^{2^k}-1$ is the product of $3$ and some (not necessarily distinct) primes that are $1\pmod{4}$ . We will use induction to do this, with base case $k=1$ and $2^{2^k}-1=3$ . For the inductive step, we notice that $2^{2^{k+1}}-1=(2^{2^k}-1)(2^{2^k}+1)$ , so we just need to prove that $2^{2^k}+1$ only has prime factors that are $1\pmod 4$ . This is true by applying Fermat's Christmas Theorem, so the induction is complete.

Now we just need to show there exists a working $m$ . We can factor $2^n-1$ into powers of distinct primes, and consider each prime power separately. For the factor of $3$ , just select $m\equiv0\pmod{3}$ . For the other primes, which must have $p\equiv 1\pmod{4}$ , we need to show that there exists a value of $m\pmod{p^k}$ such that $m^2+9\equiv\left(\frac m3 \right)^2+1\equiv 0 \pmod{p^k}$ . It is well-known that there exists a primitive root $g$ with order $\phi(p^k)=(p-1)(p^{k-1})$ . Since we know $\frac{p-1}{4}$ is an integer, we can let $\frac m3\equiv g^{\frac{(p-1)(p^{k-1})}{4}}\pmod{p^k}$ so that $\left(\frac m3 \right)^2\equiv -1 \pmod{p}$ . Then we just multiply by $3$ to get a working value for $m\pmod{p^k}$ . Then by applying CRT on all of the separate prime powers, we know that there will exist a value of $m$ such that $m^2+9$ is divisible by all of the prime powers together, and 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.

blueberryfaygo_55

340 posts

blueberryfaygo_55

#62 h Aug 16, 2024, 3:36 AM • 2 Y

Y by megarnie, cubres

The answer is all $n =2^k$ where $k$ is a nonnegative integer. We first introduce the following lemma.

Lemma. For $n>1$ , every prime divisor of $2^n-1$ is either $3$ or congruent to $1 \pmod 4$ if and only if $n$ is a power of $2$ .
Proof. First suppose that $n=2^k$ , and let $p$ be a prime divisor of $2^n-1$ . We have $2^{2^k} \equiv 1 \pmod p$ so letting $\mathrm{ord}_p(2) = r$ , it follows that $\begin{cases} r \mid 2^k \\ r \mid p-1 \end{cases}$ so $r=2^l$ for $l \geq 1$ . If $l=1$ , then $4 \equiv 1 \pmod p$ or $p=3$ ; otherwise, $r \equiv 0 \pmod 4$ , so we must have $4 \mid p-1$ or $p \equiv 1 \pmod 4$ .
Now, we show that if every prime divisor $p$ of $2^n-1$ is either $3$ or congruent to $1 \pmod 4$ , then $n$ must be a power of $2$ . For the sake of contradiction, suppose $n$ is not a power of $2$ . Then, $n = 2^u \cdot w$ where $u$ is a nonnegative integer and $w$ is an odd integer greater than $1$ . We know that $2^w - 1 \mid 2^n - 1$ but $2^w - 1 \equiv (-1)^w - 1 \equiv 1 \not \equiv 0 \pmod 3$ , so every prime dividing $2^w-1$ is congruent to $1 \pmod 4$ . It is then clear that $2^w - 1 \equiv 1 \pmod 4$ so $w=1$ , a contradiction, giving the lemma. $\blacksquare$

Returning to the problem, suppose $q$ is a prime divisor of $2^n-1$ . The given condition implies that $m^2 \equiv -9 \pmod q$ so either $q=3$ or $\left(\dfrac{-9}{q}\right) = \left(\dfrac{9}{q}\right) \left(\dfrac{-1}{q}\right) = \left(\dfrac{-1}{q}\right) = -1.$ It follows that $q \equiv 1 \pmod 4$ , but $q$ is an arbitrary prime dividing $2^n-1$ , so every prime dividing $2^n-1$ is congruent to $1 \pmod 4$ . Applying the lemma finishes, since if $n$ is a power of $2$ , we have $-9$ as a quadratic residue modulo every prime divisor of $n$ (or divisible by the prime divisor $3$ ), and the construction of $m$ follows from using the Chinese Remainder Theorem on the prime divisors of $n$ . $\blacksquare$

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

#63 h Oct 7, 2024, 2:05 PM • 1 Y

Y by cubres

Been a while since I wrote solutions.
We claim that the answer is all $n$ of the form $\boxed {n=2^k}$ .
First note by Fermat's Two Squares Theorem that any prime factor of $m^2+9$ is either equal to $3$ or congruent to $1(mod \ 4)$ .
Now if $n$ is odd, it is trivial to observe that $2^n -1 \equiv 3(mod \ 4)$ for $n \geq 3$ so it follows that the required $n$ must be of the form $2^k$ . We now show that these indeed work.
Proceed by induction.
We assume that $2^{2^k} -1 | m^2 +9$ . Now we need to show that $2^{2^{k+1}} -1 | (m+a)^2 +9$ or that $a^2 +2am$ is divisible by $2^{2^k} -1$ and $2^{2^k} +1$ . Since they are both coprime, the result follows by $CRT$ (This probably requires some care but good enough for a comeback I suppose).

Z K Y

The post below has been deleted. Click to close.

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

onyqz

195 posts

onyqz

#64 h Oct 25, 2024, 5:54 PM • 1 Y

Y by cubres

great problem
solution

Z K Y

The post below has been deleted. Click to close.

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

SomeonesPenguin

125 posts

SomeonesPenguin

#65 h Nov 24, 2024, 11:25 AM • 1 Y

Y by cubres

The answer is $n=2^k$ where $k$ is a positive integer. We will use the following lemma:

If $p\equiv 3\pmod 4$ and $p\mid x^2+y^2$ , then $p\mid x$ and $p\mid y$ .

In particular, this means that $2^n-1$ has at most one prime factor that is $3$ modulo $4$ , which is $3$ . Suppose now that there is some prime number $p\mid n$ , $p\equiv 3\pmod 4$ . Clearly $2^p-1\mid 2^n-1\mid m^2+9$ Notice now that $2^p-1\equiv 3\pmod 4$ so it must have a prime factor that is $3$ modulo $4$ . This also can't be $3$ since $3\nmid 2^p-1$ (because $p$ is odd), hence we get a contradiction.

Therefore, $n=2^k$ for some positive integer $k$ . We prove that all such $n$ work.

Note that we basically don't care about the $3$ in $2^{2^k}-1$ since from LTE $\nu_3\left(2^{2^k}-1\right)=1$ so we can just take $3\mid m$ .

Now I claim that the only prime factor that is $3$ modulo $4$ of $2^{2^k}-1$ is $3$ .
Proof: Note that $2^{2^k}-1=(2+1)\left(2^2+1\right)\dots\left(2^{2^{k-1}}+1\right)$ Besides the first factor, all of them are of the form $x^2+1$ so they can't have a prime factor $p\equiv 3\pmod 4$ . $\square$

For any other prime number $p\mid 2^{2^k}-1$ (note that from the above we have $p\equiv 1\pmod 4$ ) we have $\gcd(3,p)=1$ so $3\mid m$ doesn't affect us. Now note $\left(\dfrac{-9}{q}\right)=\left(\dfrac{-1}{q}\right) \cdot \left(\dfrac{9}{q}\right)=1$ So there is some $m$ such that $p\mid m^2+9$ . Therefore, by CRT we can find the desired $m$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

EpicBird08

1747 posts

EpicBird08

#67 h Dec 6, 2024, 7:02 PM • 1 Y

Y by cubres

Does my proof of sufficiency work?

The answer is $n = 2^k$ . Assume $n > 1$ since $n = 1$ trivially holds.

Necessity: Suppose that an odd number $d > 1$ divided $n,$ so that $2^d - 1$ divides $m^2 + 9$ and so $m^2 \equiv -9 \pmod{2^d - 1}.$ Since $d$ is odd, we have that $2^d - 1$ is not divisible by $3,$ and so we can further reduce this to $m^2 \equiv -1 \pmod{2^d - 1},$ i.e. $2^d - 1$ divides $m^2 + 1.$ We know by orders that $m^2 + 1$ only has prime divisors equivalent to $1 \pmod{4},$ so all divisors of $m^2 + 1$ are equivalent to $1 \pmod{4}.$ But $2^d - 1 \equiv 3 \pmod{4}$ for $d > 1,$ yielding a contradiction.

Sufficiency: Let $n = 2^k.$ We will construct such a number $m$ inductively, with the base case $k = 1$ holding with $m = 0.$ Now assume that we have a number $m$ such that $m^2 \equiv -9 \pmod{2^{2^k} -1}.$ Since $2^{2^{k+1}} - 1 = (2^{2^k} - 1)(2^{2^k} + 1)$ and $\gcd(2^{2^k} - 1, 2^{2^k} + 1) = 1,$ we just need to find a number $m$ such that $m^2 \equiv -9 \pmod{2^{2^k} + 1}$ , from which we are done by the Chinese Remainder Theorem. Clearly $2^{2^k} + 1$ is not divisible by $3,$ so we can reduce this to $m^2 \equiv -1 \pmod{2^{2^k} + 1}.$

Factor $2^{2^k} + 1 = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ where the $p_i$ are primes and $e_i \in \mathbb{N}_0$ such that $p_i \equiv 1 \pmod{4}$ for all $i.$ By the Chinese Remainder Theorem, it suffices to show that $m^2 \equiv -1$ has a solution modulo $p_i^{e_i}$ for all $i.$ Notice that $p_i^{e_i}$ has a primitive root, and $\phi(p_i^{e_i}) = (p_i - 1)p_i^{e_i - 1}$ is divisible by $4,$ which readily implies that $-1$ is a quadratic residue. Combining all these congruences gives us our desired $m.$

Therefore, the only $n$ such that $2^n - 1$ has a multiple of the form $m^2 + 9$ are powers of two, which we have confirmed to work.

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

#68 h Jan 7, 2025, 8:29 PM • 1 Y

Y by cubres

Suppose that $k\mid n$ for some odd $k>2$ . If $m^2\equiv-9\pmod{2^n-1}$ for some $m$ , then $m^2\equiv-9\pmod{2^k-1}$ . Since $2^k\equiv2\pmod3$ , we have $(\frac{m}3)^2\equiv-1\pmod{2^k-1}$ . Since $2^k-1\equiv3\pmod4$ , it follows that $-1$ is a quadratic residue modulo $p$ for some prime divisor $p$ such that $p\equiv3\pmod4$ , a contradiction. Hence, if $n$ is not a power of $2$ , then $2^n-1$ has no multiple of the form $m^2+9$ .

Suppose that $-9$ is a quadratic residue modulo $2^{2^r}-1$ for some nonnegative integer $r$ . note that $(3\cdot 2^{2^{r-1}})^2\equiv-9\pmod{2^{2^r}+1}$ . Then $-9$ is a quadratic residue modulo $(2^{2^r}-1)(2^{2^r}+1)=2^{2^{r+1}}-1$ . By induction, it follows that $-9$ is a quadratic residue modulo $2^{2^r}-1$ for all $r$ , so that $2^{2^r}-1$ has a multiple of the form $m^2+9$ .

We thus conclude that the solution set for $n$ is given by $\boxed{\{2^r\mid r\in\mathbb{Z},r\ge0\}}.$ $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

cursed_tangent1434

595 posts

cursed_tangent1434

#69 h Apr 8, 2025, 3:50 PM • 1 Y

Y by cubres

Mid problem, but I think it's quite instructive. Doesn't help if you misread and spend a non-trivial amount of time trying to solve the problem with 'divisor' instead of 'multiple'.

We claim that the answer is all positive integers $n$ of the form $n=2^k$ for some non-negative integer $k$ . When $n=1$ the result is clear so we deal with $n>1$ in what follows. First we shall show that all the claimed solutions indeed work.

Clearly $3 \mid 2^{2^k}-1$ and in particular, Lifting the Exponent Lemma tells us that $\nu_3(2^{2^{k}}-1)=\nu_3(3)+\nu_3(2^{k-1})=1$ . Thus, we can write
$2^n-1=3 \cdot p_1^{a_1}\cdot p_2^{a_2}\cdots p_r^{a^r}$ for distinct odd primes $p_1, p_2, \cdots , p_r$ . We first claim the following.

Claim : All primes $p_1,p_2,\dots , p_r$ are $1 \pmod{4}$ .

Proof : Simply note that since
$2^{2^k}-1=(2-1)(2+1)(2^2+1)\dots (2^{2^{k-1}}+1)$ Since each index of $2$ beyond the second factor is even, none of these factors are divisible by 3. Further, if $p \equiv 3 \pmod{4}$ (and $p>3$ ) divides one of these terms, then $p \mid 2^{2^i}+1$ for some $i \ge 1$ . However, this is a clear contradiction by Fermat's Christmas Theorem implying that the left-hand expression has no $3 \pmod{4}$ primes factors as claimed.

We let $3 \mid m$ . Further, for each prime $p_i \mid 2^{2^k}-1$ we have,
$(-9)^{\frac{p_i-1}{2}} \equiv (-1)^{\frac{p_i-1}{2}}\cdot 9^{\frac{p_i-1}{2}} \equiv (-1)^{\frac{p_i-1}{2}} \equiv 1 \pmod{p_i}$ since $4 \mid p_i-1$ as noted above. Thus, $-9$ is a QR $\pmod{p_i}$ . Thus, for each prime $p_i$ there exists some positive integer $x_i$ for which $p_i \mid x_i^2+9$ . We now resort to induction.

Say there exists a positive integer $x_{im}$ such that $p^m \mid x_{im}^2+9$ for some $m \ge 1$ . We note that,
$(x_{im}+kp^m)^2+9$ is injective $\pmod{p^{m+1}}$ and in the set $\{0,p^m,2\cdot p^m,\dots (p-1)\cdot p^m\}$ as $k$ ranges from $0$ to $p-1$ . Thus, one of these values for $k$ gives a new positive integer $x_{i(m+1)}=x_{im}+kp^m$ such that $p^{m+1}\mid x_{i(m+1)}^2+9$ .

Now, applying the inductive described above to $p_i$ , we conclude that there must exist some positive integer $y_i$ such that $p_i^{a_i} \mid y_i^2 +9$ for all $1 \le i \le r$ . We apply CRT on $3 , p_1,p_2,\dots , p_r$ to construct a suitable value for $m$ and finish.

To see why no other $n$ work, say $p \mid n$ and $2<p<n$ . Thus,
$2^p-1\mid 2^n-1 \mid m^2+9$ Since $p>2$ the left-hand side is $3 \pmod{4}$ and thus, some prime factor of $2^p-1$ , $q \ne 9 \equiv 3 \pmod{4}$ exists. However, by Fermat's Christmas Theorem this is a clear contradiction as we must have $q \mid 9$ .

Z K Y

The post below has been deleted. Click to close.

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

AshAuktober

993 posts

AshAuktober

#70 h Apr 10, 2025, 12:18 PM • 1 Y

Y by cubres

Odd $n$ don't work so $n$ must be a power of 2. Such $n$ can be shown to work using CRT combined with LTE to show $\nu_3$ can't be too large.

Also why is misreading this so real lmfao.

This post has been edited 1 time. Last edited by AshAuktober, Apr 10, 2025, 12:18 PM

Z K Y

The post below has been deleted. Click to close.

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

ATM_

17 posts

ATM_

#71 h Apr 13, 2025, 9:49 AM • 1 Y

Y by cubres

Suppose $n$ has an odd prime divisor d , such that : $d>1$
We have : $2^d-1|2^n-1$
Hence : $2^d-1|a^2+9$
$d>1\implies 2^d-1>1$ , thus: $2^d-1$ has an odd prime divisor p
By Fermat Christmas theorem: $p \equiv 1[4]$
Hence : $p|a^2+9\implies a^2\iff -9[p]$
Using quadratic recopricity : $\left(\dfrac{-9}{p}\right)=\left(\dfrac{-1}{p}\right).\left(\dfrac{3}{p}\right)^2=-1.\left(\dfrac{3}{p}\right)^2$
Because : $p\iff 3[4]$

If: $p\neq 3$ , then: $\left(\dfrac{3}{p}\right)=\pm 1\implies \left(\dfrac{3}{p}\right)^2=1$
So :b $\left(\dfrac{-9}{p}\right)=-1$ (not a quadratic residu mod p)
Absurde , Hence: $p=3$

So: $3|2^d-1\implies 2^d\equiv 1[3]$
Hence : $o_p(2)|d\implies 2|d$
Absurde ,cause d is odd
Thus n has no odd divisors
Which means $n$ is a power of 2
Let : $n=2^k/k\in \mathbb{N}$

Proof by induction:
For $n=1,2^n-1=1|a^2+9$
True
Suppose : $\exists a\in \mathbb{N}:a^2\equiv -9[2^{2^{k}}-1]$

We habe : $2^{2^{k+1}}-1=(2^k-1)(2^k+1)$
For some positive integer $a_1=3×2^{2^{k-1}},with :k\in \mathbb{N}*$
We have : $a_1^2+9=9×2^{2^k}+9=9(2^{2^k}+1)$
Thus : $2^{2^k}+1|a_1^2+9$
And : $a^2\equiv -9[2^{2^k}-1]$
Because : $pgcd(2^{2^k}-1,2^{2^k}+1)=gcd(2^{2^k}+1,2)=1$
By CRT: $\exists b\in \mathbb{N}:b\equiv a_1[2^{2^k}+1]$ and $b\equiv a[2^{2^k}-1]$
$\implies b^2\equiv a^2\equiv -9[2^{2^k}-1]$ et $b^2\equiv a_1^2\equiv -9[2^{2^k}+1]$
So : $\exists b\in \mathbb{N}:b^2\equiv -9[2^{2^{k+1}}-1]$

Hence : $\exists a\in \mathbb{N}:2^n-1|a^2+9$ iff $n$ is a power of 2

Z K Y