Problem A. 863. (November 2023)

A. 863. Let \(\displaystyle n\ge 2\) be a given integer. Find the greatest value of \(\displaystyle N\), for which the following is true: there are infinitely many ways to find \(\displaystyle N\) consecutive integers such that none of them has a divisor greater than 1 that is a perfect \(\displaystyle n^{\mathrm{th}}\) power.

Proposed by Péter Pál Pach, Budapest

(7 pont)

Deadline expired on December 11, 2023.

Answer: \(\displaystyle 2^n-1\). It is clear that among \(\displaystyle 2^n\) consecutive integers you can always find one, that is divisible by \(\displaystyle 2^n\), which is a perfect \(\displaystyle n^{th}\) power.

It is well known, that for \(\displaystyle n\ge 2\)

\(\displaystyle \sum_{k=M}^{\infty} \frac{1}{k^n}<\frac{1}{2^{n+2}}\)

is finite.

This implies that there exists \(\displaystyle M\) such that

\(\displaystyle \sum_{k=M}^{\infty} \frac{1}{k^n}<\frac{1}{2^{n+2}}.\)

Let \(\displaystyle T=\prod_{k=1}^{M-1} k^n\). We claim that there exists infinitely many values of positive integer \(\displaystyle m\) such that none of consecutive integers \(\displaystyle \{mT+1,mT+2,...,mT+2^n-1\}\) is divisible by a perfect \(\displaystyle n^{th}\) power.

To prove this, let's choose a very large number \(\displaystyle K\). For any \(\displaystyle r\in \{1,2,...,2^n-1\}\) let \(\displaystyle X_r\) denote the number of those integers among \(\displaystyle \{T+r,2T+r,...,KT+r\}\) which is divisible by a perfect \(\displaystyle n^{th}\) power.

Since \(\displaystyle T\) is divisible by the \(\displaystyle n^{th}\) power of all numbers that are smaller then \(\displaystyle M\), and \(\displaystyle r<2^n\), therefore \(\displaystyle sT+r\) can only be divisible by the \(\displaystyle n^{th}\) power of those numbers that are at least \(\displaystyle M\) and at most \(\displaystyle \sqrt[n]{KT}\). Moreover, for an arbitrary \(\displaystyle k\), among the \(\displaystyle K\) elements of \(\displaystyle \{T+r,2T+r,...,KT+r\}\) at most \(\displaystyle \lceil \frac{K}{k^n} \rceil\) can be divisible by \(\displaystyle k^n\), since we can assume that \(\displaystyle k\) is coprime to \(\displaystyle T\), otherwise non of the elements will be divisible by \(\displaystyle k^n\). Thus

\(\displaystyle X_r\le \sum_{k=M}^{\sqrt[n]{KT}} \lceil \frac{K}{k^n} \rceil\le \sqrt[n]{KT}+\sum_{k=M}^{\infty} \frac{K}{k^n} \le \sqrt[n]{KT}+\frac{K}{2^{n+2}}.\)

If we choose \(\displaystyle K\) to be large enough, such that \(\displaystyle \sqrt[n]{KT}<\frac{K}{2^{n+2}}\) is satisfied, we get \(\displaystyle X_r<\frac{K}{2^{n+1}}\).

Since \(\displaystyle X_r\) is the number of those for which \(\displaystyle mT+r\) is divisible by a perfect \(\displaystyle n^{th}\) power for \(\displaystyle m\le K\), and \(\displaystyle X_1+X_2+...+X_{2^n-1}<K/2\), therefore at least for \(\displaystyle K/2\) values of \(\displaystyle m\le K\) consecutive integers \(\displaystyle \{mT+1,mT+2,...,mT+2^n-1\}\) cannot contain a perfect \(\displaystyle k^{th}\) power for large enough values of \(\displaystyle K\), and this proves that infinitely many such values of \(\displaystyle m\) exist.

Statistics:

21 students sent a solution.
7 points:	Bodor Mátyás, Chrobák Gergő, Czanik Pál, Diaconescu Tashi, Fleischman Illés, Foris Dávid, Holló Martin, Nguyen Kim Dorka, Simon László Bence, Szabó 810 Levente, Szakács Ábel, Varga Boldizsár, Wiener Anna, Zömbik Barnabás.
5 points:	2 students.
4 points:	1 student.
3 points:	1 student.
1 point:	2 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, November 2023