Find all pairs of integers $(m,n)$ such that $m^6 = n^{n+1} + n -1$.
Problem
Source: Turkey TST 2013 - Day 2 - P1
Tags: algebra, polynomial, number theory, greatest common divisor, modular arithmetic, number theory proposed, nice problem
02.04.2013 19:54
if n=4k, then m^6=4s+3,impossible. suppose n=4k+1,now write the equation as m^6+1=n(n^n+1).now n^n+1 is congruent to 2 mod 4.but any a^2+1 has factors of the form 2 or 4k+1.so n^n+1=2 or n=1. n=4k+3,then m^6 is congruent to 3 mod 4,impossible. n=4k+2,then m^6+1=n(n^n+1),implies n=2,which is clearly impossible
03.04.2013 18:10
Could you explain how? You state that $n^n+1 \cong 2(mod$ $4)$ and that $a^2 +1$ has no factor of the form $4k+3$. So what? Where is the contradicttion? And in the case $n=4k+2$, you just say that $n=2$ which isn't very obvious to me??
04.04.2013 05:56
in the case, n=4k+1, n^n+1 is a factor of m^6+1.but n^n+1 is of the form 4k+2.hence n^n+1=2 when,n=4k+2,n is a factor of n^n+1 which forces us to conclude n=2
04.04.2013 08:18
In case $n=4k+1$, $n^n + 1$ is a factor of $m^6 +1$.But $n^n +1$ is not a prime because $n+1|n^n +1$. So you cannot conclude that $n^n +1=2$. It is only equivalent to say that $v_2(m^6+1)=1$. In the case $n=4k+2$, why would $n|n^n +1$? Maybe I am missing obvious things but read your proof properly. If you use some other lemmas, properties etc., state them clearly but otherwise, i am afraid that your proof is wrong. Didn't any of the people from AoPS at the Turkey TST solve this?? I cannot get a correct proof but i would really like it if someone posted a proof.
04.04.2013 13:47
If $n>1$ is odd then $\left(n^{\frac{n+1}{2}}\right)^2<n^{n+1}+n-1<\left(n^{\frac{n+1}{2}}+1\right)^2$, hence it can't be perfect square.
04.04.2013 19:19
First, just like dr_Civot did, notice that $n$ can't be odd and can't be $\equiv -1\, mod \, 3$. (otherwise it will be between two consecutive squares or cubes). Also, using that $n$ is even, we conclude that we can't have $n\equiv 0\, mod\, 3$ (otherwise we get $m^6\equiv -1 \,mod\,3$). So $n\equiv\, 4 mod\, 6$. Consider the polinomial $x^{n+1}+x-1$. As $n\equiv \,4 mod \,6$ we get $x^2-x+1|x^{n+1}+x-1$. It's easy to do this polynomial division by hand. We get: $x^{n+1}+x-1=(x^2-x+1)(x^{n-1}+x^{n-2}-x^{n-4}-x^{n-5}+x^{n-7}+x^{n-8}-x^{n-10}-x^{n-11}...-x^6-x^5+x^3+x^2-1)$ (the pattern is a periodic $(1,1,0,-1,-1,0)$ and a $(1,1,0,-1)$ in the end) Now, it is a boring, but not hard calculation to get that for x=n, $gcd(n^2-n+1,n^{n-1}+n^{n-2}-...+n^3+n^2-1)=1$. (actually, after the usual calculation, we get that this $gcd$ divides $3$, but it can't be $3$, because $n^2-n+1 \equiv 1 mod 3$). So $n^2- n+1$ is a square, a contradiction. (because $(n-1)^2<n^2-n+1<n^2$).
06.04.2013 00:52
There is also another proof using the fact $n+1 | n^{n+1}+n+2=y^6+3$ if $n \equiv 4 \pmod 6$. In this case since $n+1 \equiv 5 \pmod 6$ it must have a prime divisor equivalent to $2$ modulo $3$ which is impossible since $-3$ is not a square residue modulo such a prime.
30.04.2013 13:47
crazyfehmy wrote: There is also another proof using the fact $n+1 | n^{n+1}+n+2=y^6+3$ if $n \equiv 4 \pmod 6$. In this case since $n+1 \equiv 5 \pmod 6$ it must have a prime divisor equivalent to $2$ modulo $3$ which is impossible since $-3$ is not a square residue modulo such a prime. excuse me please, but can you explain this step, thank you:) In this case since $n+1 \equiv 5 \pmod 6$ it must have a prime divisor equivalent to $2$ modulo $3$ which is impossible since $-3$ is not a square residue modulo such a prime.[/quote]
30.04.2013 14:11
Const41 wrote: crazyfehmy wrote: There is also another proof using the fact $n+1 | n^{n+1}+n+2=y^6+3$ if $n \equiv 4 \pmod 6$. In this case since $n+1 \equiv 5 \pmod 6$ it must have a prime divisor equivalent to $2$ modulo $3$ which is impossible since $-3$ is not a square residue modulo such a prime. excuse me please, but can you explain this step, thank you:) In this case since $n+1 \equiv 5 \pmod 6$ it must have a prime divisor equivalent to $2$ modulo $3$ which is impossible since $-3$ is not a square residue modulo such a prime. $y^6$ is a perfect square and $y^6 \equiv -3 \pmod {n+1}$. Now we claim that there exists a prime divisor $p$ of $n+1$ satisfying $p \equiv 2 \pmod 3.$ This is true since if all prime divisors of $n+1$ (which are necessarily greater than $3$) are of the form $3k+1$ then $n+1$ must also be of that form which is a contradiction. Now let $p$ be a prime divisor of $n+1$ of the form $3k+2.$ Then we again get a contradiction because $-3$ is a square residue modulo $p$, but this is impossible since $p \equiv 2 \pmod 3.$ If you do not know the proof of the last statement, I can give you hint. Let $x^2 \equiv -3 \pmod p$ where $p \equiv 2 \pmod 3$ and $p>2$. Then choose an integer $y$ such that $2y+1 \equiv x \pmod p$. (Such a $y$ exists.) Then the condition gives us that $y^2+y+1 \equiv 0 \pmod p$ which means $y^3 \equiv 1 \pmod p$. Now use Fermat's theorem to get a contradiction.
01.05.2013 13:38
crazyfehmy wrote: $y^6$ is a perfect square and $y^6 \equiv -3 \pmod {n+1}$. Now we claim that there exists a prime divisor $p$ of $n+1$ satisfying $p \equiv 2 \pmod 3.$ This is true since if all prime divisors of $n+1$ (which are necessarily greater than $3$) are of the form $3k+1$ then $n+1$ must also be of that form which is a contradiction. Now let $p$ be a prime divisor of $n+1$ of the form $3k+2.$ Then we again get a contradiction because $-3$ is a square residue modulo $p$, but this is impossible since $p \equiv 2 \pmod 3.$ If you do not know the proof of the last statement, I can give you hint. Let $x^2 \equiv -3 \pmod p$ where $p \equiv 2 \pmod 3$ and $p>2$. Then choose an integer $y$ such that $2y+1 \equiv x \pmod p$. (Such a $y$ exists.) Then the condition gives us that $y^2+y+1 \equiv 0 \pmod p$ which means $y^3 \equiv 1 \pmod p$. Now use Fermat's theorem to get a contradiction. Thank you very much!!! Now it is clear for me:)
17.05.2013 12:40
thank you, very much, CRAZYFEHMY! The best solution.
22.02.2018 18:51
A further alternative. Just as above, $n$ must be even. If, $n\equiv 0 \pmod{4}$, then, $m^6\equiv -1\pmod{8}$, a contradiction. Therefore, $n\equiv 2\pmod{4}$. In particular, $n\equiv 2,6\pmod{8}$. If, $n\equiv 6\pmod{8}$, notice that, $n$ has a prime divisor of form $4k+3$, and denoting this prime by $p$, we have, $n(n^n+1)=m^6+1\implies p\mid m^6+1$, a contradiction. Hence, we must have that, $n\equiv 2 \pmod{8}$. Now, it can also be seen that, $n\equiv 1\pmod{3}$ (otherwise, $n\equiv 2$ would squeeze $m^6$ between two cubes, while, $n\equiv 0$ would make $m^6\equiv -1\pmod{3}$). Now, observe that, $n^3 \equiv 1 \pmod{n^2+n+1}$, hence, $n^{n+1}=n^{3i+2} \equiv n^2 \pmod{n^2+n+1}$, hence, $$ n^2+n+1 \mid n^{n+1}+n+1 = m^6+2 \implies n^2+n+1 \mid m^6+2. $$Using, $n\equiv 2 \pmod{8}$, we have, $n^2+n+1 \equiv 7\pmod{8}$, hence, it either contains a prime, that is congruent to $7$ modulo $8$, or congruent to $5$ in modulo $8$ (convince yourself that this indeed is true), hence, using that prime $r$, we have, $m^6\equiv -2\pmod{r}$, a contradiction, since, $-2$ is a quadratic residue modulo $p$, if and only if, $p\equiv 1,3 \pmod{8}$. We are done,
18.04.2020 03:09
Clearly we may assume that $n\ge 5$ or something and check small cases by hand. I'll just show there aren't any solutions for $n\ge 5$. If $n$ is odd, then \[\left(n^{\frac{n+1}{2}}\right)^2<n^{n+1} + n -1<\left(n^{\frac{n+1}{2}}+1\right)^2,\]and if $n$ is $2\pmod{3}$, then \[\left(n^{\frac{n+1}{3}}\right)^3<n^{n+1} + n -1<\left(n^{\frac{n+1}{3}}+1\right)^3.\]Thus, $n\equiv 0,4\pmod{6}$. If $n\equiv 0\pmod{6}$, then \[n^{n+1}+n-1\equiv 2\pmod{3},\]which is not a square, so we must have $n\equiv 4\pmod{6}$, so let $n=6k-2$. We now notice that \[x^{n+1}+x-1 = (x^2-x+1)\left(x^3+x^2-1+\sum_{\ell=1}^{k-1}(x^{6\ell+3}+x^{6\ell+2}-x^{6\ell}-x^{6\ell-1})\right).\]Working modulo $x^2-x+1$, we have \begin{align*} &x^3+x^2-1+\sum_{\ell=1}^{k-1}(x^{6\ell+3}+x^{6\ell+2}-x^{6\ell}-x^{6\ell-1}) \\ &= x-3 + \sum_{\ell=1}^{k-1}(x^{3}+x^{2}-1-x^{5}) \\ &= k(x-3), \end{align*}so \[\gcd\left(n^3+n^2-1+\sum_{\ell=1}^{k-1}(n^{6\ell+3}+n^{6\ell+2}-n^{6\ell}-n^{6\ell-1}),n^2-n+1\right)=\gcd(k(n-3),n^2-n+1).\]It is not hard to see that this is $1$, so we must have that $n^2-n+1$ is itself a sixth power. In fact, it cannot even be a square as if it was $a^2$, then \[(2n-1)^2-(2a)^2=5,\]which isn't possible for $n\ge 5$, as desired. This completes the proof.
04.05.2020 23:26
Ignore...
24.08.2021 09:39
We claim that $(m,n)=(1,1),(-1,1)$ is the only solution to this problem. For the sake of contradiction,assume that $m,n>1$ If, $n\equiv 0 \pmod{4}$, then, $m^6\equiv -1\pmod{8}$, a contradiction. Therefore, $n\equiv 2\pmod{4}$. Now since $m^6=(m^3)^2$,$m^6 \equiv 1+2-1 \equiv -1 \pmod 3$ if $n \equiv 2 \pmod 3$ which is a contradiction since $-1$ isn't a quadratic residue $\pmod 3$ The same argument destroys $n \equiv 0 \pmod 3$ from the front so $n \equiv 1 \pmod 3$ Now choose $P|n^{n+1}+n-1$ which is $P \equiv 2 \pmod 3$ and taking mods gives $m^6 \equiv -3 \pmod p$ which is a contradiction since $-3$ isn't a quadratic residue $\pmod p$.
25.12.2021 00:13
$$m^6 = n^{n+1} + n -1$$1.If $n$ is odd. $$n=2k-1$$$$m^3+(2k-1)^k|2k-2$$the rest is easy. 2.$n$ is evan. $$m^6+1= n^{n+1} + n $$$$m^6+3 = n^{n+1} + n+2 $$$$n+1|n^{n+1} + n+2$$$$n+1|m^6+3$$$n + 1$ has no 2mod3 prime divisor. if $3|n+1$ The rest of $A^3-B^3$ is easy. if $3|n$ by mod3,ctcontradiction
26.12.2021 12:28
Romania TST
14.04.2023 01:42
$\gcd(n+1, 6)$ due to perfect power bounding reasons. Lemma. For any $3k+2$ prime $p$, the congruence $x^2 \equiv -3 \pmod p$ has no solutions. Proof. Well-known by properties of $3k+2$ primes. Let $k = n+1$. If $k \equiv 1 \pmod 3$, then $m^6 \equiv -1 \pmod 3$, which is impossible. Thus $k \equiv 2 \pmod 3$, and pick a $2 \bmod 3$ prime $p$ dividing $k$. Taking mod $p$, $m^6 \equiv -3 \pmod p$, but this is a contradiction by the Lemma. Thus only $(1, 1)$ works.