On Composite Moduli from the Viewpoint of Idempotent Numbers

Thesis

Joseph Vass

vass31@yahoo.com

Eötvös Loránd University Budapest, Hungary

Contents

1 Introduction 2 2 Basic Definitions 4 3 Idempotent Numbers 5 4 Normal Numbers 8 5 Regular Numbers 10 6 Binomial Congruences 24 7 Generalized Primitive Roots 27 8 Number Theoretic Functions 29 9 Idempotent Numbers as an Algebraic Structure 34 10 Second-Degree Polynomials 38

1 Introduction

The purpose of this paper is to introduce basic concepts, as of yet unknown, that are fundamental in the examination of composite moduli, while avoiding the notoriously difficult problem of prime-factorization. We introduce a new class of numbers, called the set of idempotent numbers, that is unavoidable when researching composite moduli. Among many interesting results, we give generalizations of well-known theorems and definitions, such as the Euler-Fermat Theorem and the concept of primitive roots. We consider the generalization of the equivalence condition for the solvability of a binomial congruence to be the main result of our paper. The paper is organized into sections of definitions, theorems, and notes. We intended to include every single result known to us regarding idempotent numbers, so as to propagate any further research that may be done on the subject by other authors. We provide basically no references, since we were unable to find any, on this particular part of Number Theory. Some of the simpler results however, may be known to group theorists, or may be found among exercises in textbooks. Since we publish all of our results, it is no surprise that the reader may find incomplete lines of thought within the network of theorems. We welcome and surely appreciate any helpful comments and papers that would be related to them. Many of our notes in this paper are meant to provide insight to the reader into our aims of research currently in progress. As we have formerly mentioned, the paper itself is concerned with revealing all the known implications of the existence of a set, called the set of idempotent numbers, modulo a composite number. In the next section, we provide definitions and notations, which will be used throughout the paper. In the section "Idempotent Numbers", we give results which show the fundamentality of this set, whenever we wish to explore the hazy structure of composite moduli. We also give a generalization of the definition of order, based on our generalization of the well-known Euler-Fermat Theorem. In the section "Normal Numbers", we define a set, which has quite a hazy structure, although not as much as the whole of ℤ_{m}. In the section "Regular Numbers", we introduce the nicest and most general set, that one can work with, when examining composite moduli. We are going to show many properties for this set, that have only been known so far for its subset of reduced residues, and we will also partition it into subsets of Abelian groups. We also give several other definitions and results, to the best of our knowledge, as of yet unknown. The next section is the most important one, since it contains the main result of this paper, which is an equivalence condition for the solvability of a binomial congruence, to the greatest degree of generality, we could hope to reach. This condition is currently difficult to calculate in practice. The next section generalizes the well-known definition of primitive roots to composite moduli. It includes only a few results, which implies that it needs the most intensive level of research, since we believe that revealing the structure of generalized primitive roots, shall also solve the problem of calculating the condition we have spoken of above. The section "Number Theoretic Functions", introduces functions defined through definitions of previous sections, all of them containing the idea of idempotent numbers. The set of idempotent numbers shows interesting algebraic properties, as revealed in the next section. Some nice operators may be defined over its elements, which are analogous to operators known from Set Theory. We will also show that idempotent numbers form a commutative ring. Our last section, entitled "Second-Degree Polynomials", discusses their sets of solutions, and in some special cases, characterizes them as well, with the use of idempotent numbers.

2 Basic Definitions

Let ℕ denote the set of whole numbers greater than or equal to 1. By "number" we will mean any whole number. In the entire paper, let m denote a fixed integer, and let

m = ∏_{i=1}^{∞} p_{i}^{α_{i}}, p_{i} prime, p_{i} < p_{i+1}, α_{i} ∈ ℕ ∪ {0}, i ∈ ℕ

be the prime-factorization of m. m is said to be square-free if α_{i} ≤ 1 for all i ∈ ℕ.

ω(m) := |{i ∈ ℕ : α_{i} > 0}|

We shall call m a weakly even number, if p_{1} = 2 and 0 ≤ α_{1} ≤ 2. Furthermore, we shall call m a barely even number, if p_{1} = 2 and α_{1} = 1. Let ⇒ denote logical inference. Let "iff" mean logical equivalence, or "if and only if", and let it be denoted by ⇔. Let ∃ denote existence (∃! meaning "exists exactly one"), and ∀ the logical term "for all".

ℤ_{m} := {1, …, m}

In case of A ⊂ ℤ_{m}, a ∈ ℤ

a ∈_{m} A ⇔ ∃b ∈ A : a ≡ b (mod m)

Let a mod m denote the number b ∈ ℤ_{m} for which a ≡ b (mod m). In case of A ⊂ ℤ

A mod m := {a mod m : a ∈ A}

Let (a, b) denote the greatest common divisor of the numbers a and b. Also, in case of A ⊂ ℕ, let gcd(a : a ∈ A) denote the greatest common divisor of all the elements in A. Let [a, b] denote the least common multiple of the numbers a and b. Also, in case of A ⊂ ℕ, let lcm(a : a ∈ A) denote the least common multiple of all the elements in A. In case of an integral vector a ∈ ℕ^{n}, n ∈ ℕ, let [a] denote the least common multiple of the coordinates of a. Let φ(m) denote the number of integers relatively prime to, and not exceeding m. Furthermore, let ψ(m) denote

ψ(m) := lcm(φ(p_{i}^{α_{i}}) : α_{i} > 0)

(Note that if m is weakly even, then the maximal order modulo m is ψ(m).) For a, b ∈ ℤ, let a | b denote that a is a divisor of b. In case of vectors a, b ∈ ℤ^{n}, n ∈ ℕ, and any relation ∼, let a ∼ b mean that a_{i} ∼ b_{i} for all 1 ≤ i ≤ n. Let Dom(f) denote the domain of function f. Regarding other basic notations and theorems on congruences, see [1].

3 Idempotent Numbers

Definition 3.1 A number e is said to be idempotent modulo m, if

e^{2} ≡ e (mod m)

Let E_{m} denote the subset of idempotent numbers in ℤ_{m}.

We will mostly denote an idempotent number by e. The notation comes from the first letter of the Hungarian word for "unit", since there may be defined groups in ℤ_{m}, with their units being idempotent numbers modulo m. If m has only one prime factor, then E_{m} = {1, m}.

Theorem 3.1 For all a ∈ ℤ

a^{φ(m)} ∈_{m} E_{m}

Proof Let i ∈ ℕ be a fixed number, and α_{i} > 0. There are two possibilities.

1. p_{i} | a Since

α_{i} = 1 + (α_{i} − 1) ≤ 2^{α_{i}−1} ≤ p_{i}^{α_{i}−1} ≤ p_{i}^{α_{i}−1}(p_{i} − 1) ≤ φ(m)

we have

a^{φ(m)} ≡ 0 (mod p_{i}^{α_{i}})

2. p_{i} ∤ a In this case, by the Euler-Fermat Theorem (and φ(p_{i}^{α_{i}}) | φ(m)), we have

a^{φ(m)} ≡ 1 (mod p_{i}^{α_{i}})

In both cases 1. and 2., we have

a^{φ(m)}(a^{φ(m)} − 1) ≡ 0 (mod p_{i}^{α_{i}})

so for all i ∈ ℕ we have

(a^{φ(m)})^{2} ≡ a^{φ(m)} (mod p_{i}^{α_{i}})

which means that

(a^{φ(m)})^{2} ≡ a^{φ(m)} (mod m)

so a^{φ(m)} is idempotent modulo m. □

Theorem 3.2 For all a ∈ ℤ

a^{ψ(m)} ∈_{m} E_{m}

Proof The proof goes the same way as above, by changing each φ(m) to ψ(m). □

Many interesting facts follow from the two theorems above. One is that every polynomial is equivalent to a polynomial of degree less than or equal to 2ψ(m) − 1 (modulo m).

Theorem 3.3 For all a ∈ ℤ

a^{φ(m)} ≡ (a, m)^{φ(m)} (mod m)

Proof This fact may be proven the same way as Theorem 3.1, by considering that

p_{i} | a ⇔ p_{i} | (a, m) (α_{i} > 0)

□

Theorem 3.4

|E_{m}| = 2^{ω(m)}

Proof From the proof of Theorem 3.1, we see that a number is idempotent modulo m iff it is congruent to either 0 or 1 modulo each of the prime power divisors of m. From this fact, our theorem follows quite clearly, by the application of the Chinese Remainder Theorem (see [1]). □

Theorem 3.5 For k ∈ ℕ

|kE_{m} mod m| = 2^{ω(\frac{m}{(k,m)})}

Proof Let

\frac{m}{(k, m)} = ∏_{i=1}^{∞} p_{i}^{β_{i}}

be the prime-factorization of \frac{m}{(k,m)}. We see that β_{i} = 0 iff p_{i}^{α_{i}} | k, so

ω (\frac{m}{(k, m)}) = |\{i : β_{i} > 0\}| = |\{i : p_{i}^{α_{i}} ∤ k\}|

Without hurting generality, we may suppose that p_{i} are ordered so that for some n ∈ ℕ we have β_{i} > 0 if 1 ≤ i ≤ n and β_{i} = 0 if i > n. Let

m_{1} := ∏_{i=1}^{n} p_{i}^{α_{i}}, m_{2} := ∏_{i=n+1}^{∞} p_{i}^{α_{i}}

This way we have for all e ∈ E_{m} that

ke ≡ 0 or ke ≡ k ≢ 0 (mod p_{i}^{α_{i}}) (1 ≤ i ≤ n)

and ke ≡ 0 (mod m_{2}). So by the Chinese Remainder Theorem and Theorem 3.4 we have

|kE_{m} mod m| = |kE_{m_{1}} mod m_{1}| · |kE_{m_{2}} mod m_{2}| = |E_{m_{1}}| · |\{0\}| = 2^{n} = 2^{ω(\frac{m}{(k,m)})}

□

Theorem 3.6 If for some a ∈ ℤ, k, l ∈ ℕ, we have a^{k}, a^{l} ∈_{m} E_{m}, then a^{k} ≡ a^{l} (mod m).

Proof

a^{k} ≡ (a^{k})^{l} ≡ a^{kl} ≡ (a^{l})^{k} ≡ a^{l} (mod m)

□

Definition 3.2 For a ∈ ℤ, let its order modulo m to be the smallest n ∈ ℕ for which a^{n} ∈_{m} E_{m}. Let |a|_{m} denote this n.

a^{0} := a^{|a|_{m}} mod m

Furthermore, let the inverse of a be denoted as

a^{−1} := a^{|a|_{m}−1} mod m

and for k ∈ ℕ

a^{−k} := (a^{−1})^{k} mod m

For b ∈ ℤ, if it exists, let ind_{b}^{m}a denote the smallest k ∈ ℕ, for which b^{k} ≡ a (mod m), and let its existence be denoted as ∃ind_{b}^{m}a.

The existence of the above n is guaranteed by Theorem 3.1.

Theorem 3.7 If for some a ∈ ℤ, k, n ∈ ℕ, k ≤ n we have a^{k+n} ≡ a^{k} (mod m), then a^{n} ∈_{m} E_{m}.

Proof

a^{k+n} ≡ a^{k} ⇒ a^{n−k}a^{k+n} ≡ a^{n−k}a^{k} ⇒ (a^{n})^{2} ≡ a^{n} (mod m)

so we have that a^{n} ∈_{m} E_{m}. □

Theorem 3.8 If m_{1}, m_{2} ∈ ℕ, m = [m_{1}, m_{2}], then

e ∈ E_{m} ⇔ e ∈_{m_{1}} E_{m_{1}} and e ∈_{m_{2}} E_{m_{2}}

Proof This follows from the fact that a number is idempotent modulo m iff it is congruent to either 0 or 1 modulo each of the prime power divisors of m. □

Problem 3.1 Defining the sequence of numbers (a_{n})_{n=1}^{∞} recursively with

a_{0} := 1, a_{n} := 42^{a_{n−1}} (n ∈ ℕ)

what will be the last two digits of a_{100}?

Solution With some calculation, we get the following results

a_{100} = 42^{a_{99}}, |42|_{100} = 20, 42^{20} ≡ 76 (mod 100)
a_{99} = 42^{a_{98}}, |42|_{20} = 4, 42^{4} ≡ 16 (mod 20)
a_{98} = 42^{a_{97}}, |42|_{4} = 2, 42^{2} ≡ 4 (mod 4)
a_{97} ≡ 0 (mod 2) ⇒ a_{98} ≡ 0 (mod 4) ⇒ a_{99} ≡ 16 (mod 20) ⇒
⇒ a_{100} ≡ 76 · 42^{16} ≡ 76 · 56 ≡ 56 (mod 100)

□

Note that the above problem may be solved in other ways as well. I decided to include it in our discussion, because this idea of a solution made me realize the importance of idempotent numbers when discussing composite moduli, and it also gave me incentive to investigate composite moduli from the viewpoint of idempotent numbers, starting the research which resulted in this paper.

4 Normal Numbers

Definition 4.1 a ∈ ℤ is said to be normal modulo m if the following logical inference holds

a^{k} ∈_{m} E_{m} ⇒ |a|_{m} | k (k ∈ ℕ)

Let N_{m} denote the subset of normal numbers in ℤ_{m}. Furthermore, for e ∈ E_{m}, let N_{m}^{e} denote the set

{a ∈ N_{m} : a^{|a|_{m}} ≡ e (mod m)}

Theorem 4.1 A number a ∈ ℤ_{m} is normal iff the following logical inference holds

a^{k} ≡ a^{l} (mod m) ⇒ k ≡ l (mod |a|_{m}) (k, l ∈ ℕ)

Proof First, let us suppose that a ∈ ℤ_{m} is normal. Then

a^{k} ≡ a^{l} ⇒ a^{k}a^{lφ(m)−l} ≡ a^{lφ(m)} (mod m)

Since a^{lφ(m)} ∈_{m} E_{m} and |a|_{m} | φ(m), we have

0 ≡ k + lφ(m) − l ≡ k − l ⇒ k ≡ l (mod |a|_{m})

Now, if the inference holds, with l := |a|_{m} we have that a is normal. □

