Longest arithmetic progressions in reduced residue systems
From the text: In this article, the author completely determines the length of longest arithmetic progressions in the least positive reduced residue system and in all reduced residue systems modulo \(n\) for every positive integer \(n\). For each \(n\in\mathbb N\), let \(A(n) = \{a\in\mathbb N\mid 1 \le a\le n\text{ and }(a, n) = 1\}\) be the least positive reduced residue system modulo \(n\) and let \(f(n)\) be the length of longest arithmetic progressions contained in \(A(n)\). \textit{Bernardo Recamán} (see Chapter B40 in [R. K. Guy, Unsolved problems in number theory. 3rd ed. New York: Springer-Verlag (2004; Zbl 1058.11001)]) asked if \(f(n)\to\infty\) as \(n\to\infty\). \textit{P. Stumpf} [Integers 17, Paper A04, 4 p. (2017; Zbl 1357.11013)] recently gave an affirmative answer to this question by establishing the bounds \[ \max\left\{\frac{p-1}{2}, \frac{n}{\gamma(n)}\right\} \le f(n) \le \max\left\{p-1, \frac{n}{\gamma(n)}\right\}. \] where \(p\) is the largest prime factor of \(n\) and \(\gamma(n) = \prod_{p\mid n} p\). In this article, the author extends his ideas further and obtain exact formula for \(f(n)\) for all \(n\) (see Theorems 3.1, 3.2, and 3.3). Note that there may be two or more arithmetic progressions contained in \(A(n)\) having maximal length. In addition, if we consider the reduced residue system different from \(A(n)\), the length of longest arithmetic progressions may be more than \(f(n)\). Let \(B(n)\) be a set of reduced residue system modulo \(n\) and let \(f_B(n)\) be the length of longest arithmetic progressions contained in \(B(n)\). Then it is natural to consider a function \(F\colon \mathbb N\to \mathbb N\) given by \[ F(n) = \max\{f_B(n) \mid B(n) \text{ is a set of reduced residue system modulo }n\}. \] The author gives an exact formula for \(F(n)\) in Theorem 3.4. In addition, he obtains a maximal order and a minimal order for \(F(n)\) and \(f(n)\) in Theorems 3.5 and 3.6, respectively. Estimates for the partial sums of \(F(n)\) and \(f(n)\) are also given in Theorems 3.7 and 3.8, respectively.
scientific article; zbMATH DE number 6802536