Maths Olympiad Prep

Library / /5 of 55

, 2019

Number theory Difficulty 7.9 National olympiad, round 2 Prove it IMO

Find all pairs (m,n)(m, n) of positive integers satisfying the equation
(2n1)(2n2)(2n4)(2n2n1)=m! \left(2^{n}-1\right)\left(2^{n}-2\right)\left(2^{n}-4\right) \cdots\left(2^{n}-2^{n-1}\right)=m!

Solutions — 2

Solution 1

We will get an upper bound on nn from the speed at which v2(Ln)v_{2}\left(L_{n}\right) grows.
From
Ln=(2n1)(2n2)(2n2n1)=21+2++(n1)(2n1)(2n11)(211) L_{n}=\left(2^{n}-1\right)\left(2^{n}-2\right) \cdots\left(2^{n}-2^{n-1}\right)=2^{1+2+\cdots+(n-1)}\left(2^{n}-1\right)\left(2^{n-1}-1\right) \cdots\left(2^{1}-1\right)
we read
v2(Ln)=1+2++(n1)=n(n1)2. v_{2}\left(L_{n}\right)=1+2+\cdots+(n-1)=\frac{n(n-1)}{2} .
On the other hand, v2(m!)v_{2}(m!) is expressed by the Legendre formula as
v2(m!)=i=1m2i v_{2}(m!)=\sum_{i=1}^{\infty}\left\lfloor\frac{m}{2^{i}}\right\rfloor
As usual, by omitting the floor functions,
v2(m!)<i=1m2i=m. v_{2}(m!)<\sum_{i=1}^{\infty} \frac{m}{2^{i}}=m .
Thus, Ln=m!L_{n}=m! implies the inequality
n(n1)2<m. \begin{equation*} \frac{n(n-1)}{2}<m . \tag{2} \end{equation*}
In order to obtain an opposite estimate, observe that
Ln=(2n1)(2n2)(2n2n1)<(2n)n=2n2. L_{n}=\left(2^{n}-1\right)\left(2^{n}-2\right) \cdots\left(2^{n}-2^{n-1}\right)<\left(2^{n}\right)^{n}=2^{n^{2}} .
We claim that
2n2<(n(n1)2)! for n6. \begin{equation*} 2^{n^{2}}<\left(\frac{n(n-1)}{2}\right)!\text{ for } n \geqslant 6 . \tag{3} \end{equation*}
For n=6n=6 the estimate (3) is true because 262<6.910102^{6^{2}}<6.9 \cdot 10^{10} and (n(n1)2)!=15!>1.31012\left(\frac{n(n-1)}{2}\right)!=15!>1.3 \cdot 10^{12}.
For n7n \geqslant 7 we prove (3) by the following inequalities:
(n(n1)2)!=15!1617n(n1)2>23616n(n1)215=22n(n1)24=2n22n(n2)24>2n2. \begin{aligned} \left(\frac{n(n-1)}{2}\right)! & =15!\cdot 16 \cdot 17 \cdots \frac{n(n-1)}{2}>2^{36} \cdot 16^{\frac{n(n-1)}{2}-15} \\ & =2^{2 n(n-1)-24}=2^{n^{2}} \cdot 2^{n(n-2)-24}>2^{n^{2}} . \end{aligned}
Putting together (2) and (3), for n6n \geqslant 6 we get a contradiction, since
Ln<2n2<(n(n1)2)!<m!=Ln L_{n}<2^{n^{2}}<\left(\frac{n(n-1)}{2}\right)!<m!=L_{n}
Hence n6n \geqslant 6 is not possible.
Checking manually the cases n5n \leqslant 5 we find
L1=1=1!,L2=6=3!,5!<L3=168<6!,7!<L4=20160<8! and 10!<L5=9999360<11!. \begin{gathered} L_{1}=1=1!, \quad L_{2}=6=3!, \quad 5!<L_{3}=168<6!, \\ 7!<L_{4}=20160<8!\quad \text{ and } \quad 10!<L_{5}=9999360<11!. \end{gathered}
So, there are two solutions:
(m,n){(1,1),(3,2)}. (m, n) \in\{(1,1),(3,2)\} .

Solution 2

Like in the previous solution, the cases n=1,2,3,4n=1,2,3,4 are checked manually. We will exclude n5n \geqslant 5 by considering the exponents of 3 and 31 in (1).
For odd primes pp and distinct integers a,ba, b, coprime to pp, with pabp \mid a-b, the Lifting The Exponent lemma asserts that
vp(akbk)=vp(ab)+vp(k). v_{p}\left(a^{k}-b^{k}\right)=v_{p}(a-b)+v_{p}(k) \text{.}
Notice that 3 divides 2k12^{k}-1 if only if kk is even; moreover, by the Lifting The Exponent lemma we have
v3(22k1)=v3(4k1)=1+v3(k)=v3(3k) v_{3}\left(2^{2 k}-1\right)=v_{3}\left(4^{k}-1\right)=1+v_{3}(k)=v_{3}(3 k)
Hence,
v3(Ln)=2knv3(4k1)=kn2v3(3k). v_{3}\left(L_{n}\right)=\sum_{2 k \leqslant n} v_{3}\left(4^{k}-1\right)=\sum_{k \leqslant\left\lfloor\frac{n}{2}\right\rfloor} v_{3}(3 k) .
Notice that the last expression is precisely the exponent of 3 in the prime factorisation of (3n2)!\left(3\left\lfloor\frac{n}{2}\right\rfloor\right)!. Therefore
v3(m!)=v3(Ln)=v3((3n2)!)3n2m3n2+2 \begin{align*} v_{3}(m!)=v_{3}\left(L_{n}\right) & =v_{3}\left(\left(3\left\lfloor\frac{n}{2}\right\rfloor\right)!\right) \\ 3\left\lfloor\frac{n}{2}\right\rfloor & \leqslant m \leqslant 3\left\lfloor\frac{n}{2}\right\rfloor+2 \tag{4} \end{align*}
Suppose that n5n \geqslant 5. Note that every fifth factor in LnL_{n} is divisible by 31=25131=2^{5}-1, and hence we have v31(Ln)n5v_{31}\left(L_{n}\right) \geqslant\left\lfloor\frac{n}{5}\right\rfloor. Then
n10n5v31(Ln)=v31(m!)=k=1m31k<k=1m31k=m30 \begin{equation*} \frac{n}{10} \leqslant\left\lfloor\frac{n}{5}\right\rfloor \leqslant v_{31}\left(L_{n}\right)=v_{31}(m!)=\sum_{k=1}^{\infty}\left\lfloor\frac{m}{31^{k}}\right\rfloor<\sum_{k=1}^{\infty} \frac{m}{31^{k}}=\frac{m}{30} \tag{5} \end{equation*}
By combining (4) and (5),
3n<m3n2+2 3 n<m \leqslant \frac{3 n}{2}+2
so n<43n<\frac{4}{3} which is inconsistent with the inequality n5n \geqslant 5.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.