Theorem 4.2 If m_{1}, m_{2} ∈ ℕ, m_{1} | m_{2}, a ∈ N_{m_{1}}, then |a|_{m_{1}} | |a|_{m_{2}}.

Proof

a^{|a|_{m_{2}}} ∈_{m_{2}} E_{m_{2}}, m_{1} | m_{2} ⇒ a^{|a|_{m_{2}}} ∈_{m_{1}} E_{m_{1}}, a ∈ N_{m_{1}} ⇒ |a|_{m_{1}} | |a|_{m_{2}}

□

Theorem 4.3 Let m_{1}, m_{2} ∈ ℕ be such that m = [m_{1}, m_{2}], and a ∈ ℤ_{m}. If a ∈_{m_{1}} N_{m_{1}} and a ∈_{m_{2}} N_{m_{2}}, then a ∈ N_{m} and |a|_{m} = [|a|_{m_{1}}, |a|_{m_{2}}].

Proof By Theorem 3.8, for k ∈ ℕ we have

a^{k} ∈_{m} E_{m} ⇔ a^{k} ∈_{m_{1}} E_{m_{1}}, a^{k} ∈_{m_{2}} E_{m_{2}} ⇒ [|a|_{m_{1}}, |a|_{m_{2}}] | k

so [|a|_{m_{1}}, |a|_{m_{2}}] | |a|_{m}. With k = [|a|_{m_{1}}, |a|_{m_{2}}] we have a^{[|a|_{m_{1}},|a|_{m_{2}}]} ∈_{m} E_{m} so |a|_{m} ≤ [|a|_{m_{1}}, |a|_{m_{2}}], so |a|_{m} = [|a|_{m_{1}}, |a|_{m_{2}}]. We also see from above that a is normal modulo m. □

Theorem 4.4 If a ∈ N_{m}, k ∈ ℕ then

|a^{k}|_{m} = \frac{|a|_{m}}{(k, |a|_{m})}

Proof

(a^{k})^{\frac{|a|m}{(k,|a|m)}} ≡ (a^{|a|_{m}})^{\frac{k}{(k,|a|m)}} ∈_{m} E_{m}

so we have

|a^{k}|_{m} ≤ \frac{|a|_{m}}{(k, |a|_{m})}

by Definition 3.2.

a^{kl} ∈_{m} E_{m} ⇒ |a|_{m} | kl ⇔ \frac{|a|_{m}}{(k, |a|_{m})} | l

so we have

|a^{k}|_{m} ≥ \frac{|a|_{m}}{(k, |a|_{m})}

□ Theorem 4.5 If a ∈ N_{m}, n ∈ ℕ, then a^{n} ∈_{m} N_{m}. Proof For all k ∈ ℕ

(a^{n})^{k} ∈_{m} E_{m} ⇒ |a|_{m} | nk ⇔ |a^{n}|_{m} = \frac{|a|_{m}}{(n, |a|_{m})} | k

□ Theorem 4.6 Let e ∈ E_{m}, a, b ∈ N_{m}^{e}, k ∈ ℕ be such that ∃ind_{b}^{m}a. Then

a^{\frac{|b|m}{(k,|b|m)}} ∈_{m} E_{m} ⇒ (k, |b|_{m}) | ind_{b}^{m}a

Proof

e ≡ a^{\frac{|b|m}{(k,|b|m)}} ≡ b^{\frac{|b|mind^{m}_{b}a}{(k,|b|m)}} (mod m) ⇒

⇒ |b|_{m} | \frac{|b|_{m}ind_{b}^{m}a}{(k, |b|_{m})} ⇔ \frac{ind_{b}^{m}a}{(k, |b|_{m})} ∈ ℤ ⇔ (k, |b|_{m}) | ind_{b}^{m}a

□ Theorem 4.7 For all a ∈ N_{m} we have a^{−1} ∈ N_{m}, |a^{−1}|_{m} = |a|_{m} and

(a^{−1})^{−1} ≡ a^{|a|_{m}+1} (mod m)

Proof The first statement follows from Theorem 4.5. The second statement follows from Theorems 4.5 and 4.4 since

|a^{|a|_{m}−1}|_{m} = \frac{|a|_{m}}{(|a|_{m} − 1, |a|_{m})} = |a|_{m}

If |a|_{m} ≥ 2 then

(a^{−1})^{−1} ≡ (a^{|a|_{m}−1})^{|a|_{m}−1} ≡ a · (a^{|a|_{m}})^{|a|_{m}−2} (mod m)

The case of a ∈ E_{m} is trivial. □

5 Regular Numbers

Definition 5.1 a ∈ ℤ is said to be regular modulo m if

a^{|a|_{m}+1} ≡ a (mod m)

Let R_{m} denote the subset of regular numbers in ℤ_{m}. Furthermore, for e ∈ E_{m}, let R_{m}^{e} denote the set

{a ∈ R_{m} : a^{|a|_{m}} ≡ e (mod m)}

From Theorems 3.1 and 3.6 we have that for all a ∈ ℤ

a^{|a|_{m}} ≡ a^{φ(m)} (mod m)

We will apply this simple fact in our next theorem.

Theorem 5.1

R_{m} = ℤ_{m}

iff m is square-free.

Proof First, let us suppose that R_{m} = ℤ_{m}. Then for all i : α_{i} > 0 we have

p_{i}(p_{i}^{φ(m)} − 1) ≡ 0 (mod m) ⇒ p_{i}(p_{i}^{φ(m)} − 1) ≡ 0 (mod p_{i}^{α_{i}}) ⇒ α_{i} = 1

Now, if m is square-free, then for all a ∈ ℤ_{m}

a(a^{φ(m)} − 1) ≡ 0 (mod p_{i}) (i ∈ ℕ) ⇒ a(a^{φ(m)} − 1) ≡ 0 (mod m)

□

Theorem 5.2

R_{m} ⊂ N_{m}

Proof We need to show that for all a ∈ R_{m}, if a^{k} ∈_{m} E_{m} then |a|_{m} | k for all k ∈ ℕ. Let q, r ∈ ℕ ∪ {0} be such that

k = q|a|_{m} + r, 0 ≤ r < |a|_{m}

Let us suppose that r > 0. Then we have

a^{r} ≡ a · a^{r−1} ≡ a^{|a|_{m}+1} · a^{r−1} ≡ (a^{|a|_{m}})^{q} · a^{r} ≡ a^{k} (mod m)

so a^{r} ∈_{m} E_{m}, which is a contradiction by Definition 3.2. □

Theorem 5.3 For all e ∈ E_{m}

R_{m}^{e} = {ea mod m : a^{|a|_{m}} ≡ e (mod m), a ∈ ℤ_{m}}

Proof If a ∈ R_{m}^{e} then a ≡ e · a (mod m) which is obviously in the set on the right-hand side. Now if a ∈ ℤ_{m} is such that a^{φ(m)} ≡ e (mod m), then multiplying this congruence by ea we have

(ea)(ea)^{φ(m)} ≡ ea (mod m)

so ea ∈_{m} R_{m}^{e}. □

Theorem 5.4 For all a ∈ ℤ

a^{m} ≡ a^{m−φ(m)} ≡ a^{m+φ(m)} (mod m)

and

a^{m−φ(m)} ∈_{m} R_{m}

Furthermore

a^{φ(m)−1} ∈_{m} R_{m}

if |a|_{m} < φ(m) and a ∈ N_{m}.

Proof Let i ∈ ℕ be a fixed number, and α_{i} > 0. There are two possibilities.

1. p_{i} | a

α_{i} ≤ p_{i}^{α_{i}−1} ≤ p_{i}^{α_{i}−1} · q = m − φ(m)

for some q ∈ ℕ, so

a^{m−φ(m)} ≡ 0 (mod p_{i}^{α_{i}})

2. p_{i} ∤ a In this case we have

a^{φ(m)} ≡ 1 (mod p_{i}^{α_{i}})

In both cases 1. and 2., we have

a^{m−φ(m)}(a^{φ(m)} − 1) ≡ 0 (mod p_{i}^{α_{i}})

from which we have our first congruence. The second one follows easily, by multiplying both sides by a^{φ(m)}.

a^{m−φ(m)} · (a^{m−φ(m)})^{φ(m)} ≡ a^{m−φ(m)} · a^{φ(m)} = a^{m} ≡ a^{m−φ(m)} (mod m)

From Theorem 5.2, and the definition of normal numbers, we have that φ(m) = k|a|_{m} for some k > 1. So

a^{φ(m)−1} · (a^{φ(m)−1})^{φ(m)} ≡ a^{φ(m)−1} · a^{φ(m)} ≡
≡ a^{φ(m)} · a^{|a|_{m}} · a^{(k−1)|a|_{m}−1} ≡ a^{|a|_{m}} · a^{(k−1)|a|_{m}−1} = a^{φ(m)−1} (mod m)

□

Note that based on our previous theorem, we may define the function

δ_{m}(a) := min{n ∈ ℕ : a^{n} ∈_{m} R_{m}} (a ∈ ℤ_{m})

which has the property

δ_{m}(a) = min{n ∈ ℕ : a^{|a|_{m}+n} ≡ a^{n} (mod m)}

since

a^{n} ∈_{m} R_{m} ⇔ a^{|a|_{m}+n} ≡ a^{n} (mod m)

Theorem 5.5 A number a ∈ ℤ_{m} is regular iff the following logical inference holds

p_{i} | a ⇒ p_{i}^{α_{i}} | a (i ∈ ℕ, α_{i} > 0)

Proof If a ∈ R_{m} then a · a^{φ(m)} ≡ a (mod m). Let i ∈ ℕ be such that α_{i} > 0, and suppose that p_{i} | a. Then as in the proof of Theorem 3.1, we have

a ≡ a · a^{φ(m)} ≡ a · 0 ≡ 0 (mod p_{i}^{α_{i}})

Now, let us suppose that the inference holds. Let i ∈ ℕ be such that α_{i} > 0. There are two possible cases.

1. p_{i} | a Then we know that p_{i}^{α_{i}} | a is true as well, so

a · a^{φ(m)} ≡ 0 ≡ a (mod p_{i}^{α_{i}})

2. p_{i} ∤ a In this case we have (a, p_{i}^{α_{i}}) = 1, so

a · a^{φ(m)} ≡ a (mod p_{i}^{α_{i}})

From these two cases we have that a ∈ R_{m}. □

Theorem 5.6 A number a ∈ ℤ_{m} is regular iff the following equivalence holds

a^{k} ≡ a^{l} (mod m) ⇔ k ≡ l (mod |a|_{m}) (k, l ∈ ℕ)

It is also true that if a ∈ ℤ_{m} is regular, then the following equivalence holds

a^{k} ∈_{m} E_{m} ⇔ |a|_{m} | k (k ∈ ℕ)

Proof Let us first suppose that a ∈ ℤ_{m} is regular. The ⇒ part of the equivalence follows from Theorems 4.1 and 5.2. The ⇐ part is also true, since if l ≥ k and k ≡ l (mod |a|_{m}), then for some q ≥ 0, we have l = k + q|a|_{m}, so

a^{l} ≡ a^{k+q|a|_{m}} ≡ a^{k}a^{|a|_{m}} ≡ a^{k} (mod m)

where the last congruence holds, because a is regular. Let us now suppose that the equivalence holds. Then, with k := |a|_{m} + 1, l := 1, we have that a is regular. The second equivalence follows easily from the first. □

Theorem 5.7 A number a ∈ ℤ_{m} is regular iff there exists some n > 1 such that

a^{n} ≡ a (mod m)

Proof First, let us suppose that such an n exists. Then by Theorem 3.7 we have a^{n−1} ∈_{m} E_{m}, from which a^{n−1} ≡ a^{|a|_{m}} (mod m) follows by the application of Theorem 3.6. So, by multiplying this congruence by a, we get our desired result. Now, supposing that a is regular, we may take n := |a|_{m} + 1. □

Theorem 5.8 For a ∈ ℤ_{m}

a ∈ R_{m} ⇔ (a, \frac{m}{(a, m)}) = 1 ⇔ (a, m) ∈ R_{m}

Proof The first equivalence follows clearly from Theorem 5.5. Using this, and the fact that

((a, m), \frac{m}{((a, m), m)}) = (a, \frac{m}{(a, m)})

we get the second equivalence. □

Theorem 5.9 For all a ∈ N_{m}

a ∈ R_{m} ⇔ (a^{−1})^{−1} ≡ a (mod m)

Proof Follows from Theorem 4.7. □

Theorem 5.10 Let m_{1}, m_{2} ∈ ℕ be such that m = [m_{1}, m_{2}], and a ∈ ℤ_{m}. Then

a ∈ R_{m} ⇔ a ∈_{m_{1}} R_{m_{1}} and a ∈_{m_{2}} R_{m_{2}}

Furthermore, if a ∈ R_{m} then |a|_{m} = [|a|_{m_{1}}, |a|_{m_{2}}].

Proof We will prove the equivalence using Theorem 5.5. Let us suppose that m_{1} and m_{2} have prime-factorizations

m_{1} = ∏_{i=1}^{∞} p_{i}^{β_{i}}, m_{2} = ∏_{i=1}^{∞} p_{i}^{γ_{i}}

Then we have that α_{i} = max(β_{i}, γ_{i}) for all i ∈ ℕ, since m = [m_{1}, m_{2}]. The ⇒ part: Taking any i such that p_{i} | a, we have p_{i}^{α_{i}} | a, which implies p_{i}^{β_{i}} | a and p_{i}^{γ_{i}} | a, since α_{i} = max(β_{i}, γ_{i}), so a ∈_{m_{1}} R_{m_{1}} and a ∈_{m_{2}} R_{m_{2}}. The ⇐ part: Taking any i such that p_{i} | a, we have p_{i}^{β_{i}} | a and p_{i}^{γ_{i}} | a, which implies p_{i}^{α_{i}} | a, so we have that a ∈ R_{m}. Now, let us suppose that a ∈ R_{m}. By Theorem 3.8, for k ∈ ℕ we have

a^{k} ∈_{m} E_{m} ⇔ a^{k} ∈_{m_{1}} E_{m_{1}}, a^{k} ∈_{m_{2}} E_{m_{2}} ⇔ [|a|_{m_{1}}, |a|_{m_{2}}] | k

