6
$\begingroup$

The problem statement is

Let $a_1,a_2,\dots,a_n$ be a strictly decreasing sequence of positive integers, with $a_1\equiv5\ (\text{mod }8)$.

Prove that for all positive integers $n$, if $$a_1+a_2+\dots+a_n\le2^{n-4}\text,$$ then for all positive integers $m$, $$a_2!a_3!\dots a_n!+1\neq a_1^m\text.$$

Consider that if $n\le6$, the statement is never false, since the antecendent never holds (because $2^{n-4}\le2^{6-4}=4$ and $a_1+a_2+\dots+a_n\ge a_1\ge5$).

It remains to prove the statement for $n\ge7$.

I set out to prove it by contradiction, assuming $a_1+a_2+\dots+a_n\le2^{n-4}$ and $a_2!a_3!\dots a_n!+1=a_1^m$ for some positive integer $m$.

What I obtained:

  1. Because $a_1\equiv5\ (\text{mod }8)$, we have $a_1^m\equiv5\ (\text{mod }8)$ if $m$ is odd, and $a_1^m\equiv1\ (\text{mod }8)$ if $m$ is even.

  2. Because $n\ge7$ and the sequence is strictly decreasing, we have $a_2\ge6$ (otherwise, $a_7$ would not be positive). Therefore, $8\mid720\mid a_2!$. It follows that $a_2!a_3!\dots a_n!+1\equiv1\ (\text{mod }8)$.

  3. From (1) and (2), we obtain that $m$ is even.

  4. Consider that $(a_2!a_3!\dots a_n!,a_2!a_3!\dots a_n!+1)=1$, where $(a,b)$ denotes the greatest common divisor of $a$ and $b$. It follows that $$(a_2!a_3!\dots a_n!,a_1^m)=1\\ \implies(a_2!,a_1)=1\text;$$ in other words, $a_1$ is relatively prime to $a_2!$. It follows that the smallest prime factor (and thus any prime factor) of $a_1$ is larger than $a_2$.

But I couldn't get much further.

$\endgroup$
  • 1
    $\begingroup$ Not much help, but the sum of the n terms cannot be smaller than $n(n+1)/2$, which is always larger than $2^{n-4}$ for $n \le 10$, so it remains to prove the statement for $n \geq 11$. $\endgroup$ – Keith Backman Jun 29 '18 at 20:11
0
$\begingroup$

Just an observation, without using $a_1 \equiv 5 \pmod{8}$ ...


Let's look at the least possible cases: $$a_n=1 \Rightarrow a_n!=1$$ $$a_{n-1}>a_n \Rightarrow a_{n-1}\geq2 \Rightarrow a_{n-1}!\geq 2$$ $$a_{n-2}>a_{n-1}\geq3 \Rightarrow a_{n-2}!\geq 2^2$$ $$...$$ $$a_{2}\geq n-1 \Rightarrow a_{2}!\geq 2^{n-2}$$ Then, if we assume such an $m$ exists, then: $$(2^{n-4})^{m}>a_1^m=a_2!a_3!...a_n!+1\geq 2^{1+2+...+(n-2)}=2^{\frac{(n-2)(n-1)}{2}}$$ leading to $$(n-2)(n-1)<2m(n-4)$$ which only starts showing possible solutions for $m\geq5$.

$\endgroup$
0
+100
$\begingroup$

This is a sketch of ideas that should lead to a proof.

The basic idea is to compare the highest power of 2 that divides $a_1^m-1$ and the highest power of 2 that divides $a_2!a_3!\ldots a_n!$ and show that the first is smaller than the second.

Let $m=2^rq$. Then using the fact that $a_1 \equiv 5$ (mod 8), we get that the largest $k$ for which $2^k$ divides $a_1^m-1$ is $r+2$. To see this, write $a_1^m-1=(a_1^q-1)(a_1^q+1)(a_1^{2q}+1) \ldots$. Except the first factor, all the others are divisible by 2, but not by 4. The first one is divisible by 4 but not by 8. In particular, the value of the largest power of 2 that divides $x_1^m-1$ is at most $4m$.

Now consider $a_2!a_3!\ldots a_n!$. This is divisible by $2!3!\ldots (n-1)!$ The largest $k$ for which $2^k$ divides this is at least $\sum_{i=2}^{n-1}\lfloor i/2 \rfloor + \lfloor i/4 \rfloor + \ldots$. Show a lower bound for this.

Finally, to obtain a contradiction, show that $m$ is small, using the upper bound on the sum of the $a_i$s and also $m \leq \sum_{i=2}^{n-1} a_i \log a_i-\log n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.