IMO 2019/P4
Posted: Thu Jul 18, 2019 11:05 pm
Find all pairs $(k,n)$ of positive integers such that $k!=(2^n-1)(2^n-2)\cdots(2^n-2^{n-1})$
Proposed by Gabriel Chicas Reyes, El Salvador
Proposed by Gabriel Chicas Reyes, El Salvador
We will show that $(1,1)$ and $(3,2)$ are the only possible pairs.
Claim1: $\lfloor\frac{k}{3}\rfloor =\lfloor\frac{n}{2}\rfloor$
Proof: $k!=(2^n-1)(2^n-2)(2^n-4)......(2^n-2^{n-1})$
$ =2^{\frac{n(n-1)}{2}}(2^n-1)(2^{n-1}-1)(2^{n-2}-1)....(2-1)$ ...............(1)
As $2$ is a primitive root modulo $3^2$, we can say $2$ is a primitive root modulo $3^r$ for all positive integer $r$.
So,for any positive integer $r$, $2.3^{r-1}$ is the smallest positive integer such that $2^{2.3^{r-1}} \equiv 1 ($mod $3.3^{r-1})$
Now, we will use induction.Assume that $\lfloor\frac{k}{3}\rfloor=\lfloor\frac{n}{2}\rfloor= m$ for some integers $k,m,n$.
If we increase $\lfloor\frac{k}{3}\rfloor$ by $1$ which is $\lfloor\frac{k}{3}\rfloor= m+1$ assume that $v_3(k!)$ increases by $m'$ which implies
$v_3(3(m+1))= m' \Rightarrow v_3(m+1)=m'-1$.
As, $2^{2.3^{m'-1}}\equiv 1($mod $3^{m'}$)$\Rightarrow 2^{2.(m+1)}\equiv 1 ($mod $3^{m'})$ we can say $\lfloor\frac{n}{2}\rfloor = m+1$
Initially, for $k=3$, $n$ must be $2$ otherwise both sides in $(1)$ will not be the same.Here, $\lfloor\frac{3}{3}\rfloor = \lfloor\frac{2}{2}\rfloor$
Thus, $\lfloor\frac{k}{3}\rfloor = \lfloor\frac{n}{2}\rfloor$.
Claim2: $n\leq 4$
Proof: $v_2(k!)<k$.
So, $v_2(k!)= \frac{n(n-1)}{2} \Rightarrow$ $\frac{n(n-1)}{2}<k \Rightarrow \frac{2t(2t-1)}{2}< 3t+2$ [let $\lfloor\frac{k}{3}\rfloor=\lfloor\frac{n}{2}\rfloor = t$]
$\Rightarrow t^2<2t+1 \Rightarrow t\leq 2 \Rightarrow n\leq 4$.
Now, by checking for $n\leq 4$ we can easily get that $(1,1)$ and $(3,2)$ are the only solutions.
(Q.E.D.)
Claim1: $\lfloor\frac{k}{3}\rfloor =\lfloor\frac{n}{2}\rfloor$
Proof: $k!=(2^n-1)(2^n-2)(2^n-4)......(2^n-2^{n-1})$
$ =2^{\frac{n(n-1)}{2}}(2^n-1)(2^{n-1}-1)(2^{n-2}-1)....(2-1)$ ...............(1)
As $2$ is a primitive root modulo $3^2$, we can say $2$ is a primitive root modulo $3^r$ for all positive integer $r$.
So,for any positive integer $r$, $2.3^{r-1}$ is the smallest positive integer such that $2^{2.3^{r-1}} \equiv 1 ($mod $3.3^{r-1})$
Now, we will use induction.Assume that $\lfloor\frac{k}{3}\rfloor=\lfloor\frac{n}{2}\rfloor= m$ for some integers $k,m,n$.
If we increase $\lfloor\frac{k}{3}\rfloor$ by $1$ which is $\lfloor\frac{k}{3}\rfloor= m+1$ assume that $v_3(k!)$ increases by $m'$ which implies
$v_3(3(m+1))= m' \Rightarrow v_3(m+1)=m'-1$.
As, $2^{2.3^{m'-1}}\equiv 1($mod $3^{m'}$)$\Rightarrow 2^{2.(m+1)}\equiv 1 ($mod $3^{m'})$ we can say $\lfloor\frac{n}{2}\rfloor = m+1$
Initially, for $k=3$, $n$ must be $2$ otherwise both sides in $(1)$ will not be the same.Here, $\lfloor\frac{3}{3}\rfloor = \lfloor\frac{2}{2}\rfloor$
Thus, $\lfloor\frac{k}{3}\rfloor = \lfloor\frac{n}{2}\rfloor$.
Claim2: $n\leq 4$
Proof: $v_2(k!)<k$.
So, $v_2(k!)= \frac{n(n-1)}{2} \Rightarrow$ $\frac{n(n-1)}{2}<k \Rightarrow \frac{2t(2t-1)}{2}< 3t+2$ [let $\lfloor\frac{k}{3}\rfloor=\lfloor\frac{n}{2}\rfloor = t$]
$\Rightarrow t^2<2t+1 \Rightarrow t\leq 2 \Rightarrow n\leq 4$.
Now, by checking for $n\leq 4$ we can easily get that $(1,1)$ and $(3,2)$ are the only solutions.
(Q.E.D.)