From this we have that [|a|_{m_{1}}, |a|_{m_{2}}] | |a|_{m}. With k = [|a|_{m_{1}}, |a|_{m_{2}}] we have a^{[|a|_{m_{1}},|a|_{m_{2}}]} ∈_{m} E_{m} so |a|_{m} ≤ [|a|_{m_{1}}, |a|_{m_{2}}], so |a|_{m} = [|a|_{m_{1}}, |a|_{m_{2}}]. □

Theorem 5.11 For e ∈ E_{m}, there exist unique m_{1}, m_{2} ∈ ℕ such that m = m_{1}m_{2} and

e ≡ 1 (mod m_{1}) and e ≡ 0 (mod m_{2})

Furthermore, for all a ∈ ℤ_{m}, the following equivalence holds

a ∈ R_{m}^{e} ⇔ (a, m_{1}) = 1 and m_{2} | a

and if a ∈ R_{m}^{e} then |a|_{m} = |a|_{m_{1}}.

Proof The proof is quite trivial, with the previous theorem in mind. □

Definition 5.2 For a ∈ ℤ_{m}, a^{φ(m)} ≡ e (mod m), using the notations of the theorem above, denote μ_{m}(a) := m_{1}.

We advise the reader to observe throughout our paper, that in many cases it is sufficient to examine the set R_{μ_{m}(e)}^{1} instead of R_{m}^{e} (for any e ∈ E_{m}).

Theorem 5.12 For a ∈ ℤ_{m}

a ∈ R_{m} ⇔ a ∈_{p_{i}^{α_{i}}} R_{p_{i}^{α_{i}}} (i ∈ ℕ)

and, if a ∈ R_{m} then

|a|_{m} = lcm(|a|_{p_{i}^{α_{i}}} : 1 ≤ i ≤ ∞)

Furthermore,

|R_{m}| = ∏_{α_{i}>0}(1 + φ(p_{i}^{α_{i}}))

Proof Follows from Theorem 5.10. The formula for |R_{m}| follows from the fact that for a ∈ ℤ_{p_{i}^{α_{i}}}

a ∈ R_{p_{i}^{α_{i}}} ⇔ p_{i} ∤ a or p_{i}^{α_{i}} | a

which is a consequence of Theorem 5.5. □

Theorem 5.13 For all e ∈ E_{m}, the structure ⟨R_{m}^{e}; {e,^{−1} , ·}⟩ is an Abelian group.

Proof The properties to be shown are mostly trivial, except for maybe one. We need to show that for all a ∈ R_{m}^{e} there exists a unique b ∈ R_{m}^{e} such that ab ≡ e (mod m). Let b := a^{−1}. It is obvious that b ∈ R_{m}^{e} and ab ≡ e (mod m). Now, let us suppose that there exists some other b′ ∈ R_{m}^{e} such that ab′ ≡ e (mod m). Then we have

a(b − b′) ≡ 0 (mod m) ⇒ 0 ≡ a^{|a|_{m}−1} · a(b − b′) ≡
≡ e(b − b′) ≡ b^{|b|_{m}+1} − (b′)^{|b′|_{m}+1} ≡ b − b′ (mod m)

□

Theorem 5.14 If m is an odd number, then for all e ∈ E_{m}

∏ R_{m}^{e} ≡ (−1)^{2^{ω(μm(e))−1}} · e (mod m)

Proof We are going to make use of Theorem 10.5 from the last section, which states that

∏{a ∈ R_{m}^{e} : |a|_{m} ≤ 2} ≡ (−1)^{2^{ω(μm(e))−1}} · e (mod m)

For now, denote

S := {a ∈ R_{m}^{e} : |a|_{m} ≤ 2}

Then for all a ∈ R_{m}^{e}

a ≠ a^{−1} ⇔ a ∈ R_{m}^{e} \ S

By our previous theorem, we have that

∏ R_{m}^{e} \ S ≡ e (mod m)

So we have

∏ R_{m}^{e} ≡ (∏ R_{m}^{e} \ S) · (∏ S) ≡ e · (−1)^{2^{ω(μm(e))−1}} · e (mod m)

□

Theorem 5.15 For a ∈ R_{m}, n ∈ ℕ, i, j ∈ ℤ

(a^{n})^{−1} ≡ a^{−n} (mod m)
a^{i+j} ≡ a^{i} · a^{j} (mod m)

Proof The first statement is equivalent to saying that

a^{n \frac{|a|m}{(n,|a|m)} −n} ≡ a^{n|a|_{m}−n} (mod m)

which by Theorem 5.6 is equivalent to

n\frac{|a|_{m}}{(n, |a|_{m})} − n ≡ n|a|_{m} − n (mod |a|_{m})

(when n\frac{|a|_{m}}{(n,|a|_{m})} − n ≠ 0), and this congruence obviously holds. In the omitted case

n\frac{|a|_{m}}{(n, |a|_{m})} − n = 0 ⇔ |a|_{m} | n

So for some k ∈ ℕ, we have

a^{n|a|_{m}−n} = a^{(n−k)|a|_{m}} ≡ a^{0} (mod |a|_{m})

For the second property, we can distinguish four different cases (for nonzero exponents). Case of i, j < 0:

a^{i+j} = a^{−|i+j|} ≡ (a^{−1})^{|i+j|} = (a^{−1})^{|i|} · (a^{−1})^{|j|} ≡
≡ a^{−|i|} · a^{−|j|} ≡ a^{i} · a^{j} (mod m)

Case of i < 0, j > 0: Case of j ≥ |i|:

a^{i+j} = a^{j−|i|} ⇒ a^{j} = a^{i+j} · a^{|i|} ⇒
⇒ a^{i+j} ≡ a^{j} · (a^{|i|})^{−1} ≡ a^{j} · a^{−|i|} = a^{i} · a^{j} (mod m)

Case of j < |i|:

a^{i+j} ≡ a^{j−|i|} ≡ a^{−(|i|−j)} ≡ (a^{|i|−j})^{−1} ≡ (a^{|i|} · a^{−j})^{−1} (mod m)

where the last congruence is true with the application of the previous case.

(a^{|i|} · a^{−j}) · (a^{−|i|} · a^{j}) ≡ (a^{|i|})(a^{|i|})^{−1}(a^{j})^{−1}(a^{j}) ≡ (a^{|a|_{m}})^{|i|+j} ≡ a^{|a|_{m}} (mod m)

So by the unicity of the inverse (Theorem 5.13), we have

(a^{|i|} · a^{−j})^{−1} ≡ a^{−|i|} · a^{j} ≡ a^{i} · a^{j} (mod m)

Case of i, j > 0 is trivial. Case of i > 0, j < 0 is similar to the case of i < 0, j > 0. □

Definition 5.3 For a ∈ ℤ_{m}, let ⟨a⟩_{m} denote the set

{a^{n} mod m : 1 ≤ n ≤ |a|_{m}}

and in case of A ⊂ ℤ_{m}, let ⟨A⟩_{m} denote the set

⋃_{a∈A}⟨a⟩_{m}

Theorem 5.16 Let b, c ∈ R_{m}, n, k ∈ ℕ. Then

b^{n}, b^{k} ∈_{m} ⟨c⟩_{m} ⇔ b^{(n,k)} ∈_{m} ⟨c⟩_{m}

Proof Let us first suppose that b^{n} ≡ c^{i}, b^{k} ≡ c^{j} (mod m). Without hurting generality, we may suppose that there exist x, y ≥ 0 such that (n, k) = nx − ky. So we have

b^{(n,k)} = b^{nx−ky} = b^{nx+(−ky)} ≡ b^{nx} · b^{−ky} ≡ b^{nx} · (b^{ky})^{−1} ≡ (c^{ix}) · (c^{jy})^{φ(m)−1} ∈_{m} ⟨c⟩_{m}

with the application of Theorem 5.15. Now, let us suppose that b^{(n,k)} ≡ c^{l} (mod m). Then we have

b^{n} ≡ b^{(n,k) \frac{n}{(n,k)}} ≡ (c^{l})^{\frac{n}{(n,k)}} ∈_{m} ⟨c⟩_{m}

The proof is similar for b^{k} ∈_{m} ⟨c⟩_{m}. □

Definition 5.4 For e ∈ E_{m}, b, c ∈ R_{m}^{e}, denote

D_{m}(b, c) := gcd(n ∈ ℕ : 1 ≤ n ≤ |b|_{m}, b^{n} ∈_{m} ⟨c⟩_{m})

Theorem 5.17 If e ∈ E_{m}, b, c ∈ R_{m}^{e}, then D_{m}(b, c) | |b|_{m} and

b^{k} ∈_{m} ⟨c⟩_{m} ⇔ D_{m}(b, c) | k

It is also true that b^{D_{m}(b,c)} ∈_{m} ⟨c⟩_{m} and

⟨b⟩_{m} ∩ ⟨c⟩_{m} = ⟨b^{D_{m}(b,c)}⟩_{m}

Furthermore

|⟨b⟩_{m} ∩ ⟨c⟩_{m}| = \frac{|b|_{m}}{D_{m}(b, c)}

Proof By Theorem 5.16 and with induction, we have b^{D_{m}(b,c)} ∈_{m} ⟨c⟩_{m}. First, let us suppose that D_{m}(b, c) | k. Then we have

b^{k} ≡ (b^{D_{m}(b,c)})^{\frac{k}{Dm(b,c)}} ∈_{m} ⟨c⟩_{m}

Now, if b^{k} ∈_{m} ⟨c⟩_{m} then with k′ := k mod |b|_{m}, we have b^{k′} ∈_{m} ⟨c⟩_{m}, so D_{m}(b, c) | k′ by definition, and from this it follows that D_{m}(b, c) | k. So by the property now proven, we also have that

⟨b⟩_{m} ∩ ⟨c⟩_{m} = ⟨b^{D_{m}(b,c)}⟩_{m}

It is also true that D_{m}(b, c) | |b|_{m} since

b^{|b|_{m}} ≡ e ≡ c^{|c|_{m}} ∈_{m} ⟨c⟩_{m}

So we have

|⟨b⟩_{m} ∩ ⟨c⟩_{m}| = |⟨b^{D_{m}(b,c)}⟩_{m}| = |b^{D_{m}(b,c)}|_{m} = \frac{|b|_{m}}{(D_{m}(b, c), |b|_{m})} = \frac{|b|_{m}}{D_{m}(b, c)}

□

Theorem 5.18 Let k ∈ ℕ, e ∈ E_{m}, a, b ∈ R_{m}^{e}, ∃ind_{b}^{m}a. Then

(k, |b|_{m}) | ind_{b}^{m}a ⇔ a^{\frac{|b|m}{(k,|b|m)}} ∈_{m} E_{m}

Proof

e ≡ a^{\frac{|b|m}{(k,|b|m)}} ≡ b^{\frac{|b|mind^{m}_{b}a}{(k,|b|m)}} (mod m) ⇔

⇔ |b|_{m} | \frac{|b|_{m}ind_{b}^{m}a}{(k, |b|_{m})} ⇔ \frac{ind_{b}^{m}a}{(k, |b|_{m})} ∈ ℤ ⇔ (k, |b|_{m}) | ind_{b}^{m}a

□

Theorem 5.19 For e ∈ E_{m}, a, b ∈ R_{m}^{e}

(|a|_{m}, |b|_{m}) = 1 ⇔ |ab|_{m} = |a|_{m} · |b|_{m}

\frac{[|a|_{m}, |b|_{m}]}{(|a|_{m}, |b|_{m})} | |ab|_{m} | [|a|_{m}, |b|_{m}]

a^{|b|_{m}} ≡ b^{|a|_{m}} (mod m) ⇒ |a|_{m} = |b|_{m}

Proof We first prove the second property.

(ab)^{[|a|_{m},|b|_{m}]} ≡ e (mod m) ⇒ |ab|_{m} | [|a|_{m}, |b|_{m}]

e ≡ (ab)^{|a|_{m}·|ab|_{m}} ≡ e · b^{|a|_{m}·|ab|_{m}} ≡ b^{|a|_{m}·|ab|_{m}} (mod m) ⇒

⇒ |b|_{m} | |a|_{m} · |ab|_{m} ⇒ \frac{|b|_{m}}{(|a|_{m}, |b|_{m})} | |ab|_{m}

e ≡ (ab)^{|b|_{m}·|ab|_{m}} ≡ e · a^{|b|_{m}·|ab|_{m}} ≡ a^{|b|_{m}·|ab|_{m}} (mod m) ⇒

⇒ |a|_{m} | |b|_{m} · |ab|_{m} ⇒ \frac{|a|_{m}}{(|a|_{m}, |b|_{m})} | |ab|_{m}

⇒ [\frac{|a|_{m}}{(|a|_{m}, |b|_{m})}, \frac{|b|_{m}}{(|a|_{m}, |b|_{m})}] = \frac{[|a|_{m}, |b|_{m}]}{(|a|_{m}, |b|_{m})} | |ab|_{m}

The first property follows from the second one. Now, we prove the third one.

e ≡ a^{|b|_{m} \frac{|a|m}{(|a|m,|b|m)}} ≡ b^{\frac{|a|^{2}_{m}}{(|a|m,|b|m)}} (mod m) ⇒

⇒ |b|_{m} | |a|_{m} \frac{|a|_{m}}{(|a|_{m}, |b|_{m})} ⇔ \frac{|b|_{m}}{(|a|_{m}, |b|_{m})} | \frac{|a|_{m}}{(|a|_{m}, |b|_{m})} ⇒ |b|_{m} | |a|_{m}

We get |a|_{m} | |b|_{m} the same way. □

Theorem 5.20 Suppose that e ∈ E_{m}, a, b, c ∈ R_{m}^{e} and a ∈ ⟨b⟩_{m} ∩ ⟨c⟩_{m}. Then there exists some d ∈ R_{m}^{e} for which a ∈ ⟨d⟩_{m} and |d|_{m} = [|b|_{m}, |c|_{m}].

Proof By Theorem 5.17, we have

⟨b⟩_{m} ∩ ⟨c⟩_{m} = ⟨b^{D_{m}(b,c)}⟩_{m} = ⟨c^{D_{m}(c,b)}⟩_{m}

so there exists some K ∈ ℕ such that

