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
  • 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$ Commented Jun 29, 2018 at 20:11

2 Answers 2

1
+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$
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .