Find all pairs $(k, n)$ of positive integers such that
$$k! = (2^n − 1)(2^n − 2)(2^n − 4) · · · (2^n − 2^{n−1})$$
I tried to solve this problem but only found one solution $(1,1)$. Please help me to solve this problem.
[Math] Find all pairs $(k, n)$ of positive integers such that $k! = (2^n − 1)(2^n − 2)(2^n − 4) · · · (2^n − 2^{n−1})$
contest-mathdiophantine equationselementary-number-theoryfactorial
Related Solutions
Here is a hands on method of getting the primes you need quite quickly.
Note that $a^{25}-a=a(a^{24}-1)=a(a^{12}+1)(a^6+1)(a^3+1)(a^3-1)$ and $a^{12}+1=(a^4+1)(a^8-a^4+1)$ by successive factorisations using the difference of two squares, so you can obtain a full factorisation for small $a$.
For $a=2$ you get $2^{25}-2=2\cdot17\cdot241\cdot65\cdot9\cdot7$ and the factorisation is easy to complete.
Do a similar thing for $a=3$ to get $3\cdot82\cdot6481\cdot330\cdot 28\cdot 26$
You can then reduce the numbers you have to test to common factors these two, which will be factors of $2\cdot 3\cdot 5\cdot 7\cdot 13$ since no other primes are common.
To prove this works for all factors you need to prove that each of the primes $2,3,5,7,13$ will always divide $a^{25}-a$, and what you need is that $p|a^p-a$ for all primes $p$ and all integers $a$ which is a modest extension of the usual statement of Fermat's little theorem. Use that with the five identified primes.
if $2^a+5^b=w^2$, then $2^a \equiv w^2 \pmod 5$. This implies that $2\mid a$. So let $c\in\Bbb{N}\space|\space 2c=a$. $$2^{2c}+5^b=w^2$$ $$5^b=w^2-2^{2c}$$ $$5^b=(w-2^c)(w+2^c)$$ both $w-2^c$ and $w+2^c$ are both powers of $5$ so $\exists \space s,t\in\Bbb{N}\space|\space b=s+t, s>t,\space 5^s=w+2^c,5^t=w-2^c$ $$5^s=w+2^c\space\space\space(1)$$ $$5^t=w-2^c\space\space\space(2)$$ subtracting $(2)$ from $(1)$ we get $$5^s-5^t=2^{c+1}\space\space\space(3)$$ $$5^t(5^{s-t}-1)=2^{c+1}\space\space\space(4)$$ $5\nmid 2^{c+1}$ so $t=0$ and $s=b$. Therefore $$5^b-1=2^{c+1}\space\space\space(5)$$ $$5^b-5+2^2=2^{c+1}\space\space\space(6)$$ $$5^b-5=2^{c+1}-2^2\space\space\space(7)$$ $$5(5^{b-1}-1)=2^2(2^{c-1}-1)\space\space\space(8)$$ $5\mid $lhs of (8) $\Rightarrow$ $5\mid $rhs of (8). $5\nmid 2^2$ so $5 \mid 2^{c-1}-1 \Rightarrow 4 \mid c-1$
lhs of (8) $\equiv 0,20,27\pmod {31}$ and rhs of (8) $\equiv 0,4,12,28,29\pmod {31}$
The only way for the equation to be equal is if both sides are divisible by 31.
$31\nmid 2^2$ therefore $31\mid 2^{c-1}-1 \Rightarrow 5 \mid c-1$
Combining both of the facts that $4 \mid c-1$ and $5 \mid c-1\Rightarrow 20\mid c-1\Rightarrow 25 \mid 2^{c-1}-1\Rightarrow 25\mid $rhs of (8)$\Rightarrow 25\mid $lhs of (8) $\Rightarrow 5\mid 5^{b-1}-1\Rightarrow b=1$
plugging in $1$ for $b$ in $(5)$ implies that $c=1\Rightarrow a=2$
the first solution is $a=2$, $b=1$, $w^2=9$
Edit: In the beginning of the proof I assumed that $2^a\equiv w^2 \pmod 5$. This is true iff $b\neq 0$.
If $b=0$ then $2^a+1=w^2$ $$2^a+1=w^2$$ $$2^a=w^2-1$$ $$2^a=(w-1)(w+1)$$ both $w-1$ and $w+1$ are both powers of $2$ so $\exists \space u,v\in\Bbb{N}\space|\space a=u+v, u>v,\space 2^u=w+1,2^v=w-1$ $$2^u=w+1\quad(9)$$ $$2^v=w-1\quad(10)$$ subtracting $(10)$ from $(9)$ we get $$2^u-2^v=2\quad(11)$$ $$2^v(2^{u-v}-1)=2\quad(12)$$ This implies $v=1$ and both sides of (12) can be divided by 2 $$2^{u-1}-1=1\quad(13)$$ $$2^{u-1}=2\quad(14)$$ $$u-1=1\quad(15)$$ $$u=2\quad(16)$$ This gives the second solution $a=3$, $b=0$, $w^2=9$
Edit 2: too long for comment, answering Prathmesh's question from the comment below
After getting to equation to $(8)$ I knew that if I could show that $5 \mid 5^{b-1}-1$ then there would only be one solution to that portion of the problem. Working backwards $25 \mid 2^{c-1}-1$. powers of $2$ have a cycle of $20 \pmod{25}$. So $25 \mid 2^{c-1}-1$ iff $20 \mid c-1$. I already had $4 \mid c-1$ from the fact that both sides of $(8)$ are divisible by $5$. So I needed a mod that produces cycle that is a multiple of $5$ in powers of $2$. In general if a mod will produce a cycle $x$ if the mod is divisible by a sufficiently large power of of $x$ or is divisible by a prime factor that is of the form $xk+1$. So the mod in this case needs to have a sufficiently large power of of $5$ or has a prime factor of the form $5k+1$. Since I am trying to prove that the rhs is divisable by $25$ I can't use powers of $5$ so I am left with numbers that have a prime factor of the form $5k+1$. All primes except $2$ are odd so I can just look at numbers of the form $10k+1$. So I first tried $11$ but both sides can be $\equiv 1,3,4,5,9\pmod{11}$. $21$ has a prime factorization of $3$ and $7$ neither of which is of the form $10k+1$. so then I tried $31$.
Best Answer
Find the exponent of the largest power of 2 that divides both sides. In RHS it is $0 + 1 + \ldots + (n-1) = \frac{(n-1)n}{2}$. In LHS it can be found with Legendre's formula, which gives $\sum_{i=1}^{\infty} \lfloor \frac{k}{2^i} \rfloor$. Since $\sum_{i=1}^{\infty} \lfloor \frac{k}{2^i} \rfloor < \sum_{i=1}^{\infty} \frac{k}{2^i} = k$ (the inequality is strict because at least one term in the bracket is not an integer), we have $k > \frac{(n-1)n}{2}$, or $k \ge \frac{(n-1)n}{2}+1$.
Since $RHS < 2^{n^2}$, and factorial grows faster than any exponential function, for large values of $n$, LHS will be larger than RHS. We need to find out an upper bound for $n$.
When $n \ge 6$, $$k! \ge (\frac{(n-1)n}{2}+1)! \ge 7! \cdot 8^{\frac{(n-1)n}{2}-6} > 2^{12} \cdot 2^{\frac{3}{2}n^2 - \frac{3}{2}n - 18} = 2^{n^2} \cdot 2^{\frac{1}{2}n^2 - \frac{3}{2}n - 6}$$
And $\frac{1}{2}n^2 - \frac{3}{2}n - 6 > 0$, so LHS > RHS. Therefore there are no solutions with $n \ge 6$. Manually checking the remaining cases gives the only solutions $(1, 1)$ and $(3, 2)$.