(b^{D_{m}(b,c)})^{K} ≡ c^{D_{m}(c,b)} (mod m)

and from

|b^{D_{m}(b,c)}|_{m} = |⟨b⟩_{m} ∩ ⟨c⟩_{m}| = |c^{D_{m}(c,b)}|_{m} = \frac{|b^{D_{m}(b,c)}|_{m}}{(K, |b^{D_{m}(b,c)}|_{m})}

we have (K, |b^{D_{m}(b,c)}|_{m}) = 1.

\frac{|b|_{m}}{D_{m}(b, c)} = \frac{|c|_{m}}{D_{m}(c, b)} ⇒ D_{m}(c, b)\frac{|b|_{m}}{(|b|_{m}, |c|_{m})} = D_{m}(b, c)\frac{|c|_{m}}{(|b|_{m}, |c|_{m})}

⇒ \frac{|b|_{m}}{(|b|_{m}, |c|_{m})} | D_{m}(b, c)\frac{|c|_{m}}{(|b|_{m}, |c|_{m})}

and since

(\frac{|b|_{m}}{(|b|_{m}, |c|_{m})}, \frac{|c|_{m}}{(|b|_{m}, |c|_{m})}) = 1

we have

\frac{|b|_{m}}{(|b|_{m}, |c|_{m})} | D_{m}(b, c)

Denote

l := \frac{D_{m}(b, c)(|b|_{m}, |c|_{m})}{|b|_{m}}

|b|_{m} = n_{1}n_{2}n_{3}, |c|_{m} = k_{1}k_{2}k_{3}, l = l_{1}l_{2}

where the numbers above have the properties

k_{1} | n_{1}, n_{2} | k_{2}, l_{1} | n_{2}, l_{2} | k_{1}
1 = (n_{3}, k_{3}) = (n_{i}, n_{j}) = (n_{i}, k_{j}) = (k_{i}, k_{j}) (i ≠ j)

Then we have

(|b|_{m}, |c|_{m}) = n_{2}k_{1}, |b^{n_{2}}|_{m} = n_{1}n_{3}, |c^{k_{1}}|_{m} = k_{2}k_{3}, (|b^{n_{2}}|_{m}, |c^{k_{1}}|_{m}) = 1 and also

D_{m}(b, c) = l\frac{n_{1}}{k_{1}} n_{3}, D_{m}(c, b) = l\frac{k_{2}}{n_{2}} k_{3}, |b^{D_{m}(b,c)}|_{m} = \frac{n_{2}k_{1}}{l}

So by Theorem 5.19

|b^{n_{2}}c^{k_{1}}|_{m} = n_{1}n_{3}k_{2}k_{3} = [|b|_{m}, |c|_{m}]

Denote d := b^{n_{2}}c^{k_{1}} mod m.

d^{l \frac{n_{1}k_{2}}{k_{1}n_{2}} n_{3}k_{3}} ≡ (b^{D_{m}(b,c)})^{k_{2}k_{3}}(c^{D_{m}(c,b)})^{n_{1}n_{3}} ≡ (b^{D_{m}(b,c)})^{k_{2}k_{3}+Kn_{1}n_{3}} (mod m)

(k_{2}k_{3} + Kn_{1}n_{3}, \frac{n_{2}k_{1}}{l_{1}l_{2}} ) = 1

since \frac{n_{2}}{l_{1}} | k_{2} but (\frac{n_{2}}{l_{1}} , Kn_{1}n_{3}) = 1, and \frac{k_{1}}{l_{2}} | n_{1} but (\frac{k_{1}}{l_{2}} , k_{2}k_{3}) = 1. So there exists some N ∈ ℕ, such that

(k_{2}k_{3} + Kn_{1}n_{3})N ≡ 1 (mod \frac{n_{2}k_{1}}{l})

So since (b^{D_{m}(b,c)})^{I} ≡ a (mod m) for some I ∈ ℕ, we have

d^{l \frac{n_{1}k_{2}}{k_{1}n_{2}} n_{3}k_{3}NI} ≡ (b^{D_{m}(b,c)})^{(k_{2}k_{3}+Kn_{1}n_{3})NI} ≡ (b^{D_{m}(b,c)})^{I} ≡ a (mod m)

So a ∈ ⟨d⟩_{m}. □

Theorem 5.21 Let e ∈ E_{m}, a ∈ R_{m}^{e}, b ∈ N_{m} be such that a ∈ ⟨b⟩_{m}. Then there exists some c ∈ R_{m}^{e} such that a ∈ ⟨c⟩_{m} and |c|_{m} = |b|_{m}.

Proof Define c := be mod m. Then obviously c ∈ R_{m}^{e}, and

c^{ind_{b}^{m}a} ≡ b^{ind_{b}^{m}a} · e ≡ a · e ≡ a (mod m)

So a ∈ ⟨c⟩_{m}. Since b^{|b|_{m}} ≡ e (mod m), we have c ≡ b^{|b|_{m}+1} (mod m), so since b ∈ N_{m}, we have

|c|_{m} = \frac{|b|_{m}}{(|b|_{m} + 1, |b|_{m})} = |b|_{m}

□

Theorem 5.22 Let a ∈ R_{m}, b ∈ N_{m} be such that |a|_{m} | |b|_{m}. Then the following inference holds

∃ind_{a}^{m} b^{n} ⇒ ∃ind_{b}^{m} a^{n} (n ∈ ℕ)

Proof Let n ∈ ℕ be such that b^{n} ∈_{m} ⟨a⟩_{m}. Then ∃k ∈ ℕ : b^{n} ≡ a^{k} (mod m). From this we have

|b^{n}|_{m} = |a^{k}|_{m} ⇒ (k, |a|_{m})\frac{|b|_{m}}{|a|_{m}} = (n, |b|_{m}) ⇒ (k, |a|_{m}) | n

So ∃l ∈ ℕ : kl ≡ n (mod |a|_{m}), which implies a^{n} ≡ a^{kl} ≡ b^{nl} (mod m). □

It is easy to find numbers m ∈ ℕ, a, b ∈ N_{m} for which the theorem above does not hold.

Theorem 5.23 Let a, b ∈ R_{m} be such that |a|_{m} = |b|_{m}. Then the following equivalence holds

b^{n} ∈_{m} ⟨a⟩_{m} ⇔ a^{n} ∈_{m} ⟨b⟩_{m} (n ∈ ℕ)

Proof Follows easily from Theorem 5.22. □

Definition 5.5 For a, b ∈ R_{m} we will say that a and b are equivalent modulo m if the following are true

a^{|a|_{m}} ≡ b^{|b|_{m}} (mod m) and |a|_{m} = |b|_{m} and ∃ind_{b}^{m}a

and we shall denote it as a ∼_{m} b.

Theorem 5.24 The relation ∼_{m} truly is an equivalence relation.

Proof It is clear that a ∼_{m} a for all a ∈ R_{m}. By the previous theorem, we have that for all a, b ∈ R_{m}

a ∼_{m} b ⇔ |a|_{m} = |b|_{m}, ∃ind_{b}^{m}a ⇔ |a|_{m} = |b|_{m}, ∃ind_{a}^{m}b ⇔ b ∼_{m} a

Now, to show the transitivity of our relation, we take any a, b, c ∈ R_{m}

a ∼_{m} b, b ∼_{m} c ⇒ |a|_{m} = |b|_{m} = |c|_{m}, ∃n, k : b^{n} ≡ a, c^{k} ≡ b (mod m) ⇒
⇒ |a|_{m} = |c|_{m}, c^{nk} ≡ a (mod m) ⇒ a ∼_{m} c

□

Theorem 5.25 Let a, b ∈ R_{m}, n ∈ ℕ be such that b^{n} ∈_{m} ⟨a⟩_{m}, (n, |b|_{m}) = 1. Then ⟨b⟩_{m} ⊂ ⟨a⟩_{m}.

Proof Let k ∈ ℕ be such that b^{n} ≡ a^{k} (mod m). Let l be any integer. Then ∃s ∈ ℕ : ns ≡ l (mod |b|_{m}). From this we have b^{l} ≡ a^{ks} (mod m), which implies b^{l} ∈_{m} ⟨a⟩_{m}. □

Theorem 5.26 Let a, b ∈ R_{m}, n ∈ ℕ be such that a^{n} ∈_{m} ⟨b⟩_{m} and |b|_{m} | |a|_{m}, (n, |b|_{m}) = 1. Then ⟨b⟩_{m} ⊂ ⟨a⟩_{m}.

Proof By Theorem 5.22 we have that b^{n} ∈_{m} ⟨a⟩_{m}, so we have ⟨b⟩_{m} ⊂ ⟨a⟩_{m} by Theorem 5.25. □

Theorem 5.27 For a, b ∈ R_{m}, we have ⟨a⟩_{m} = ⟨b⟩_{m} iff |a|_{m} = |b|_{m} and there exists some n ∈ ℕ such that (n, |a|_{m}) = 1 and a^{n} ∈_{m} ⟨b⟩_{m}.

Proof First, let us suppose that ⟨a⟩_{m} = ⟨b⟩_{m}. Then

|a|_{m} = |⟨a⟩_{m}| = |⟨b⟩_{m}| = |b|_{m}

Also, for any n ∈ ℕ, (n, |a|_{m}) = 1, we have a^{n} ∈_{m} ⟨a⟩_{m} = ⟨b⟩_{m}. Now, let us suppose that |a|_{m} = |b|_{m} and there exists some n ∈ ℕ such that (n, |a|_{m}) = 1 and a^{n} ∈_{m} ⟨b⟩_{m}. Then by Theorem 5.25, we have that ⟨a⟩_{m} ⊂ ⟨b⟩_{m}. By Theorem 5.23, we have that b^{n} ∈_{m} ⟨a⟩_{m}, so by applying Theorem 5.25 once again, we get ⟨b⟩_{m} ⊂ ⟨a⟩_{m} as well. □

Theorem 5.28 Let a, b ∈ R_{m} be such that |a|_{m} | |b|_{m}. Then there exists some c ∈ R_{m} such that a, b ∈ ⟨c⟩_{m}, iff a ∈ ⟨b⟩_{m}.

Proof Let us suppose that a, b ∈ ⟨c⟩_{m} for some c ∈ R_{m}. Then

(ind_{c}^{m}b, |c|_{m}) = \frac{|c|_{m}}{|b|_{m}} | \frac{|c|_{m}}{|a|_{m}} = (ind_{c}^{m}a, |c|_{m}) | ind_{c}^{m}a

So there exists some k ∈ ℕ such that (ind_{c}^{m}b)k ≡ ind_{c}^{m}a (mod |c|_{m}). So b^{k} ≡ a (mod m). Now, if a ∈ ⟨b⟩_{m}, then with c := b, we have that a, b ∈ ⟨c⟩_{m}. □

Theorem 5.29 Let e ∈ E_{m}, a, b ∈ R_{m}^{e} be such that (|a|_{m}, |b|_{m}) = 1. Then ⟨a⟩_{m} ∩⟨b⟩_{m} = {e}.

Proof Let us take c ∈ ⟨a⟩_{m} ∩ ⟨b⟩_{m}. Then there exists some n ∈ ℕ such that n|b|_{m} ≡ ind_{a}^{m}c (mod |a|_{m}). So we have

a^{n|b|_{m}^{2}} ≡ a^{|b|_{m}ind_{a}^{m}c} ≡ c^{|b|_{m}} ≡ (b^{|b|_{m}})^{ind_{b}^{m}c} ≡ e (mod m) ⇒ |a|_{m} | n|b|_{m}^{2} ⇒
⇒ |a|_{m} | n ⇒ ind_{a}^{m}c ≡ n|b|_{m} ≡ 0 (mod |a|_{m}) ⇒ c ≡ a^{ind_{a}^{m}c} ≡ e (mod m)

□

Theorem 5.30 For b ∈ R_{m}, a ∈ ⟨b⟩_{m}, d | |b|_{m} the following equivalence holds

|a|_{m} = d ⇔ ind_{b}^{m}a = \frac{r|b|_{m}}{d} , (r, d) = 1

Proof First, let us suppose that |a|_{m} = d. Then

d = |a|_{m} = \frac{|b|_{m}}{(ind_{b}^{m}a, |b|_{m})} ⇒ ind_{b}^{m}a = \frac{r|b|_{m}}{d} , r := \frac{ind_{b}^{m}a}{(ind_{b}^{m}a, |b|_{m})}

where we see that (r, |a|_{m}) = 1. Now, let r, d, b ∈ ℕ be any numbers such that (r, d) = 1, d | b. Then

\frac{b}{(\frac{rb}{d}, b)} = d

Considering the relation between prime-factorizations and the greatest common divisor, we need to show that for all r, d, b ≥ 0, min(r, d) = 0, d ≤ b, we have b−min(r+b−d, b) = d. Supposing that r ≤ d, we get r = 0, from which the desired relation is b − (b − d) = d. Now, if d ≤ r, then d = 0, so the relation we need is b − b = 0. Applying the relation above, we get that

|a|_{m} = \frac{|b|_{m}}{(\frac{r|b|_{m}}{d} , |b|_{m})} = d

□

Theorem 5.31 For a ∈ R_{m}, d | |a|_{m}

|{b ∈ ⟨a⟩_{m} : |b|_{m} = d}| = φ(d)

and

|{b ∈ R_{m} : b ∼_{m} a}| = φ(|a|_{m})

Proof The first equality follows from the above theorem. The second one follows from the first with d = |a|_{m}. □

We now examine further properties of the function D_{m}(a, b).

Definition 5.6 For e ∈ E_{m}, a, b ∈ R_{m}^{e}, let the relative order of the numbers a and b be defined as

|a, b|_{m} := |⟨a⟩_{m} ∩ ⟨b⟩_{m}| = \frac{|a|_{m}}{D_{m}(a, b)} = \frac{|b|_{m}}{D_{m}(b, a)}

Theorem 5.32 For e ∈ E_{m}, a, b ∈ R_{m}^{e}, n ∈ ℕ

D_{m}(a, b) = D_{m}(b, a) ⇔ |a|_{m} = |b|_{m}

\frac{D_{m}(a, b)}{D_{m}(b, a)} = \frac{|a|_{m}}{|b|_{m}}

