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.
- A short note on reduced residues
- scientific article; zbMATH DE number 3236932 (Why is no real title available?)
- On the difference of consecutive numbers prime to n
- On the distribution of reduced residues
- On the Integers Relatively Prime to n and a Number-Theoretic Function Considered by Jacobsthal.
- On the number of integers x whose prime factors divide n
- On the order of magnitude of Jacobsthal's function
- Some applications of Montgomery's sieve
- The average largest prime factor
- The distribution of the average prime divisor of an integer
- The Distribution of Totatives
- Unsolved problems in number theory
- Arithmetic progressions that consist only of reduced residues
- Arithmetic progressions in the least positive reduced residue systems
- Longest arithmetic progressions of palindromes
- Sumsets associated with Wythoff sequences and Fibonacci numbers
- A short note on reduced residues
- Arithmetic progressions in the values of a quadratic polynomial
- Length of the longest arithmetic progressions in a certain reduced residue system
This page was built for publication: Longest arithmetic progressions in reduced residue systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1675609)
