This project aims to produce an academic-quality paper documenting complete
modulus trees and some of their basic properties. An outline of the project
is available in outline.md. An additional goal of this project is to collect
knowledge of these structures into a single location so that students of
elementary number theory, prime number theory, discrete mathematics, and basic
tree theory can more easily study and explore these structures.
Complete modulus trees are discrete structures that organize positive integers into tree structures using the modulus function. They are closely tied to the Chinese remainder theorem and to Euler's totient function. This makes these structures particularly suited to many interesting mathematical applications, including encryption, the study of reduced residue systems and the distribution of prime numbers, the examination of some of the deeper consequences of the Chinese remainder theorem, and prime number sieving.
I (Adam Nickle) discovered these structures during a discrete mathematics course discussion on basic tree theory. Other computer science classes I had already completed had covered some of the discussion topics, so my mind began to wander and I began to doodle in a notebook. Eventually, an interesting question occurred to me: is it possible to create a complete tree based on the modulus function? After several attempts over the next few days, I produced what we now refer to as the sequential prime modulus tree. My fellow students and I found this structure to be so interesting that it kicked off over two years of original research into their behavior and properties.
This paper is an attempt to codify these learnings into a format that can be beneficial to anyone interested in learning more about the Chinese remainder theorem, Euler's totient function (and related functions for counting tuples in reduced residue systems), primorials, and prime numbers.