D_{m}(a, b) = |a^{|a^{Dm(a,b)}|_{m}} |_{m}

D_{m}(a^{n}, b) = \frac{D_{m}(a, b)}{(n, D_{m}(a, b))}

(|a, b|_{m}, D_{m}(b, a)) = 1 ⇒ D_{m}(a, b^{n}) = D_{m}(a, b) (n, \frac{|a|_{m}}{D_{m}(a, b)})

Proof The first, second, and third relations follow trivially from Theorem 5.17. To prove the fourth relation, for any k ∈ ℕ we see that

D_{m}(a^{n}, b) | k ⇔ a^{nk} ∈_{m} ⟨b⟩_{m} ⇔ D_{m}(a, b) | nk ⇔ \frac{D_{m}(a, b)}{(n, D_{m}(a, b))} | k

To prove the fifth relation,

D_{m}(a, b^{n}) = \frac{|a|_{m}}{|b^{n}|_{m}} D_{m}(b^{n}, a) = \frac{|a|_{m}}{|b|_{m}} (n, |b|_{m})\frac{D_{m}(b, a)}{(n, D_{m}(b, a))} =

= D_{m}(a, b)\frac{(n, |b|_{m})}{(n, D_{m}(b, a))} = D_{m}(a, b) (n, \frac{|b|_{m}}{D_{m}(b, a)}) =

= D_{m}(a, b) (n, \frac{|a|_{m}}{D_{m}(a, b)})

□

Theorem 5.33 For e ∈ E_{m}, a, b ∈ R_{m}^{e}, n, k ∈ ℕ

|a, b|_{m} = |b, a|_{m}
|a, a|_{m} = |a|_{m}
(|a|_{m}, |b|_{m}) = 1 ⇒ |a, b|_{m} = 1

b ∈ ⟨a⟩_{m} ⇒ |a, b|_{m} = |b|_{m}

(|a, b|_{m}, D_{m}(a, b)) = 1 ⇒ |a^{n}, b|_{m} = \frac{|a, b|_{m}}{(n, |a, b|_{m})}

(|a, b|_{m}, D_{m}(a, b^{k})D_{m}(b, a)) = 1 ⇒ |a^{n}, b^{k}|_{m} = \frac{|a, b|_{m}}{(n(k, |a, b|_{m}), |a, b|_{m})}

Proof The first and second relations are trivial. The first inference follows from Theorem 5.29, and the second is trivial. Now, to prove the fifth relation,

|a^{n}, b|_{m} = \frac{|b|_{m}}{D_{m}(b, a^{n})} = \frac{|b|_{m}}{D_{m}(b, a) (n, \frac{|b|_{m}}{D_{m}(b,a)})} = \frac{|a, b|_{m}}{(n, |a, b|_{m})}

Lastly, since

(|a, b|_{m}, D_{m}(a, b^{k})) = 1 ⇒ (|a, b^{k}|_{m}, D_{m}(a, b^{k})) = 1

we have

|a^{n}, b^{k}|_{m} = \frac{|a, b^{k}|_{m}}{(n, |a, b^{k}|_{m})} = \frac{|b, a|_{m}}{(k, |b, a|_{m}) (n, \frac{|b,a|_{m}}{(k,|b,a|_{m})})} =

= \frac{|a, b|_{m}}{(n(k, |a, b|_{m}), |a, b|_{m})}

□

6 Binomial Congruences

Definition 6.1 For a ∈ ℤ, k ∈ ℕ let M_{m}(k, a) denote the logical function which gives "true" if the equation in x

x^{k} ≡ a (mod m)

is solvable, otherwise let its value be "false". Furthermore, let S_{m}(k, a) denote the set of solutions in ℤ_{m} of the equation above, and let S_{m}^{R}(k, a) denote the set of regular solutions in ℤ_{m}. In case of a ∈ R_{m}, let ω_{m}(a) denote the number

max {|b|_{m} : b ∈ R_{m}, ∃ind_{b}^{m}a}

furthermore let ind^{m}a := \frac{ω_{m}(a)}{|a|_{m}}.

Note that ω_{m}(a) = φ(m) for some a ∈ R_{m}, iff R_{m}^{1} is cyclical.

Theorem 6.1 For a ∈ R_{m}, k ∈ ℕ

M_{m}(k, a) ⇔ a^{\frac{ωm(a)}{(k,ωm(a))}} ∈_{m} E_{m}

Proof Let b ∈ R_{m} be such that ∃ind_{b}^{m}a and |b|_{m} = ω_{m}(a). Then we have

a^{\frac{ωm(a)}{(k,ωm(a))}} ∈_{m} E_{m} ⇔ (k, |b|_{m}) | ind_{b}^{m}a

If (k, |b|_{m}) | ind_{b}^{m}a holds, then there must exist some 1 ≤ l ≤ |b|_{m} for which kl ≡ ind_{b}^{m}a (mod |b|_{m}). So we have

b^{kl} ≡ b^{ind_{b}^{m}a} (mod m) ⇒ (b^{l})^{k} ≡ a (mod m)

so b^{l} is a solution of the equation. Now, let x_{0} be a solution of the equation, and denote e := a^{φ(m)} mod m, c := x_{0}e mod m. Then we have that c is a solution as well, since

c^{k} ≡ (x_{0})^{k}e ≡ a · a^{|a|_{m}} ≡ a (mod m)

and c ∈ R_{m} since

c · c^{|c|_{m}} ≡ c · c^{φ(m)} ≡ x_{0}e(x_{0}^{k})^{φ(m)} ≡ x_{0}e ≡ c (mod m)

It is also clear that |c|_{m} | |b|_{m}. For, let us make the indirect assumption that |c|_{m} ∤ |b|_{m}. Then we have |c|_{m} < |b|_{m} by the definition of ω_{m}(a). We also know by Theorem 5.20 that there exists some d ∈ R_{m}, such that ∃ind_{d}^{m}a and |d|_{m} = [|b|_{m}, |c|_{m}]. It is clear that |d|_{m} > |b|_{m}, which obviously contradicts the selection of b and the definition of ω_{m}(a). So we must have that |c|_{m} | |b|_{m}. From this, we have

a^{\frac{ωm(a)}{(k,ωm(a))}} ≡ a^{\frac{|b|m}{(k,|b|m)}} ≡ (c^{k})^{\frac{|b|m}{(k,|b|m)}} ≡ (c^{|c|_{m}})^{\frac{|b|m}{|c|m} · \frac{k}{(k,|b|m)}} ≡ e (mod m) □

The difficulty of the verification of the condition

a^{\frac{ωm(a)}{(k,ωm(a))}} ∈_{m} E_{m}

lies within the calculation of ω_{m}(a). So I believe that the examination of the mapping m ↦ ω_{m}(a) is probably the most logical direction, research on this subject should take. Let us look at some immediate corollaries of our theorem.

Theorem 6.2 For a ∈ R_{m}, k ∈ ℕ

M_{m}(k, a) ⇔ M_{m}((k, φ(m)), a) ⇔ M_{m}((k, ψ(m)), a)

Proof The equivalence follows trivially from our previous theorem, since

ω_{m}(a) | φ(m), ψ(m) ⇒ (k, ω_{m}(a)) = ((k, φ(m)), ω_{m}(a)) = ((k, ψ(m)), ω_{m}(a))

□

Theorem 6.3 For a ∈ R_{m}, k_{1}, k_{2} ∈ ℕ

M_{m}(k_{1}, a) and M_{m}(k_{2}, a) ⇔ M_{m}([k_{1}, k_{2}], a)

Proof Our theorem follows from Theorem 5.16, and the fact that

(\frac{ω_{m}(a)}{(k_{1}, ω_{m}(a))}, \frac{ω_{m}(a)}{(k_{2}, ω_{m}(a))}) = \frac{ω_{m}(a)}{([k_{1}, k_{2}], ω_{m}(a))}

□

We now look at a necessary and then a sufficient condition for the solvability of a binomial congruence modulo m.

Theorem 6.4 For a ∈ ℤ_{m}, k ∈ ℕ

M_{m}(k, a) ⇒ a^{\frac{φ(m)}{(k,φ(m))}} ∈_{m} E_{m}

Proof Let the solution of the binomial congruence, be denoted by x_{0}. Then

a^{\frac{φ(m)}{(k,φ(m))}} ≡ (x_{0}^{k})^{\frac{φ(m)}{(k,φ(m))}} ≡ (x_{0}^{φ(m)})^{\frac{k}{(k,φ(m))}} ∈_{m} E_{m}

□

Theorem 6.5 Let a, b ∈ R_{m}, k ∈ ℕ be such that ∃ind_{b}^{m}a and (k, |b|_{m}) | ind_{b}^{m}a. Then M_{m}(k, a).

Proof If the conditions above are satisfied, then for some l ∈ ℤ_{|b|_{m}}, we have kl ≡ ind_{b}^{m}a (mod |b|_{m}). So since b ∈ R_{m}, we have

b^{kl} ≡ b^{ind_{b}^{m}a} (mod m) ⇒ b^{l} ∈_{m} S_{m}(k, a) ⇒ M_{m}(k, a)

□

We now look at some special solutions of a binomial congruence.

Theorem 6.6 Let a, b ∈ R_{m}, e ∈ E_{|b|_{m}}, k, l ∈ ℕ, kl ∈ R_{|b|_{m}}^{e} be such that ∃ind_{b}^{m}a ∈ R_{|b|_{m}}^{e}, kl ≡ e (mod |b|_{m}) and M_{m}(k, a). Then

b^{lind_{b}^{m}a+n \frac{|b|m}{(k,|b|m)}} ∈_{m} S_{m}(k, a) (n ∈ ℕ)

Proof

k(lind_{b}^{m}a + n\frac{|b|_{m}}{(k, |b|_{m})}) ≡ ind_{b}^{m}a + n\frac{k}{(k, |b|_{m})}|b|_{m} ≡ ind_{b}^{m}a (mod |b|_{m}) ⇒

⇒ (b^{lind_{b}^{m}a+n \frac{|b|m}{(k,|b|m)}} )^{k} ≡ b^{ind_{b}^{m}a} ≡ a (mod m)

□

Next, we examine the number of solutions of a binomial congruence.

Theorem 6.7 If a ∈ R_{m}, k ∈ ℕ and M_{m}(k, a), then |S_{m}^{R}(k, a)| > 0.

Proof It is clear that x_{0} ·e ∈_{m} S_{m}^{R}(k, a) for any x_{0} ∈ S_{m}(k, a), where a^{|a|_{m}} ≡ e (mod m). □

Theorem 6.8 If e ∈ E_{m}, a ∈ R_{m}^{e}, k ∈ ℕ and M_{m}(k, a), then |S_{m}^{R}(k, a)| = |S_{m}^{R}(k, e)|.

Proof Let x_{0} ∈ S_{m}^{R}(k, a) be some regular solution. Then according to Theorem 5.13, we have exactly one x_{0}^{−1} ∈ R_{m}^{e} such that x_{0}^{−1}x_{0} ≡ e (mod m). Let us define the set

A := {x_{0}^{−1}x_{i} : x_{i} ∈ S_{m}^{R}(k, a)}

Then we have that A ⊂ S_{m}^{R}(k, e), since for any x_{i} ∈ S_{m}^{R}(k, a)

(x_{0}^{−1}x_{i})^{k} ≡ (x_{0}^{−1})^{k}x_{i}^{k} ≡ (x_{0}^{−1})^{k}x_{0}^{k} ≡ e (mod m)

and for i ≠ j we have x_{0}^{−1}x_{i} ≢ x_{0}^{−1}x_{j} (mod m), for let suppose that for some i ≠ j

x_{0}^{−1}x_{i} ≡ x_{0}^{−1}x_{j} ⇒ x_{i} ≡ x_{i}x_{0}^{−1}x_{0} ≡ x_{j}x_{0}^{−1}x_{0} ≡ x_{j} (mod m)

which is a contradiction. So we have that |S_{m}^{R}(k, a)| = |A| ≤ |S_{m}^{R}(k, e)|. We also have that

S_{m}^{R}(k, a) = x_{0} · S_{m}^{R}(k, e) mod m ⊂ S_{m}^{R}(k, a)

so |S_{m}^{R}(k, e)| ≤ |S_{m}^{R}(k, a)|. □

7 Generalized Primitive Roots

Definition 7.1 A number g ∈ R_{m} is said to be a generalized primitive root modulo m, if ω_{m}(g) = |g|_{m}. Let the set of such g be denoted by G_{m}. Furthermore, let Ω_{m}(a) denote the set

{b ∈ R_{m} : ∃ind_{b}^{m}a and |b|_{m} = ω_{m}(a)}

Theorem 7.1 For all a ∈ R_{m}

Ω_{m}(a) ⊂ G_{m}

Furthermore, for all g ∈ G_{m} there exists some a ∈ R_{m} such that g ∈ Ω_{m}(a).

Proof To prove the first part of our theorem, take any b ∈ Ω_{m}(a), and let us suppose indirectly that b ∉ G_{m}. Then there exists some c ∈ R_{m}, such that ∃ind_{c}^{m}b and |c|_{m} > |b|_{m}. Obviously ∃ind_{c}^{m}a, since

(c^{ind_{c}^{m}b})^{ind_{b}^{m}a} ≡ b^{ind_{b}^{m}a} ≡ a (mod m)

Which contradicts the maximality of |b|_{m} = ω_{m}(a). Now, to prove the second part, take any g ∈ G_{m}. It is trivial, that g ∈ Ω_{m}(g). □

Note that our theorem implies the nonemptyness of G_{m}.

Theorem 7.2 For a ∈ R_{m}, g ∈ Ω_{m}(a) the following equivalence holds

g^{n} ∈_{m} Ω_{m}(a) ⇔ (n, |g|_{m}) = 1 (n ∈ ℕ)

Proof To prove the ⇒ part of the equivalence

|g|_{m} = ω_{m}(a) = |g^{n}|_{m} = \frac{|g|_{m}}{(n, |g|_{m})} ⇒ (n, |g|_{m}) = 1

Now, if we suppose that (n, |g|_{m}) = 1, then there exists some k ∈ ℕ such that nk ≡ ind_{g}^{m}a (mod |g|_{m}). So

