Distance between consecutive elements of the multiplicative group of integers modulo n

Steven Brown
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 30, 2024, Number 1, Pages 81–99
DOI: 10.7546/nntdm.2024.30.1.81-99
Full paper (PDF, 314 Kb)

Details

Authors and affiliations

Steven Brown
41 Boulevard du Roi, 78000 Versailles, France

Abstract

For a prime number p, we consider its primorial P:=p\# and U(P):={\left(\ZZ{P}\right)}^\times the set of elements of the multiplicative group of integers modulo P which we represent as points anticlockwise on a circle of perimeter P. These points considered with wrap around modulo P are those not marked by the Eratosthenes sieve algorithm applied to all primes less than or equal to p.

In this paper, we are mostly concerned with providing formulas to count the number of gaps of a given even length D in U(P) which we note K(D,P). This work, presented with different notations is closely related to [5]. We prove the formulas in three steps. Although only the last step relates to the problem of gaps in the Eratosthenes sieve (see Section 3.2.2) the previous formulas may be of interest to study occurrences of defined gaps sequences.

  • For a positive integer n, we prove a general formula based on the inclusion-exclusion principle to count the number of occurrences of configurations1 in any subset of \ZZ{n}. (see Equation (7) in Theorem 2.1).
  • For a square-free integer P, we particularize this formula when the subset of interest is U(P). (see Equation (11) in Theorem 3.2).
  • For a prime p and its primorial P:=p\#, we particularize the formula again to study gaps in U(P). Given a positive integer D representing a distance on the circle, we give formulas to count K(D,P) the number of gaps of length D between elements of U(P) (see Equation (15) and Section 4.1).

In addition, we provide a formula (see Equation (27) in Theorem 5.1) to count the number of occurrences of gaps of an even length N that contain exactly i elements of U(P).

1 A defined sequence of gaps between the elements of the subset; this is referred to as a constellation in [5].

Keywords

  • Sieves
  • Sieve of Eratosthenes
  • Modular arithmetic
  • Multiplicative group of integers modulo
  • Chinese remainder theorem
  • Inclusion-exclusion principle
  • Euler’s phi function
  • Nagell’s totient function
  • Prime numbers
  • Jacobsthal function
  • Primorial

2020 Mathematics Subject Classification

  • 11A07
  • 11A41
  • 11B99
  • 11N05
  • 11N35
  • 11N99
  • 03E99

References

  1. Andreescu, T., & Andrica, D. (2009). Number Theory: Structures, Examples, and Problems. Birkhauser.
  2. Cohen, E. (1960). Nagell’s totient function. Mathematica Scandinavica, 8(1), 55–58.
  3. Hardy, G. H., & Wright, E. M. (1979). An Introduction to the Theory of Numbers. Oxford University Press.
  4. Haukkanen, P., & Sivaramakrishnan, R. (1998). Nagell’s totient revisited. Notes on Number Theory and Discrete Mathematics, 4(3), 93–100.
  5. Holt, F. B. (2015). Combinatorics of the gaps between primes. Preprint. arXiv:1510.00743.
  6. Iwaniec, H. (1978). On the problem of Jacobsthal. Demonstratio Mathematica, 11(1), 225–232.
  7. OEIS Foundation Inc. (2023). The On-Line Encyclopedia of Integer Sequences. Available online at: https://oeis.org.
  8. Tarnauceanu, M. (2013). A generalization of the Euler’s totient function. Preprint. arXiv:1312.1428.
  9. Van Hamme, L. (1971). Sur une gen eralisation de l’indicateur d’Euler. Bulletins de l’Academie Royale de Belgique, 57(1), 805–817.
  10. Weisstein, E. W. (2009). Landau’s Problems. Available online at: https://
    mathworld.wolfram.com/.
  11. Ziller, M. (2020). On differences between consecutive numbers coprime to primorials. Preprint. arXiv:2007.01808.

Manuscript history

  • Received: 2 October 2023
  • Revised: 12 December 2024
  • Accepted: 11 February 2024
  • Online First: 29 February 2024

Copyright information

Ⓒ 2024 by the Author.
This is an Open Access paper distributed under the terms and conditions of the Creative Commons Attribution 4.0 International License (CC BY 4.0).

Related papers

  • Haukkanen, P., & Sivaramakrishnan, R. (1998). Nagell’s totient revisited. Notes on Number Theory and Discrete Mathematics, 4(3), 93–100.

Cite this paper

Brown, S. (2024). Distance between consecutive elements of the multiplicative group of integers modulo n. Notes on Number Theory and Discrete Mathematics, 30(1), 81-99, DOI: 10.7546/nntdm.2024.30.1.81-99.

Comments are closed.