Let $n$ be a positive integer with the following property: $2^n-1$ divides a number of the form $m^2+81$, where $m$ is a positive integer. Find all possible $n$.
Problem
Source:
Tags: number theory, quadratic reciprocity
12.12.2016 15:52
The answer is powers of $2$. I am busy now, so I'll just write a lemma: If a prime $p$ divides a number of the form $m^2+81$, then necessarily $p=2$ or $p=3$ or $4\mid p-1$.
12.12.2016 15:54
Yes, it is just the first supplement of QR followed by the fact that a number that is $3\pmod{4}$ must have a prime divisor that is $3\pmod{4}$ ._.
12.12.2016 16:03
Almost the same as IMO Shortlist 1998 N5.
12.12.2016 16:03
rafayaashary1 wrote: Yes, it is just the first supplement of QR followed by the fact that a number that is $3\pmod{4}$ must have a prime divisor that is $3\pmod{4}$ ._. How to continue?
12.12.2016 16:53
I think it is necessary and sufficient that $n=2^k$. Necessary because if $n'\mid n\iff 2^{n'}-1\mid 2^n-1$ where $n'>2$ and $n'$ is odd, there is a prime $3\pmod{4}$ that is not $3$ dividing $2^{n'}-1$, which in turn divides $2^{n}-1$. Sufficient because we have $2^{2^{k}}-1=\left(2^{2^{k-1}}+1\right)\left(2^{2^{k-2}}+1\right)\cdots 5\cdot 3$, and it is well known that $p\mid 2^{2^{l}}+1\implies p\equiv 1\pmod{2^{l+1}}$, so by CRT we can find the proper $m$.
05.05.2017 19:11
As @v_Enhance said, it is similar to the question in IMO 39 shortlist, while the original proposal was $m^2+9$. Indeed, any odd perfect square fits the question well(for $3^{2k}$ the answer is the same, for other $p$ some calculations are needed)