(g^{n})^{k} ≡ g^{ind_{g}^{m}a} ≡ a (mod m) ⇒ ∃ind_{g^{n}}^{m}a

and

|g^{n}|_{m} = \frac{|g|_{m}}{(n, |g|_{m})} = |g|_{m} = ω_{m}(a)

So g^{n} ∈_{m} Ω_{m}(a). □

Theorem 7.3 For a ∈ R_{m} the following equivalence holds

g ∈ Ω_{m}(a) ⇔ g^{−1} ∈ Ω_{m}(a)

Proof Follows from our previous theorem. □

Theorem 7.4 Let m_{1}, m_{2} ∈ ℕ be such that m = [m_{1}, m_{2}], and g ∈ ℤ_{m}. If g ∈_{m_{1}} G_{m_{1}} and g ∈_{m_{2}} G_{m_{2}}, then g ∈_{m} G_{m}.

Proof Let us suppose indirectly, that g ∉ G_{m}. This means that there exists some h ∈ R_{m} and n ∈ ℕ, such that |h|_{m} > |g|_{m}, and h^{n} ≡ g (mod m). This implies that (n, |h|_{m}) > 1, and for i ∈ {1, 2}

h^{n} ≡ g (mod m_{i}) ⇒ |g|_{m_{i}} = \frac{|h|_{m_{i}}}{(n, |h|_{m_{i}})} ⇒ (n, |h|_{m_{i}}) = 1

So combining the two we get

1 = [(n, |h|_{m_{1}}), (n, |h|_{m_{2}})] = (n, [|h|_{m_{1}}, |h|_{m_{2}}]) = (n, |h|_{m})

which is a contradiction. □

Our theorem above sheds some light on the still hazy structure of G_{m}.

Theorem 7.5 If a, b ∈ R_{m}, a ∼_{m} b, then ω_{m}(a) = ω_{m}(b).

Proof It is clear, that (ind_{b}^{m}a, |b|_{m}) = 1. So for any g ∈ Ω_{m}(b)

(g^{ind_{g}^{m}b})^{ind_{b}^{m}a} ≡ a (mod m)

so ∃ind_{g}^{m}a. So

ω_{m}(b) = |g|_{m} ≤ ω_{m}(a)

The inequality ω_{m}(a) ≤ ω_{m}(b) may be proven in the same way. □

The theorem above shows, that in our quest of finding an easy method for the calculation of the function ω_{m}, it would be worth examining the equivalence classes according to the relation ∼_{m}. It also implies that if a number is equivalent to a gen. primitive root, then it is a gen. primitive root as well. Therefore, it would also be worth examining the structure of G_{m} and Ω_{m}(a), partitioned according to our equivalence relation.

8 Number Theoretic Functions

In this section, we shall examine some functions, along with some of their properties, emerging from the discussions above.

Definition 8.1 A number theoretic function f : ℕ → ℕ is said to be multiplicative, if for all a, b ∈ D(f), (a, b) = 1

a · b ∈ D(f) and f(a · b) = f(a) · f(b)

and we shall denote it as f ∈ M. We will say that f is quasimultiplicative, if for all a, b ∈ D(f)

[a, b] ∈ D(f) and f([a, b]) = [f(a), f(b)]

and we shall denote it as f ∈ QM. We will say that f is division-invariant, if the following inference holds for all a, b ∈ D(f)

a | b ⇒ f(a) | f(b)

and we shall denote it as f ∈ DI. Lastly, we will say that f is prime-power division-invariant, if for all primes q and β, γ ∈ ℕ, β ≤ γ, such that q^{β}, q^{γ} ∈ D(f), we have f(q^{β}) | f(q^{γ}); and we shall denote it as f ∈ DI_{p^{α}}.

Note that the functions ψ (by our theorem below), m ↦ |a|_{m} (with domain {m ∈ ℕ : a ∈_{m} N_{m}}), a ↦ (a, b) are quasimultiplicative. We suspect, that for most (if not all) quasimultiplicative functions, there exists some quick algorithm for their computation. The basis of this conjecture is that the well-known Euclidean Algorithm computes the function a ↦ (a, b) ∈ QM. Furthermore, it is also possible, that the computation of most multiplicative functions relies heavily on prime-factorization; that is, their computation is mostly equivalent to prime-factorization, in terms of speed.

Theorem 8.1 For any g ∈ DI_{p^{α}}, D(g) = ℕ and n ∈ ℕ, with prime-factorization n = ∏_{i∈ℕ} p_{i}^{γ_{i}}, define the function f as

f(n) = lcm(g(p_{i}^{γ_{i}}) : i ∈ ℕ)

Then f ∈ QM.

Proof Take a, b ∈ D(f), with prime-factorizations a = ∏_{i∈ℕ} p_{i}^{γ_{i}}, b = ∏_{i∈ℕ} p_{i}^{δ_{i}}. Then

f([a, b]) = lcm(g(p_{i}^{max(γ_{i},δ_{i})}) : i ∈ ℕ) =
= lcm([g(p_{i}^{min(γ_{i},δ_{i})}), g(p_{i}^{max(γ_{i},δ_{i})})] : i ∈ ℕ) =
= [lcm(g(p_{i}^{γ_{i}}) : i ∈ ℕ), lcm(g(p_{i}^{δ_{i}}) : i ∈ ℕ)] = [f(a), f(b)]

□

It is interesting to ponder the question whether there would exist such a g for all f ∈ QM.

Theorem 8.2

f ∈ QM ⇔ f ∈ DI and (a, b ∈ D(f), (a, b) = 1 ⇒ f(ab) = [f(a), f(b)]) Proof First, let us suppose that f ∈ QM, and take a, b ∈ D(f) such that a | b. Then

f(b) = f([a, b]) = [f(a), f(b)] ⇒ f(a) | f(b)

Now, suppose that the right hand side of the equivalence holds. Let a, b ∈ D(f) and n_{i}, k_{i} ∈ ℕ (i = 1, 2, 3) be such that

a = n_{1}n_{2}n_{3}, b = k_{1}k_{2}k_{3}, n_{1} | k_{1}, k_{2} | n_{2}

1 = (n_{i}, n_{j}) = (k_{i}, k_{j}) = (n_{i}, k_{j}) = (n_{3}, k_{3}) (i ≠ j)

Such decompositions exist, and are easy to find, by looking at the prime factorizations of a and b. So we have [a, b] = k_{1}n_{2}n_{3}k_{3}, and

f([a, b]) = [f(k_{1}), f(n_{2}), f(n_{3}), f(k_{3})] = [[f(n_{1}), f(k_{1})], [f(k_{2}), f(n_{2})], f(n_{3}), f(k_{3})] =

= [[f(n_{1}), f(n_{2}), f(n_{3})], [f(k_{1}), f(k_{2}), f(k_{3})]] = [f(a), f(b)]

□ Theorem 8.3

f ∈ DI ⇔ ∀a, b ∈ D(f) : [f(a), f(b)] | f([a, b])

Proof First, let us suppose that f ∈ DI. For any a, b ∈ D(f)

a, b | [a, b] ⇒ f(a), f(b) | f([a, b]) ⇒ [f(a), f(b)] | f([a, b])

Now, suppose that the right hand side property is what holds for f. Then for any a, b ∈ D(f) a | b ⇒ f([a, b]) = f(b) ⇒ [f(a), f(b)] | f(b) ⇒ [f(a), f(b)] = f(b) ⇒ f(a) | f(b) □ Theorem 8.4 If f ∈ QM is injective, then the following equivalence holds

a | b ⇔ f(a) | f(b) (a, b ∈ D(f))

Proof If f ∈ QM, then by Theorem 8.2, we have the ⇒ part of the equivalence. Now, suppose that a, b ∈ D(f) and f(a) | f(b). Then

f(b) = [f(a), f(b)] = f([a, b]) ⇒ b = [a, b] ⇒ a | b

□ Definition 8.2 For e ∈ E_{m}, k ∈ ℕ, let us define the following sets

kR_{m} := {a ∈ R_{m} : |a|_{m} = k}, _{k}R_{m}^{e} := _{k}R_{m} ∩ R_{m}^{e} Now, define

r_{m}^{e}(k) := |_{k}R_{m}^{e}| (k ∈ ℕ)

Furthermore, let

ρ_{m}^{e}(k) := |{a ∈ R_{m}^{e} : |a|_{m} | k}| (k ∈ ℕ)

Note that by Theorem 6.8 we have that

|S_{m}^{R}(k, a)| = |S_{m}^{R}(k, e)| = ρ_{m}^{e}(k)

if k ∈ ℕ, e ∈ E_{m}, a ∈ R_{m}^{e} and M_{m}(k, a).

Theorem 8.5 For all e ∈ E_{m}

r_{m}^{e}(k) = r_{μ_{m}(e)}^{1}(k), ρ_{m}^{e}(k) = ρ_{μ_{m}(e)}^{1}(k) (k ∈ ℕ)

Furthermore, if m is weakly even, then r_{m}^{e}, ρ_{m}^{e} ∈ M.

Proof By the application of Theorem 5.11, we have the first statement of the theorem. So, this result shows that it is enough to prove the multiplicativity of our functions for the case of e = 1. Let k_{1}, k_{2} ∈ ℕ be such that (k_{1}, k_{2}) = 1 and r_{m}^{1}(k_{1}), r_{m}^{1}(k_{2}) > 0 (otherwise the theorem holds trivially). Let k := k_{1}k_{2} and n := ω(m). The following equivalence is quite trivial. For all x ∈ ℕ^{n}

[x] = k ⇔ ∃!u, v ∈ ℕ^{n} : x_{i} = u_{i}v_{i}, (u_{i}, v_{i}) = 1 (1 ≤ i ≤ n) and k_{1} = [u], k_{2} = [v]

For simplicity’s sake, let us suppose that α_{i} > 0 for all 1 ≤ i ≤ n. Let f denote the integral vector (φ(p_{1}^{α_{1}}), …, φ(p_{n}^{α_{n}})). Since m is weakly even, we know that for all moduli p_{i}^{α_{i}} (1 ≤ i ≤ n), there exists a primitive root modulo p_{i}^{α_{i}}. So, it is well-known, that if a primitive root exists modulo p_{i}^{α_{i}}, then the number of integers in ℤ_{p_{i}^{α_{i}}} of order d ∈ ℕ is φ(d) (for d | φ(p_{i}^{α_{i}})). Now, with the above facts, and the Chinese Remainder Theorem in mind, we have the following

r_{m}^{1}(k) = ∑ (∏_{i=1}^{n} φ(x_{i}) : x ∈ ℕ^{n}, [x] = k, x | f) =

= ∑ (∏_{i=1}^{n} φ(x_{i}) : u ∈ ℕ^{n}, [u] = k_{1}, u | f, v ∈ ℕ^{n}, [v] = k_{2}, v | f) =

= ∑ ((∏_{i=1}^{n} φ(u_{i})) (∏_{i=1}^{n} φ(v_{i})) : u ∈ ℕ^{n}, [u] = k_{1}, u | f, v ∈ ℕ^{n}, [v] = k_{2}, v | f) =

= (∑ (∏_{i=1}^{n} φ(u_{i}) : u ∈ ℕ^{n}, [u] = k_{1}, u | f)) ·

· (∑ (∏_{j=1}^{n} φ(v_{j}) : v ∈ ℕ^{n}, [v] = k_{2}, v | f)) =

= r_{m}^{1}(k_{1}) · r_{m}^{1}(k_{2})

The multiplicativity of the function ρ_{m}^{1}, may be shown similarly. All we need to do, is change some equality signs to division signs, as follows,

ρ_{m}^{1}(k) = ∑ (∏_{i=1}^{n} φ(x_{i}) : x ∈ ℕ^{n}, [x] | k, x | f) =

= ∑ (∏_{i=1}^{n} φ(x_{i}) : u ∈ ℕ^{n}, [u] | k_{1}, u | f, v ∈ ℕ^{n}, [v] | k_{2}, v | f) =

= ∑ ((∏_{i=1}^{n} φ(u_{i})) (∏_{i=1}^{n} φ(v_{i})) : u ∈ ℕ^{n}, [u] | k_{1}, u | f, v ∈ ℕ^{n}, [v] | k_{2}, v | f) =

= (∑ (∏_{i=1}^{n} φ(u_{i}) : u ∈ ℕ^{n}, [u] | k_{1}, u | f)) ·

· (∑ (∏_{j=1}^{n} φ(v_{j}) : v ∈ ℕ^{n}, [v] | k_{2}, v | f)) =

= r_{m}^{1}(k_{1}) · r_{m}^{1}(k_{2})

□

So the theorem above, tells us, that if m is weakly even, then it is enough to determine r_{m}^{e} and ρ_{m}^{e} at the prime-power divisors of k ∈ ℕ.

Theorem 8.6 Supposing that m is weakly even, β ∈ ℕ, q ∈ ℕ is prime, q^{β} | ψ(m), n = ω(m), and without hurting generality, we may also suppose that for some δ ∈ (ℕ ∪ {0})^{n}

α_{i} > 0, φ(p_{i}^{α_{i}}) = q^{δ_{i}}r_{i}, (q, r_{i}) = 1 (1 ≤ i ≤ n)

Then

ρ_{m}^{1}(q^{β}) = q^{∑_{i=1}^{n} min(β,δ_{i})}
r_{m}^{1}(q^{β}) = ρ_{m}^{1}(q^{β}) − ρ_{m}^{1}(q^{β−1})
r_{m}^{1}(q) = q^{Δ} − 1, Δ = |{δ_{i} ≠ 0 : 1 ≤ i ≤ n}|

Proof The first relation may be proven in the following manner, by considering the ideas that follow from m being weakly even, like in the proof of the previous theorem,

ρ_{m}^{1}(q^{β}) = ∑ (∏_{i=1}^{n} φ(q^{γ_{i}}) : max(γ) ≤ β, γ ≤ δ) =

= ∑_{γ_{i}≤min(β,δ_{i})} q^{∑_{i} γ_{i}} · (1 − \frac{1}{q})^{∑_{γ_{i}≠0} 1} =

= ∏_{i=1}^{n} (1 + q (1 − \frac{1}{q}) + q^{2} (1 − \frac{1}{q}) + … + q^{min(β,δ_{i})} (1 − \frac{1}{q})) =

