Longest arithmetic progressions in reduced residue systems (Q1675609)

From MaRDI portal
Revision as of 15:36, 14 July 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Longest arithmetic progressions in reduced residue systems
scientific article

    Statements

    Longest arithmetic progressions in reduced residue systems (English)
    0 references
    2 November 2017
    0 references
    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.
    0 references
    arithmetic progression
    0 references
    residue class
    0 references
    prime
    0 references
    squarefree number
    0 references
    asymptotic
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references