Longest arithmetic progressions in reduced residue systems
type: Item
instance of: scholarly article
title: Longest arithmetic progressions in reduced residue systems
zbMATH Open document ID: 1433.11006
author: Prapanpong Pongsriiam
published in: Journal of Number Theory
publication date: 2017-11-02T00:00:00Z
review text: 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)\) …
reviewed by: Olaf Ninnemann
Mathematics Subject Classification ID: 11B25
Mathematics Subject Classification ID: 11A07
Mathematics Subject Classification ID: 11N37
Mathematics Subject Classification ID: 11N56
zbMATH DE Number: 6802536
zbMATH Keywords: arithmetic progression
zbMATH Keywords: residue class
zbMATH Keywords: prime
zbMATH Keywords: squarefree number
zbMATH Keywords: asymptotic
MaRDI profile type: Publication
full work available at URL: j.jnt.2017.07.017
OpenAlex ID: W2753063967
cites work: On the number of integers \(\leqq x\) whose prime factors divide \(n\)
cites work: The distribution of the average prime divisor of an integer
cites work: On the Integers Relatively Prime to $n$ and a Number-Theoretic Function Considered by Jacobsthal.
cites work: Unsolved problems in number theory
cites work: The Distribution of Totatives
cites work: On the difference of consecutive numbers prime to n
cites work: On the distribution of reduced residues
cites work: Q5402460
cites work: Q5524475
cites work: A short note on reduced residues
cites work: Some applications of Montgomery's sieve
cites work: On the order of magnitude of Jacobsthal's function
DOI: 10.1016/J.JNT.2017.07.017
description: scientific article; zbMATH DE number 6802536