= ∏_{i=1}^{n} (1 + \frac{q − 1}{q} (−1 + \frac{q^{min(β,δ_{i})+1} − 1}{q − 1})) =

= ∏_{i=1}^{n} (1 − 1 + \frac{1}{q} + q^{min(β,δ_{i})} − \frac{1}{q}) = q^{∑_{i=1}^{n} min(β,δ_{i})}

The second relation is quite trivial. The third one follows from the first and the second. □

Theorem 8.7 If m is weakly even, then

ρ_{m}^{1}(k) = ∏_{i=1}^{∞}(k, φ(p_{i}^{α_{i}})) (k ∈ ℕ)

Proof First, let us examine the case of m = p^{α}, α ∈ ℕ, p is prime, and there exists a primitive root modulo p^{α}, and k = q^{β}, q prime, β ∈ ℕ. Then, for some r ∈ ℕ, we have φ(p^{α}) = q^{δ}r, q ∤ r, so by our previous theorem, we get

ρ_{p^{α}}^{1}(q^{β}) = q^{min(β,δ)} = (q^{β}, φ(p^{β}))

The general case follows quite trivially, through the Chinese Remainder Theorem. □

Theorem 8.8 If m is weakly even, then ρ_{m}^{e} ∈ DI for all e ∈ E_{m}.

Proof Follows easily from our previous theorem. □

Theorem 8.9 For e ∈ E_{m}, k ∈ ℕ

|⟨_{k}R_{m}^{e}⟩_{m}| = \frac{k · r_{m}^{e}(k)}{φ(k)}

Proof Let us group the elements of _{k}R_{m}^{e} into equivalence classes, according to the equivalence relation of Definition 5.5. By Theorem 5.31, we have that each equivalence class has φ(k) elements, so the number of equivalence classes is \frac{|_{k}R_{m}^{e}|}{φ(k)}. Each representative of an equivalence class, has an orbit consisting of k elements, so we see that the above relation holds. □

Theorem 8.10 If m is weakly even, then k ↦ |⟨_{k}R_{m}^{e}⟩_{m}| ∈ M for all e ∈ E_{m}.

Proof Our theorem follows easily from Theorem 8.5 and the above relation. □

9 Idempotent Numbers as an Algebraic Structure

Definition 9.1 For e, e_{1}, e_{2} ∈_{m} E_{m}, let us define the following operators

ē:= (1 − e) mod m

e_{1} ∘ e_{2} := (e_{1}e_{2} + ē_{1}ē_{2}) mod m
e_{1} ⊗ e_{2} := \overline{ē_{1} · ē_{2}}
e_{1} ∼ e_{2} := \overline{ē_{1} · e_{2}}

Theorem 9.1 For e ∈ E_{m}, a, b, c, d ∈ ℤ, n ∈ ℕ, the following identities hold

(ae + bē)(ce + dē) ≡ (ac)e + (bd)ē (mod m)

(ae + bē)^{n} ≡ (a^{n})e + (b^{n})ē (mod m)

Proof

(ae + bē)(ce + dē) ≡ (ac)e + (ad)eē + (bc)ēe + (bd)ē ≡ (ac)e + (bd)ē (mod m) The second identity follows from the first one. □ Theorem 9.2 For e, e_{1}, e_{2} ∈ E_{m}, we have

ē, e_{1} ∘ e_{2}, e_{1} ⊗ e_{2}, e_{1} ∼ e_{2} ∈ E_{m}

Proof Follows trivially from our previous theorem. □ Definition 9.2 Let B_{m} denote the set

B_{m} := {p_{i}^{α_{i}} : α_{i} > 0}

For A ⊂ B_{m}

Ā := B_{m} \ A

For e ∈ E_{m} define

B_{m}(e) := {k ∈ B_{m} : k | e}

Theorem 9.3 For e, e_{1}, e_{2} ∈ E_{m} the following identities hold

B_{m}(ē) = \overline{B_{m}(e)}

B_{m}(e_{1} · e_{2}) = B_{m}(e_{1}) ∪ B_{m}(e_{2})
B_{m}(e_{1} ⊗ e_{2}) = B_{m}(e_{1}) ∩ B_{m}(e_{2})
B_{m}(e_{1} ∼ e_{2}) = B_{m}(e_{1}) \ B_{m}(e_{2})
B_{m}(e_{1} ∘ e_{2}) = B_{m}(e_{1})△B_{m}(e_{2})

Proof The first two identities are trivial.

B_{m}(e_{1} ⊗ e_{2}) = B_{m}(\overline{ē_{1} · ē_{2}}) = \overline{B_{m}(ē_{1} · ē_{2})} = \overline{\overline{B_{m}(e_{1})} ∪ \overline{B_{m}(e_{2})}} = B_{m}(e_{1}) ∩ B_{m}(e_{2})

B_{m}(e_{1} ∼ e_{2}) = B_{m}(e_{1}) ∩ \overline{B_{m}(e_{2})} = B_{m}(e_{1}) \ B_{m}(e_{2})

To prove the last identity, we first make a bit of calculation.

(e_{1} ∼ e_{2}) · (e_{2} ∼ e_{1}) ≡ \overline{ē_{1}e_{2}} · \overline{e_{1}ē_{2}} ≡ (1 − ē_{1}e_{2})(1 − e_{1}ē_{2}) ≡
≡ 1 − e_{1}ē_{2} − ē_{1}e_{2} ≡ e_{1} + ē_{1} − e_{1}ē_{2} − ē_{1}e_{2} ≡ e_{1} ∘ e_{2} (mod m)
B_{m}(e_{1} ∘ e_{2}) = B_{m}((e_{1} ∼ e_{2}) · (e_{2} ∼ e_{1})) = B_{m}(e_{1} ∼ e_{2}) ∪ B_{m}(e_{2} ∼ e_{1}) =
= (B_{m}(e_{1}) \ B_{m}(e_{2})) ∪ (B_{m}(e_{2}) \ B_{m}(e_{1})) = B_{m}(e_{1})△B_{m}(e_{2})

□

Considering the properties above, we see that an isomorphism may be defined between E_{m} and the class of subsets of any finite set, which has ω(m) elements.

Theorem 9.4 The structure ⟨E_{m}; {1,^{−1} , ∘}⟩ is an Abelian group, where each element is of order two.

Proof First, we will show that for all e_{1}, e_{2} ∈ E_{m}, there exists one and only one e_{3} ∈ E_{m} such that e_{1} = e_{2} ∘ e_{3}. Let us take any e ∈ E_{m}. Then

e_{2} ∘ e ≡ ē_{2} − (ē_{2} − e_{2})e (mod m)

and (ē_{2} − e_{2}, m) = 1 since (ē_{2} − e_{2})^{2} ≡ 1 (mod m). So by Theorem 3.5 we have

|e_{2} ∘ E_{m}| = |ē_{2} − (ē_{2} − e_{2})E_{m}| = |(ē_{2} − e_{2})E_{m}| = 2^{ω( \frac{m}{(ē_{2}−e_{2},m)} )} = 2^{ω(m)} = |E_{m}|

which proves both the existence and unicity of e_{3}. It is clear that e ∘ 1 = e and e ∘ e = 1, so we have the existence of an inverse, and that each element is of order two. It is also obvious that ∘ is commutative. In order to show that ∘ is associative, take any e_{1}, e_{2}, e_{3} ∈ E_{m}. Then

(e_{1} ∘ e_{2}) ∘ e_{3} ≡ (e_{1}e_{2} + ē_{1}ē_{2}) ∘ e_{3} ≡ (e_{1}e_{2} + ē_{1}ē_{2})e_{3} + (ē_{1}e_{2} + e_{1}ē_{2})ē_{3} ≡
≡ e_{1}e_{2}e_{3} + ē_{1}ē_{2}e_{3} + ē_{1}e_{2}ē_{3} + e_{1}ē_{2}ē_{3} ≡ e_{1}(e_{2}e_{3} + ē_{2}ē_{3}) + ē_{1}(ē_{2}e_{3} + e_{2}ē_{3}) ≡
≡ e_{1} ∘ (e_{2}e_{3} + ē_{2}ē_{3}) ≡ e_{1} ∘ (e_{2} ∘ e_{3}) (mod m)

□

Theorem 9.5 The ⊗ operator is commutative and associative. Multiplication is distributive with respect to ⊗, and ⊗ is distributive with respect to ∘.

Proof The commutativity of ⊗ is trivial. Now, take any e_{1}, e_{2}, e_{3} ∈ E_{m}.

(e_{1} ⊗ e_{2}) ⊗ e_{3} ≡ \overline{\overline{(e_{1} ⊗ e_{2})} · ē_{3}} ≡ \overline{\overline{(\overline{ē_{1} · ē_{2}})} · ē_{3}} ≡ \overline{ē_{1} · ē_{2} · ē_{3}} (mod m)

which proves the associativity of ⊗. Now, to prove the third property, we calculate

e_{1} · (e_{2} ⊗ e_{3}) ≡ e_{1} · \overline{ē_{2} · ē_{3}} ≡ e_{1}(1 − (1 − e_{2})(1 − e_{3})) ≡ e_{1}e_{3} + e_{1}e_{2} − e_{1}e_{2}e_{3} ≡

≡ 1 − (1 − e_{1}e_{2})(1 − e_{1}e_{3}) ≡ \overline{\overline{e_{1}e_{2}} · \overline{e_{1}e_{3}}} ≡ (e_{1} · e_{2}) ⊗ (e_{1} · e_{3}) (mod m)

The fourth property follows from

e_{1} ⊗ (e_{2} ∘ e_{3}) ≡ \overline{ē_{1}\overline{(e_{2}e_{3} + ē_{2}ē_{3})}} ≡ \overline{ē_{1}(e_{2}ē_{3} + ē_{2}e_{3})} ≡
≡ \overline{ē_{1}ē_{3} − ē_{1}ē_{2}ē_{3} + ē_{1}ē_{2} − ē_{1}ē_{3}ē_{2}} ≡ \overline{\overline{ē_{1}ē_{2}} · ē_{1}ē_{3} + ē_{1}ē_{2} · \overline{ē_{1}ē_{3}}} ≡
≡ \overline{ē_{1}ē_{2}} · \overline{ē_{1}ē_{3}} + ē_{1}ē_{2} · ē_{1}ē_{3} ≡ (e_{1} ⊗ e_{2}) ∘ (e_{1} ⊗ e_{3}) (mod m)

□

Theorem 9.6 The structure ⟨E_{m}; {∘, ⊗}⟩ is a commutative ring, with ∘ being "addition" and ⊗ being "multiplication".

Proof Follows from our previous two theorems. □

We see that because of the isomorphism that exists between E_{m} and the subsets of a finite set, the above theorem states the well-known fact from Set Theory, that the subsets of a set form a commutative ring with respect to the operators ∩ and △.

Theorem 9.7 For e, e_{1}, e_{2} ∈ E_{m}, we have

e · ē ≡ m, e + ē ≡ 1 (mod m)
e ∘ 1 = e, e ∘ ē = m, e ∘ m = ē
\overline{e_{1} ∘ e_{2}} = ē_{1} ∘ e_{2} = e_{1} ∘ ē_{2}
e_{1} ∘ e_{2} ≡ (e_{1} + ē_{2})(ē_{1} + e_{2}) ≡ (e_{1} − ē_{2})^{2} ≡ (ē_{1} − e_{2})^{2} (mod m)

Proof The fourth line of identities seems a bit nontrivial, so we shall prove it in part below.

(e_{1} + ē_{2})(ē_{1} + e_{2}) ≡ e_{1}ē_{1} + e_{1}e_{2} + ē_{2}ē_{1} + ē_{2}e_{2} ≡ e_{1}e_{2} + ē_{2}ē_{1} (mod m)
(e_{1} − ē_{2})^{2} ≡ e_{1} − 2e_{1}ē_{2} + ē_{2} ≡ e_{1}(1 − ē_{2}) + ē_{2}(1 − e_{1}) ≡ e_{1}e_{2} + ē_{2}ē_{1} (mod m)

□

Note that the first and second lines of identities show that ∘ behaves somewhat like multiplication. In our upcoming theorems, we will prove properties of ⊗ which show that it may behave in a sense both like multiplication and addition.

Theorem 9.8 For e, e_{1}, …, e_{n} ∈ E_{m}, we have

e ⊗ e = e, e ⊗ 1 = 1

(e_{1} ⊗ e_{2}) − (ē_{1} ⊗ ē_{2}) ≡ e_{1} · e_{2} − ē_{1} · ē_{2} (mod m)
((e_{1} ⊗ e_{2}) − (ē_{1} ⊗ ē_{2}))^{2} ≡ e_{1} ∘ e_{2} (mod m)
\overline{ē_{1} ⊗ ē_{2}} ≡ e_{1} · e_{2} (mod m)

⨂_{i=1}^{n} e_{i} = \overline{∏_{i=1}^{n} ē_{i}}

e ⊗ ē = 1, e ⊗ 0 = e
(e_{1} · e_{2}) ⊗ (ē_{1} · ē_{2}) ≡ e_{1} · e_{2} + ē_{1} · ē_{2} ≡ e_{1} ∘ e_{2} (mod m)

Proof The first four lines of properties, are quite trivial. The fifth property may be proven via induction, using the associativity of ⊗. The sixth and seventh lines are quite trivial calculations as well. □

Our next theorem shows a peculiar property of ⊗, in which it behaves both like addition and multiplication. In fact, the second property sheds light on the double nature of this operator.

Theorem 9.9 For e, e_{1}, e_{2} ∈ E_{m}, we have

(e_{1} ∘ e) ⊗ (e_{2} ∘ e) ≡ (e_{1} ⊗ e_{2})e + (ē_{1} ⊗ ē_{2})ē (mod m)
e_{1} ⊗ e_{2} ≡ e_{1} + e_{2} − e_{1} · e_{2} (mod m)

Proof

