Find all non-negative integers $m$ and $n$, such that $(2^n-1) \cdot (3^n-1)=m^2$.
Problem
Source: China TST 2002 Quiz
Tags: number theory unsolved, number theory
06.02.2009 17:11
Is there any idea or solution?
07.02.2009 17:06
Hint: gcd(2^n-1,3^n-1)=1 with n>1 .
07.02.2009 18:48
$ \gcd(2^4-1,3^4-1)=5$.
07.02.2009 19:14
tronghieu wrote: Hint: $ gcd(2^n-1,3^n-1)=1$ with n>1 . It is not true, for example $ (2^4-1,3^4-1)=5$. $ n=1$ is not solution. If $ n>1$ - odd, then $ 3^n-1=2\mod 8$, but $ 2^n-1$ -odd, therefore $ (2^n-1)(3^n-1)=2\mod 4$ is not square. If $ n$ even, then $ 3|2^n-1$. It give $ n=2^k3^la, (a,6)=1$ and must be $ k\ge 2$ - even, $ l\ge 1$ - odd. Therefore $ 12|n$. Consider prime factors $ (2^{12}-1)(3^{12}-1)=2^4*3^2*5^2*7^2*13^2*73$ Therefore or $ 36|n$ or $ 36\not |n, 12*73|n$,...
17.05.2009 11:48
the key of my solution is applying the theorem of Pell's equation. if $ m=0$, then $ n=0$.we claim that there is no other solutions Assume the opposite, let $ (n,m)$ be a solution and $ m$ is a positive integer. if $ n$ is odd, then $ 2\not |(2^n-1)$,$ 2|(3^n-1)$ and $ 4\not |(3^n-1)$, so $ 2|(2^n-1)(3^n-1)$ and $ 4\not |(2^n-1)(3^n-1)$.that means $ 2|m^2$ and $ 4\not |m^2$, a contradiction. So $ n$ is even Since $ (2^n-1)(3^n-1)=m^2$, we can assume that $ 2^n-1=da^2$ and $ 3^n-1=db^2$ ($ d,a,b$ are positive integers, $ d$ is square-free) Then consider the Pell's Equation $ x^2-dy^2=1$, $ (2^{\frac {n}{2}}, a)$ and $ (3^{\frac {n}{2}}, b)$ are both solutions of it. According to the theorem of Pell's equation, assume the solution of $ x^2-dy^2=1$ is $ (x_k,y_k)$, then $ x_0=1$, $ x_1=t$($ t$ is a positive integer),and $ x_{k+2}=2tx_{k+1}-x_k$ for any non-negetive integer $ k$. So we have that $ 2^{\frac {n}{2}}$ and $ 3^{\frac {n}{2}}$ are both terms in the sequence $ {x_k}$ if $ t$ is odd, then every term of $ {x_k}$ is odd, while $ 2^{\frac {n}{2}}$ is even, a contradiction. so $ t$ is even. then consider the recurrent relation we find that $ x_k$ is even iff $ k$ is odd. if $ 3|t-1$, then every term of $ {x_k}$ is congruent to $ 1$ ($ mod 3$), while $ 3^{\frac {n}{2}}$ is a multiple of $ 3$, a contradiction. if $ 3|t-2$, then $ x_k$ is congruent to $ 1$ ($ mod 3$) when $ k$ is even and $ x_k$ is congruent to $ 2$ ($ mod 3$) when $ k$ is odd.But $ 3^{\frac {n}{2}}$ is a multiple of $ 3$, a contradiction. so $ t$ is a multiple of $ 3$. then consider the recurrent relation we find that $ x_k$ is a multiple of $ 3$ iff $ k$ is odd. But for any $ x_k$, $ x_k$ is a multiple of $ 3$ iff $ k$ is odd iff $ x_k$ is even, so $ x_k$ can not be a power of 3, a contradiction,too. Q.E.D.
28.08.2009 06:08
A very good solution . Congrats
23.08.2010 16:13
Please help me.I don't understand that why we have the recurence:$x_{k+2}=2tx_{k+1}-x_k$.Thank you
01.10.2012 10:09
A good problem!
11.01.2016 06:44
I have a short solution using only modular arithmetic and lifting the exponent. Assume that $n > 0$ is a solution. First, note that $2 \mid n$, otherwise the exponent of $2$ in LHS in odd. From this (by lifting) we deduce that $n$ must be divisible by $3$ as well. Let $n=6k$. Then \[ (2^{6k}-1)(3^{6k}-1) \equiv (2^k-1)(16^k-1) \equiv (2^k-1)^2 (2^k+1)(4^k+1) \pmod{31} \]must be a quadratic residue. We claim this implies $5 \mid k$. Indeed, for $k \equiv 1,2,3,4 \pmod5$ we get $3 \cdot 5$, $5 \cdot 17$, $5 \cdot 13$, $17 \cdot 9$ are non-quadratic residues mod $31$, since of the primes here, only $5$ is a quadratic residue. So let $n = 10c$. Then we have that $\left( (2^{10})^c - 1 \right)\left( (3^{10})^c - 1 \right)$ is a perfect square. But now by lifting the exponent on the prime $11$ we get a contradiction, because $\nu_{11}(2^{10}-1) = 1$ and $\nu_{11}(3^{10}-1) = 2$, thus the exponent of $11$ in the original is $3+2\nu_{11}(c)$.
13.07.2020 23:21
linboll wrote: the key of my solution is applying the theorem of Pell's equation. if $ m=0$, then $ n=0$.we claim that there is no other solutions Assume the opposite, let $ (n,m)$ be a solution and $ m$ is a positive integer. if $ n$ is odd, then $ 2\not |(2^n-1)$,$ 2|(3^n-1)$ and $ 4\not |(3^n-1)$, so $ 2|(2^n-1)(3^n-1)$ and $ 4\not |(2^n-1)(3^n-1)$.that means $ 2|m^2$ and $ 4\not |m^2$, a contradiction. So $ n$ is even Since $ (2^n-1)(3^n-1)=m^2$, we can assume that $ 2^n-1=da^2$ and $ 3^n-1=db^2$ ($ d,a,b$ are positive integers, $ d$ is square-free) But can you assume that these guys have the same factor D? Then consider the Pell's Equation $ x^2-dy^2=1$, $ (2^{\frac {n}{2}}, a)$ and $ (3^{\frac {n}{2}}, b)$ are both solutions of it. According to the theorem of Pell's equation, assume the solution of $ x^2-dy^2=1$ is $ (x_k,y_k)$, then $ x_0=1$, $ x_1=t$($ t$ is a positive integer),and $ x_{k+2}=2tx_{k+1}-x_k$ for any non-negetive integer $ k$. So we have that $ 2^{\frac {n}{2}}$ and $ 3^{\frac {n}{2}}$ are both terms in the sequence $ {x_k}$ if $ t$ is odd, then every term of $ {x_k}$ is odd, while $ 2^{\frac {n}{2}}$ is even, a contradiction. so $ t$ is even. then consider the recurrent relation we find that $ x_k$ is even iff $ k$ is odd. if $ 3|t-1$, then every term of $ {x_k}$ is congruent to $ 1$ ($ mod 3$), while $ 3^{\frac {n}{2}}$ is a multiple of $ 3$, a contradiction. if $ 3|t-2$, then $ x_k$ is congruent to $ 1$ ($ mod 3$) when $ k$ is even and $ x_k$ is congruent to $ 2$ ($ mod 3$) when $ k$ is odd.But $ 3^{\frac {n}{2}}$ is a multiple of $ 3$, a contradiction. so $ t$ is a multiple of $ 3$. then consider the recurrent relation we find that $ x_k$ is a multiple of $ 3$ iff $ k$ is odd. But for any $ x_k$, $ x_k$ is a multiple of $ 3$ iff $ k$ is odd iff $ x_k$ is even, so $ x_k$ can not be a power of 3, a contradiction,too. Q.E.D. But can you assume that these guys have the same factor D?
15.07.2020 13:20
v_Enhance wrote: I have a short solution using only modular arithmetic and lifting the exponent. Assume that $n > 0$ is a solution. First, note that $2 \mid n$, otherwise the exponent of $2$ in LHS in odd. From this (by lifting) we deduce that $n$ must be divisible by $3$ as well. Let $n=6k$. Then \[ (2^{6k}-1)(3^{6k}-1) \equiv (2^k-1)(16^k-1) \equiv (2^k-1)^2 (2^k+1)(4^k+1) \pmod{31} \]must be a quadratic residue. We claim this implies $5 \mid k$. Indeed, for $k \equiv 1,2,3,4 \pmod5$ we get $3 \cdot 5$, $5 \cdot 17$, $5 \cdot 13$, $17 \cdot 9$ are non-quadratic residues mod $31$, since of the primes here, only $5$ is a quadratic residue. So let $n = 10c$. Then we have that $\left( (2^{10})^c - 1 \right)\left( (3^{10})^c - 1 \right)$ is a perfect square. But now by lifting the exponent on the prime $11$ we get a contradiction, because $\nu_{11}(2^{10}-1) = 1$ and $\nu_{11}(3^{10}-1) = 2$, thus the exponent of $11$ in the original is $3+2\nu_{11}(c)$. How did you get the idea to take mod11?
15.07.2020 17:53
Because 11 is 3-Wieferich, i.e. $11^2 \mid 3^{10}-1$. This fact is the key ingredient of the proof.
08.11.2020 03:01
shobber wrote: Find all non-negative integers $m$ and $n$, such that $(2^n-1) \cdot (3^n-1)=m^2$. clearly $n=1$ is not an answer. now taking $mode(3)$ gives $2|n$ so $16|3^n-1$ which gives $4|n$. rewrite as $$(2^{4k}-1)(3^{4k}-1)=(6^{2k}-1)^2-(3^{2k}-2^{2k})^2=x^2$$so $m^2+n^2=6^{2k}-1$ now taking $mode(4)$ gives that there are no solutions.
04.11.2022 01:02
Mr.C wrote: shobber wrote: so $m^2+n^2=6^{2k}-1$ now taking $mode(4)$ gives that there are no solutions. $m^2+n^2=(6^{2k}-1)^2$
04.11.2022 01:03
This problem and similar ones were solved in this paper of L. Szalay (2000): https://www.researchgate.net/profile/Laszlo-Szalay-2/publication/264956499_On_the_diophantine_equation_2_n_-13_n_-1x_2/links/588f3f7845851567c9405de3/On-the-diophantine-equation-2-n-13-n-1x-2.pdf