(e_{1} ∘ e) ⊗ (e_{2} ∘ e) ≡ 1 − \overline{e_{1} ∘ e} · \overline{e_{2} ∘ e} ≡
≡ 1 − (ē_{1}e + e_{1}ē)(ē_{2}e + e_{2}ē) ≡ 1 − (ē_{1}ē_{2}e + e_{1}e_{2}ē) ≡
≡ e + ē − (ē_{1}ē_{2}e + e_{1}e_{2}ē) ≡ (e_{1} ⊗ e_{2})e + (ē_{1} ⊗ ē_{2})ē (mod m)

The second property is just simple calculation. □

10 Second-Degree Polynomials

Definition 10.1 For k ∈ ℤ, let S_{m,k} denote the set of solutions of the equation

x^{2} ≡ kx (mod m)

among the elements of ℤ_{m}.

Theorem 10.1 Let k ∈ ℤ be such that (k, m) = 1. Then

S_{m,k} = kE_{m} mod m

Proof Let i ∈ ℕ be such that α_{i} is positive. Then from

x_{0}^{2} ≡ kx_{0} (mod p_{i}^{α_{i}})

it follows that

x_{0} ≡ 0 or x_{0} ≡ k (mod p_{i}^{α_{i}})

Let e ∈ E_{m} be such that μ_{m}(x_{0}) = μ_{m}(e). Then for all i ∈ ℕ we have x_{0} ≡ ke (mod p_{i}^{α_{i}}), so x_{0} ≡ ke (mod m). So we may conclude that S_{m,k} ⊂ kE_{m} mod m. Now, we see that kE_{m} mod m ⊂ S_{m,k} as well, since for any e ∈ E_{m}, we have

(ke)^{2} ≡ k(ke) (mod m)

□

Theorem 10.2 Let a, b ∈ ℤ be such that (b − a, m) = 1. Then for all solutions r ∈ ℤ_{m} of the equation

(x − a)(x − b) ≡ 0 (mod m)

there exists a unique e ∈ E_{m}, such that

r ≡ ae + bē (mod m)

Proof Our equation may be rearranged as

(x − a)^{2} ≡ (b − a)(x − a) (mod m)

So since (b − a, m) = 1, by our previous theorem we have that for all solutions r ∈ ℤ, there exists a unique e ∈ E_{m}, such that

r − a ≡ (b − a)e (mod m)

which may be rearranged as

r ≡ ae + bē (mod m)

□

Theorem 10.3 Let m and a ∈ ℤ be such that (2a, m) = 1. Then for all solutions r_{1}, r_{2} ∈ ℤ_{m} of the equation

x^{2} ≡ a (mod m)

there exists a unique e ∈ E_{m}, such that

r_{1} ≡ r_{2}(e − ē) (mod m)

Proof With the notation above, we have that our equation is equivalent to the equation

(x − r_{2})(x − (−r_{2})) ≡ 0 (mod m)

Now, since r_{2}^{2} ≡ a (mod m), we have (r_{2}, m) = (a, m) = 1, from which we have (r_{2} − (−r_{2}), m) = 1 since 2 ∤ m, so by our previous theorem, we have that there exists a unique e ∈ E_{m}, such that

r_{1} ≡ r_{2}e + (−r_{2})ē ≡ r_{2}(e − ē) (mod m)

□

Theorem 10.4 Let m be an odd number, or four times an odd number. Then for all solutions r ∈ ℤ_{m} of the equation

x^{2} ≡ 1 (mod m)

there exists a unique e ∈ E_{m}, such that

r ≡ e − ē (mod m)

Proof The case when m is odd, follows from our previous theorem. Now, if m is four times an odd number, then it is easy to see that

ω (\frac{m}{(2, m)}) = ω(m)

Our equation is equivalent to the equation

(x + 1)^{2} ≡ 2(x + 1) (mod m)

so we see that all elements of 2E_{m} − 1 satisfy this equation, and by Theorem 3.5 we also have that

|2E_{m} − 1 mod m| = 2^{ω(\frac{m}{(2,m)})} = 2^{ω(m)}

which is the number of solutions of our equation if m is four times an odd number, so we have that, for all r ∈ ℤ_{m} satisfying the equation, there exists a unique e ∈ E_{m}, such that

r ≡ 2e − 1 ≡ e − ē (mod m)

□

Theorem 10.5 Let m be an odd number. Then for all e ∈ E_{m}

S_{m}^{R}(2, e) ⊂ {e(e_{0} − ē_{0}) mod m : e_{0} ∈ E_{m}}

Furthermore, if e ≠ m, then for all e_{0} ∈ E_{m} we have e(e_{0} − ē_{0}) ≢ e(ē_{0} − e_{0}) (mod m). Moreover, the following properties are valid

|S_{m}^{R}(2, e)| = 2^{ω(μ_{m}(e))}

∏ S_{m}^{R}(2, e) ≡ (−1)^{2^{ω(μm(e))−1}} · e (mod m)

Proof Take any i ∈ ℕ such that p_{i} ≠ 2, and a ∈ S_{m}^{R}(2, e). There are two possible cases. If a^{2} ≡ 0 (mod p_{i}^{α_{i}}), then a ≡ 0 (mod p_{i}^{α_{i}}), since a ∈ R_{p_{i}^{α_{i}}}. If a^{2} ≡ 1 (mod p_{i}^{α_{i}}), then since p_{i} ≠ 2 it follows that a ≡ ±1 (mod p_{i}^{α_{i}}). From these two cases, we have that a ≡ e(e_{0} − ē_{0}) (mod m), for some e_{0} ∈ E_{m}. Let us suppose indirectly, that there exists some e_{0} ∈ E_{m}, such that e(e_{0} − ē_{0}) ≡ e(ē_{0} − e_{0}) (mod m). Then 2(e_{0} − ē_{0})e ≡ 0 (mod m), from which we have e ≡ 0 (mod m), since (2(e_{0} − ē_{0}), m) = 1, because

(e_{0} − ē_{0})^{2} ≡ e_{0} + ē_{0} ≡ 1 (mod m)

So e = m, which of course is a contradiction. To prove the third property, observe that for all a ∈ S_{m}^{R}(2, e)

a^{2} ≡ e (mod m) ⇔ a^{2} ≡ 1 (mod μ_{m}(e)) and a^{2} ≡ 0 (mod \frac{m}{μ_{m}(e)})

So for all p_{i}^{α_{i}} ∈ \overline{B_{m}(e)}, we have a ≡ ±1 (mod p_{i}^{α_{i}}). Meanwhile a ≡ 0 (mod \frac{m}{μ_{m}(e)}), since a ∈ R_{m}^{e}. So by the Chinese Remainder Theorem, and since ω(μ_{m}(e)) = |\overline{B_{m}(e)}|, we have the formula. By the first property, with the notation n := 2^{ω(μ_{m}(e))}, we have

∏ S_{m}^{R}(2, e) ≡ e(e_{1} − ē_{1})(e_{2} − ē_{2}) … (e_{n} − ē_{n}) ≡
≡ e · [(e_{1} − ē_{1}) … (e\frac{n}{2} − ē\frac{n}{2} )] · [(ē_{1} − e_{1}) … (ē\frac{n}{2} − e\frac{n}{2} )] ≡
≡ e · (−1)^{\frac{n}{2}} (mod m)

□

Definition 10.2 For k ∈ ℤ, r ∈ S_{m,k}, e ∈ E_{m} define

r̄:= (k − r) mod m
r ∘ e := (re + r̄ē) mod m
r ⊗ e := (k − r̄ē) mod m

Note that we continue to use the same notations as in the previous section. In order to distinguish between these operators that have been denoted the same way, even though they are different, always refer to the set from which the operands have been taken.

Theorem 10.6 For k ∈ ℤ, r ∈ S_{m,k}, e ∈ E_{m}, we have

r̄, r ∘ e, r ⊗ e ∈ S_{m,k}

Proof

(k − r)^{2} ≡ k^{2} − 2kr + r^{2} ≡ k^{2} − 2kr + kr ≡ k(k − r) (mod m)
(r ∘ e)^{2} ≡ r^{2}e + r̄^{2}ē ≡ (kr)e + (kr̄)ē ≡ k(r ∘ e) (mod m)
(r ⊗ e)^{2} ≡ k^{2} − 2kr̄ē + r̄^{2}ē ≡ k(k − r̄ē) ≡ k(r ⊗ e) (mod m)

□ Theorem 10.7 Take any e ∈ E_{m} and k ∈ ℤ. Then

S_{m,k} = S_{m,k} ∘ e

Proof In order to show the equality of the two sets, it is enough for us to prove that for any r_{1}, r_{2} ∈ S_{m,k}, r_{1} ≠ r_{2}, we have r_{1} ∘ e ≠ r_{2} ∘ e. For let us suppose indirectly, that there exist some r_{1}, r_{2} ∈ S_{m,k}, r_{1} ≠ r_{2}, such that r_{1} ∘ e = r_{2} ∘ e. Then

r_{1} − r_{2} ≡ (e − ē)^{2}(r_{1} − r_{2}) ≡ (e − ē)((r_{1} − r_{2})e + (r_{2} − r_{1})ē) ≡

≡ (e − ē)((r_{1} − r_{2})e + (r̄_{1} − r̄_{2})ē) ≡ (e − ē)(r_{1} ∘ e − r_{2} ∘ e) ≡ 0 (mod m)

So we arrive at a contradiction. □ Theorem 10.8 For k ∈ ℤ, e, e_{1}, e_{2} ∈ E_{m}, r ∈ S_{m,k} the following properties hold

\overline{r ∘ e} = r ∘ ē = r̄ ∘ e

(r ∘ e_{1}) ∘ e_{2} = r ∘ (e_{1} ∘ e_{2})

Proof

\overline{r ∘ e} ≡ k − (r ∘ e) ≡ ke + kē − (re + r̄ē) ≡ r̄e + rē ≡ r ∘ ē ≡ r̄ ∘ e (mod m)
(r ∘ e_{1}) ∘ e_{2} ≡ (re_{1} + r̄ē_{1}) ∘ e_{2} ≡ (re_{1} + r̄ē_{1})e_{2} + (r̄e_{1} + rē_{1})ē_{2} ≡
≡ re_{1}e_{2} + r̄ē_{1}e_{2} + r̄e_{1}ē_{2} + rē_{1}ē_{2} ≡ r(e_{1}e_{2} + ē_{1}ē_{2}) + r̄(ē_{1}e_{2} + e_{1}ē_{2}) ≡
≡ r ∘ (e_{1} ∘ e_{2}) (mod m)

□ Note that the second property is somewhat like associativity. Theorem 10.9 For k ∈ ℤ, (k, m) = 1 and r ∈ S_{m,k}, the following equivalence holds

r ∘ e_{1} = r ∘ e_{2} ⇔ e_{1} = e_{2} (e_{1}, e_{2} ∈ E_{m})

Proof The ⇐ part of the equivalence is trivial. To prove the ⇒ part, first we see that

(r − r̄)^{2} ≡ r^{2} − 2rr̄ + r̄^{2} ≡ kr + kr̄ ≡ k^{2} (mod m)

Now, let us suppose that r ∘ e_{1} = r ∘ e_{2}. This means that

re_{1} + r̄ē_{1} ≡ re_{2} + r̄ē_{2} ⇒ r̄ + (r − r̄)e_{1} ≡ r̄ + (r − r̄)e_{2} (mod m)

First subtracting r̄, then squaring both sides, we get

k^{2}e_{1} ≡ k^{2}e_{2} (mod m)

which implies that e_{1} = e_{2}, since (k, m) = 1. □

Definition 10.3 For e ∈ E_{m}, r_{1}, r_{2} ∈ S_{m,e} define

r_{1} ∘ r_{2} := (r_{1}r_{2} + r̄_{1}r̄_{2}) mod m

r_{1} ⊗ r_{2} := \overline{r̄_{1} · r̄_{2}}

Same can be said for these operators, as for those of Definition 10.2. Theorem 10.10 For e ∈ E_{m}, r_{1}, r_{2} ∈ S_{m,e}, we have

r_{1} ∘ r_{2}, r_{1} ⊗ r_{2} ∈ S_{m,e}

Proof

(r_{1} ∘ r_{2})^{2} ≡ r_{1}^{2}r_{2}^{2} + r̄_{1}^{2}r̄_{2}^{2} ≡ e(r_{1} ∘ r_{2}) (mod m)
(\overline{r̄_{1} · r̄_{2}})^{2} ≡ e − 2er̄_{1}r̄_{2} + r̄_{1}^{2}r̄_{2}^{2} ≡ e(1 − r̄_{1}r̄_{2}) ≡ e(r_{1} ⊗ r_{2}) (mod m)

□ Theorem 10.11 For e ∈ E_{m}, a, b ∈ R_{m}^{e}, c, d ∈ ℤ, n ∈ ℕ, r ∈ S_{m,e}, we have

(ar + br̄)(cr + dr̄) ≡ (ac)r + (bd)r̄ (mod m)

(ar + br̄)^{n} ≡ a^{n}r + b^{n}r̄ (mod m)

Proof

rr̄ ≡ 0 ⇒ (ar + br̄)(cr + dr̄) ≡ (ac)r^{2} + (bd)r̄^{2} ≡ (ea)cr + (eb)dr̄ (mod m) The second property follows from the first one via induction. □ Theorem 10.12 For all e ∈ E_{m}, k ∈ R_{m}^{e} we have

S_{m,k} ∩ R_{m}^{e} = {k}

Proof For any r ∈ S_{m,k} ∩ R_{m}^{e} we have

r ∈_{μ_{m}(e)} S_{μ_{m}(e),k} ∩ R_{μ_{m}(e)}^{1} = (kE_{μ_{m}(e)} mod μ_{m}(e)) ∩ R_{μ_{m}(e)}^{1} =

= {k mod μ_{m}(e)} ⇒ r ≡ k (mod μ_{m}(e))

So, since

r ≡ 0 ≡ k (mod \frac{m}{μ_{m}(e)})

and μ_{m}(e) = μ_{m}(k) = μ_{m}(r), we have that r = k. □

Acknowledgements

I would like to express my vast gratitude to Professor Mihály Szalay, for the enormous amount of time and effort it took to review my paper. Besides his various helpful comments and corrections, I would like to say special thanks to him for his help on the proof of Theorem 5.20, which was a lemma of utmost importance.

References

[1] Andrews G.E., Number Theory, Dover Publications Inc., New York, 1994, pp. 49-138.