On the Multiplicative Order of a^{n} Modulo n

Jonathan Chappelon^{1} Université Lille Nord de France F-59000 Lille France

        jonathan.chappelon@lmpa.univ-littoral.fr

Abstract

Let n be a positive integer and α_{n} be the arithmetic function which assigns the multiplicative order of a^{n} modulo n to every integer a coprime to n and vanishes elsewhere. Similarly, let β_{n} assign the projective multiplicative order of a^{n} modulo n to every integer a coprime to n and vanishes elsewhere. In this paper, we present a study of these two arithmetic functions. In particular, we prove that for positive integers n_{1} and n_{2} with the same square-free part, there exists a relationship between the functions α_{n_{1}} and α_{n_{2}} and between the functions β_{n_{1}} and β_{n_{2}}. This allows us to reduce the determination of α_{n} and β_{n} to the case where n is square-free. These arithmetic functions recently appeared in the context of an old problem of Molluzzo, and more precisely in the study of which arithmetic progressions yield a balanced Steinhaus triangle in ℤ/nℤ for n odd.

1 Introduction

We start by introducing some notation relating to the order of certain elements modulo n. For every positive integer n and every prime number p, we denote by v_{p}(n) the p-adic valuation of n, i.e., the greatest exponent e ⩾ 0 for which p^{e} divides n. The prime factorization of n may then be written as

n = ∏_{p∈ℙ}p^{v_{p}(n)},

where ℙ denotes the set of all prime numbers. We denote by rad(n) the radical of n, i.e., the largest square-free divisor of n, namely

rad(n) = ∏_{p|n^{p∈ℙ}} p.

1ULCO, LMPA J. Liouville, B.P. 699, F-62228 Calais, France and CNRS, FR 2956, France.

For every positive integer n and every integer a coprime to n, we denote by O_{n}(a) the multiplicative order of a modulo n, i.e., the smallest positive integer e such that a^{e} ≡ 1 (mod n), namely

O_{n}(a) = min {e ∈ ℕ^{∗} | a^{e} ≡ 1 (mod n)}

and we denote by R_{n}(a) the multiplicative remainder of a modulo n, i.e., the multiple of n defined by

R_{n}(a) = a^{O_{n}(a)} − 1.

The multiplicative order of a modulo n also corresponds with the order of the element π_{n}(a), where π_{n} : ℤ −↠ ℤ/nℤ is the canonical surjective morphism, in the multiplicative group (ℤ/nℤ)^{∗}, the group of units of ℤ/nℤ. Note that O_{n}(a) divides φ(n), φ being the Euler’s totient function.

For every positive integer n, we define and denote by α_{n} the arithmetic function

α_{n} : ℤ ⟶ ℕ a ⟼ \{ \begin{matrix}O_{n} (a^{n}) , & for all gcd(a, n) = 1; \\ 0, & otherwise, \end{matrix}

where gcd(a, n) denotes the greatest common divisor of a and n, with the convention that gcd(0, n) = n. Observe that, for every a coprime to n, the integer α_{n}(a) divides φ(n)/ gcd(φ(n), n). This follows from the previous remark on O_{n}(a) and the equality α_{n}(a) = O_{n}(a^{n}) = O_{n}(a)/ gcd(O_{n}(a), n).

For every positive integer n and every integer a coprime to n, we denote by PO_{n}(a) the projective multiplicative order of a modulo n, i.e., the smallest positive integer e such that a^{e} ≡ ±1 (mod n), namely

PO_{n}(a) = min {e ∈ ℕ^{∗} | a^{e} ≡ ±1 (mod n)} .

The projective multiplicative order of a modulo n also corresponds with the order of the element \overline{π_{n}(a)} in the multiplicative quotient group (ℤ/nℤ)^{∗}/\{−1, 1\}.

For every positive integer n, we define and denote by β_{n} the arithmetic function

β_{n} : ℤ ⟶ ℕ a ⟼ \{ \begin{matrix}PO_{n} (a^{n}) , & for all gcd(a, n) = 1; \\ 0, & otherwise. \end{matrix}

Observe that we have the alternative α_{n} = β_{n} or α_{n} = 2β_{n}.

In this paper, we study in detail these two arithmetic functions. In particular, we prove that, for every positive integers n_{1} and n_{2} such that

\{ \begin{matrix}rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩽ 1; \\ 2 rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩾ 2, \end{matrix}

the integer α_{n_{1}}(a) (respectively β_{n_{1}}(a)) divides α_{n_{2}}(a) (resp. β_{n_{2}}(a)), for every integer a. More precisely, we determine the exact relationship between the functions α_{n_{1}} and α_{n_{2}} and between β_{n_{1}} and β_{n_{2}}. We prove that we have

α_{n_{1}}(a) = \frac{α_{n_{2}}(a)}{gcd (α_{n_{2}}(a), \frac{gcd(n_{1},R_{n_{2}}(a))}{n_{2}})} for all gcd(a, n_{1}) = 1

in Theorem 6 of Section 2 and that we have

β_{n_{1}}(a) = \frac{β_{n_{2}}(a)}{gcd (β_{n_{2}}(a), \frac{gcd(n_{1},R_{n_{2}}(a))}{n_{2}})} for all gcd(a, n_{1}) = 1

in Theorem 13 of Section 3. Thus, for every integer a coprime to n, the determination of α_{n}(a) is reduced to the computation of α_{rad(n)}(a) and R_{rad(n)}(a) if v_{2}(n) ⩽ 1 and of α_{2 rad(n)}(a) and R_{2 rad(n)}(a) if v_{2}(n) ⩾ 2. These theorems on the functions α_{n} and β_{n} are derived from Theorem 7 of Section 2, which states that

O_{n_{1}}(a) = O_{n_{2}}(a) · \frac{n_{1}}{gcd(n_{1}, R_{n_{2}}(a))},

for all integers a coprime to n_{1} and n_{2}. This result generalizes the following theorem of Nathanson which, in the above notation, states that for every odd prime number p and for every positive integer k, we have the equality

O_{p^{k}}(a) = O_{p}(a) · \frac{p^{k}}{gcd(p^{k}, R_{p}(a))}

for all integers a not divisible by p.

Theorem 3.6 of [3]. Let p be an odd prime, and let a ≠ ±1 be an integer not divisible by p. Let d be the order of a modulo p. Let k_{0} be the largest integer such that a^{d} ≡ 1 (mod p^{k_{0}}). Then the order of a modulo p^{k} is d for k = 1, …, k_{0} and dp^{k−k_{0}} for k ⩾ k_{0}.

For every finite sequence S = (a_{1}, …, a_{m}) of length m ⩾ 1 in ℤ/nℤ, we denote by ΔS the Steinhaus triangle of S, that is the finite multiset of cardinality \binom{m+1}{2} in ℤ/nℤ defined by

ΔS = \{∑_{k=0}^{i} \binom{i}{k}a_{j+k} | 0 ⩽ i ⩽ m − 1 , 1 ⩽ j ⩽ m − i\} .

A finite sequence S in ℤ/nℤ is said to be balanced if each element of ℤ/nℤ occurs in its Steinhaus triangle ΔS with the same multiplicity. For instance, the sequence (2, 2, 3, 3) of length 4 is balanced in ℤ/5ℤ. Indeed, as depicted in Figure 1, its Steinhaus triangle is composed by each element of ℤ/5ℤ occuring twice.

0 4 1 4 0 1 2 2 3 3

Figure 1: The Steinhaus triangle of a balanced sequence in ℤ/5ℤ

Note that, for a sequence S of length m ⩾ 1 in ℤ/nℤ, a necessary condition on m for S to be balanced is that the integer n divides the binomial coefficient \binom{m+1}{2}. In 1976, John C. Molluzzo [2] posed the problem to determine whether this necessary condition on m is also sufficient to guarantee the existence of a balanced sequence. In [1], it was proved that, for each odd number n, there exists a balanced sequence of length m for every m ≡ 0 or −1 (mod α_{n}(2) · n) and for every m ≡ 0 or −1 (mod β_{n}(2) · n). This was achieved by analyzing the Steinhaus triangles generated by arithmetic progressions. In particular, since β_{3^{k}}(2) = 1 for all k ⩾ 1, the above result implies a complete and positive solution of Molluzzo’s problem in ℤ/nℤ for all n = 3^{k}.

2 The arithmetic function α_{n}

The table depicted in Figure 2 gives us the first values of α_{n}(a) for every positive integer n, 1 ⩽ n ⩽ 20, and for every integer a, −20 ⩽ a ⩽ 20.

\begin{matrix}n\a & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 3 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 \\ 4 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 5 & 1 & 4 & 4 & 2 & 0 & 1 & 4 & 4 & 2 & 0 & 1 & 4 & 4 & 2 & 0 & 1 & 4 & 4 & 2 & 0 \\ 6 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 7 & 1 & 3 & 6 & 3 & 6 & 2 & 0 & 1 & 3 & 6 & 3 & 6 & 2 & 0 & 1 & 3 & 6 & 3 & 6 & 2 \\ 8 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 9 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 & 0 & 1 & 2 \\ 10 & 1 & 0 & 2 & 0 & 0 & 0 & 2 & 0 & 1 & 0 & 1 & 0 & 2 & 0 & 0 & 0 & 2 & 0 & 1 & 0 \\ 11 & 1 & 10 & 5 & 5 & 5 & 10 & 10 & 10 & 5 & 2 & 0 & 1 & 10 & 5 & 5 & 5 & 10 & 10 & 10 & 5 \\ 12 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 13 & 1 & 12 & 3 & 6 & 4 & 12 & 12 & 4 & 3 & 6 & 12 & 2 & 0 & 1 & 12 & 3 & 6 & 4 & 12 & 12 \\ 14 & 1 & 0 & 3 & 0 & 3 & 0 & 0 & 0 & 3 & 0 & 3 & 0 & 1 & 0 & 1 & 0 & 3 & 0 & 3 & 0 \\ 15 & 1 & 4 & 0 & 2 & 0 & 0 & 4 & 4 & 0 & 0 & 2 & 0 & 4 & 2 & 0 & 1 & 4 & 0 & 2 & 0 \\ 16 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 17 & 1 & 8 & 16 & 4 & 16 & 16 & 16 & 8 & 8 & 16 & 16 & 16 & 4 & 16 & 8 & 2 & 0 & 1 & 8 & 16 \\ 18 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\ 19 & 1 & 18 & 18 & 9 & 9 & 9 & 3 & 6 & 9 & 18 & 3 & 6 & 18 & 18 & 18 & 9 & 9 & 2 & 0 & 1 \\ 20 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \end{matrix}

Figure 2: The first values of α_{n}(a)

The positive integer α_{n}(a) seems to be difficult to determine. Indeed, there is no general formula known to compute the multiplicative order of an integer modulo n but, however, we get the following helpful propositions.

Lemma 1. Let n_{1} and n_{2} be two positive integers such that rad(n_{1}) = rad(n_{2}). Then, an integer a is coprime to n_{1} if, and only if, it is also coprime to n_{2}.

Proof. This follows from the definition of the greatest common divisor of two integers and from the definition of the radical of an integer.

Proposition 2. Let n_{1} and n_{2} be two positive integers such that rad(n_{1})|n_{2} and n_{2}|n_{1}. Then, for every integer a, the integer α_{n_{1}}(a) divides α_{n_{2}}(a).

Proof. If a is not coprime to n_{1} and n_{2}, then, by definition of the functions α_{n_{1}} and α_{n_{2}} and by Lemma 1, we have

α_{n_{1}}(a) = α_{n_{2}}(a) = 0.

Suppose that a is coprime to n_{1} and n_{2}. If v_{p}(n_{1}) = 1 for all prime factors p of n_{1}, then n_{2} = n_{1}. Otherwise, let p be a prime factor of n_{1} such that v_{p}(n_{1}) ⩾ 2. We shall show that α_{n_{1}}(a) divides α_{n_{1}/p}(a). By definition of α_{n_{1}/p}(a), there exists an integer u such that

a^{α_{n_{1}/p}(a)· \frac{n_{1}}{p}} = 1 + u · \frac{n_{1}}{p} .

Therefore, by the binomial theorem, we have

a^{α_{n_{1}/p}(a)·n_{1}} = (a^{α_{n_{1}/p}(a)· \frac{n_{1}}{p}} )^{p} = (1 + u · \frac{n_{1}}{p} )^{p} = 1 + u · n_{1} + ∑_{k=2}^{p} \binom{p}{k} · u^{k} · (\frac{n_{1}}{p} )^{k}.

Since v_{p}(n_{1}) ⩾ 2, it follows that (n_{1}/p)^{k} is divisible by n_{1} for every integer k ⩾ 2 and so

a^{α_{n_{1}/p}(a)·n_{1}} ≡ 1 (mod n_{1}).

Hence α_{n_{1}}(a) divides α_{n_{1}/p}(a). This completes the proof.

An exact relationship between α_{n_{1}}(a) and α_{n_{2}}(a), for every integer a coprime to n_{1} and n_{2}, is determined at the end of this section. We first settle the easy prime power case.

Proposition 3. Let p be a prime number and let a be an integer. Then we have

α_{p^{k}}(a) = O_{p}(a)

for every positive integer k.

Proof. Let k be a positive integer. If a is not coprime to p, then we have α_{p^{k}}(a) = α_{p}(a) = 0. Suppose now that a is coprime to p. By Proposition 2, the integer α_{p^{k}}(a) divides α_{p}(a). It remains to prove that α_{p}(a) divides α_{p^{k}}(a). The congruence

a^{α_{p^{k}} (a)·p^{k}} ≡ 1 (mod p^{k})

implies that

a^{α_{p^{k}} (a)·p^{k}} ≡ 1 (mod p),

and hence, by Fermat’s Little Theorem, it follows that

a^{α_{p^{k}} (a)·p} ≡ a^{α_{p^{k}} (a)·p^{k}} ≡ 1 (mod p).

Therefore α_{p}(a) divides α_{p^{k}}(a). Finally, we have

α_{p^{k}}(a) = α_{p}(a) = O_{p}(a^{p}) = O_{p}(a).

This completes the proof.

Remark 4. If p = 2, then, for every positive integer k, we obtain

α_{2^{k}}(a) = O_{2}(a) = \{ \begin{matrix}0, & for a even; \\ 1, & for a odd. \end{matrix}

Proposition 5. Let n_{1} and n_{2} be two coprime numbers and let a be an integer. Then α_{n_{1}n_{2}}(a) divides lcm(α_{n_{1}}(a), α_{n_{2}}(a)), the least common multiple of α_{n_{1}}(a) and α_{n_{2}}(a).

Proof. If gcd(a, n_{1}n_{2}) ≠ 1, then gcd(a, n_{1}) ≠ 1 or gcd(a, n_{2}) ≠ 1 and so

α_{n_{1}n_{2}}(a) = lcm(α_{n_{1}}(a), α_{n_{2}}(a)) = 0.

Suppose now that gcd(a, n_{1}n_{2}) = 1 and hence that the integers a, n_{1} and n_{2} are coprime pairwise. Let i ∈ {1, 2}. The congruences

a^{α_{n_{i}}(a)·n_{i}} ≡ 1 (mod n_{i})

imply that

a^{n_{1}n_{2} lcm(α_{n_{1}}(a),α_{n_{2}}(a))} ≡ 1 (mod n_{i}).

Therefore α_{n_{1}n_{2}}(a) divides lcm(α_{n_{1}}(a), α_{n_{2}}(a)) by the Chinese remainder theorem.

Let n_{1} and n_{2} be two positive integers such that

\{ \begin{matrix}rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩽ 1; \\ 2 rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩾ 2. \end{matrix}

By definition, we know that α_{n_{1}}(a) = α_{n_{2}}(a) = 0 for every integer a not coprime to n_{1} and n_{2}. We end this section by determining the exact relationship between α_{n_{1}}(a) and α_{n_{2}}(a) for every integer a coprime to n_{1} and n_{2}.

Theorem 6. Let n_{1} and n_{2} be two positive integers such that

\{ \begin{matrix}rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩽ 1; \\ 2 rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩾ 2. \end{matrix}

Then, for every integer a coprime to n_{1} and n_{2}, we have

α_{n_{1}}(a) = \frac{α_{n_{2}}(a)}{gcd (α_{n_{2}}(a), \frac{gcd(n_{1},R_{n_{2}}(a))}{n_{2}})}

This result is a corollary of the following theorem.

Theorem 7. Let n_{1} and n_{2} be two positive integers such that

\{ \begin{matrix}rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩽ 1; \\ 2 rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩾ 2. \end{matrix}

Then, for every integer a coprime to n_{1} and n_{2}, we have

O_{n_{1}}(a) = O_{n_{2}}(a) · \frac{n_{1}}{gcd(n_{1}, R_{n_{2}}(a))}.

The proof of this theorem is based on the following lemma.

Lemma 8. Let n be a positive integer and let a be an integer coprime to n. Let m be an integer such that rad(m)| rad n. Then, there exists an integer u_{m}, coprime to n if m is odd, or coprime to n/2 if m is even, such that

a^{O_{n}(a)·m} = 1 + u_{m} · R_{n}(a) · m.

Proof. We distinguish different cases based upon the parity of m. First, we prove the odd case by induction on m. If m = 1, then, by definition of the integer R_{n}(a), we have

a^{O_{n}(a)} = 1 + R_{n}(a).

Therefore the assertion is true for m = 1.

Now, let p be a prime factor of m and suppose that the assertion is true for the odd number m/p, i.e., there exists an integer u_{m/p}, coprime to n, such that

a^{O_{n}(a)· \frac{m}{p}} = 1 + u_{m/p} · R_{n}(a) · \frac{m}{p}.

Then, we obtain

a^{O_{n}(a)·m} \begin{matrix}= (a^{O_{n}(a)· \frac{m}{p}} )^{p} = (1 + u_{m/p} · R_{n}(a) · \frac{m}{p})^{p} \\ = 1 + u_{m/p} · R_{n}(a) · m + ∑_{k=2}^{p−1} \binom{p}{k} (u_{m/p} · R_{n}(a) · \frac{m}{p})^{k} + (u_{m/p} · R_{n}(a) · \frac{m}{p})^{p} \\ = \begin{matrix}1 + (u_{m/p} + ∑_{k=2}^{p−1} \frac{\binom{p}{k}}{p} · (u_{m/p})^{k} · R_{n}(a)^{k−1} · (\frac{m}{p})^{k−1}+ \\ +(u_{m/p})^{p} · \frac{R_{n}(a)^{p−1}}{p} · (\frac{m}{p})^{p−1}) · R_{n}(a) · m \end{matrix} \\ = 1 + u_{m} · R_{n}(a) · m. \end{matrix}

Since n divides R_{n}(a) which divides

u_{m} − u_{m/p} = ∑_{k=2}^{p−1} \frac{\binom{p}{k}}{p} · (u_{m/p})^{k} · R_{n}(a)^{k−1} · (\frac{m}{p})^{k−1} + (u_{m/p})^{p} · \frac{R_{n}(a)^{p−1}}{p} · (\frac{m}{p})^{p−1},

it follows that gcd(u_{m}, n) = gcd(u_{m/p}, n) = 1. This completes the proof for the odd case.

Suppose now that n and m are even. We proceed by induction on v_{2}(m). If v_{2}(m) = 1, then m/2 is odd and by the first part of this proof,

a^{\frac{m}{2} ·O_{n}(a)} = 1 + u_{m/2} · \frac{m}{2} · R_{n}(a)

where u_{m/2} is coprime to n and hence to n/2. Now assume that v_{2}(m) > 1 and that

a^{\frac{m}{2} ·O_{n}(a)} = 1 + u_{m/2} · \frac{m}{2} · R_{n}(a)

with u_{m/2} coprime to n/2. Then, we obtain

a^{O_{n}(a)·m} \begin{matrix}= (a^{O_{n}(a)· \frac{m}{2}} )^{2} = (1 + u_{m/2} · R_{n}(a) · \frac{m}{2})^{2} \\ = 1 + u_{m/2} · R_{n}(a) · m + (u_{m/2} · R_{n}(a) · \frac{m}{2})^{2} \\ = 1 + (u_{m/2} + (u_{m/2})^{2} · \frac{R_{n}(a)}{2} · \frac{m}{2}) · R_{n}(a)m \\ = 1 + u_{m} · R_{n}(a) · m. \end{matrix}

Since n/2 divides R_{n}(a)/2 which divides u_{m}−u_{m/2}, it follows that gcd(u_{m}, n/2) = gcd(u_{m/2}, n/2) = 1. This completes the proof.

We are now ready to prove Theorem 7.

Proof of Theorem 7. The proof is by induction on the integer n_{1}/n_{2}. If n_{1} = n_{2}, then we have

\frac{n_{1}}{gcd(n_{1}, R_{n_{2}}(a))} = \frac{n_{1}}{gcd(n_{1}, R_{n_{1}}(a))} = \frac{n_{1}}{n_{1}} = 1,

since R_{n_{1}}(a) is divisible by n_{1}, and thus the statement is true. Let p be a prime factor of n_{1} and n_{2} such that n_{2} divides n_{1}/p and suppose that

O_{n_{1}/p}(a) = O_{n_{2}}(a) · \frac{n_{1}/p}{gcd(n_{1}/p, R_{n_{2}}(a))}.

First, the congruence

a^{O_{n_{1}}(a)} ≡ 1 (mod n_{1})

implies that

a^{O_{n_{1}}(a)} ≡ 1 (mod \frac{n_{1}}{p})

and so O_{n_{1}/p}(a) divides O_{n_{1}}(a). We consider two cases.

First Case: v_{p}(n_{1}) ⩽ v_{p} (R_{n_{2}}(a)). Since n_{2} divides n_{1}/p, it follows that O_{n_{2}}(a) divides O_{n_{1}/p}(a). Let r = \frac{O_{n_{1}/p}(a)}{O_{n_{2}}(a)}. Hence

R_{n_{1}/p}(a) \begin{matrix}= a^{O_{n_{1}/p}(a)} − 1 = a^{O_{n_{2}}(a)·r} − 1 = (a^{O_{n_{2}}(a)} − 1) (∑_{k=0}^{r−1} a^{kO_{n_{2}}(a)}) \\ = R_{n_{2}}(a) (∑_{k=0}^{r−1} a^{kO_{n_{2}}(a)}) \end{matrix}

and so R_{n_{1}/p}(a) is divisible by R_{n_{2}}(a). This leads to

v_{p}(n_{1}) ⩽ v_{p} (R_{n_{2}}(a)) ⩽ v_{p} (R_{n_{1}/p}(a)) .

Therefore R_{n_{1}/p}(a) is divisible by n_{1} and hence we have

a^{O_{n_{1}/p}(a)} = 1 + R_{n_{1}/p}(a) ≡ 1 (mod n_{1}).

This implies that O_{n_{1}}(a) = O_{n_{1}/p}(a). Moreover, the hypothesis v_{p}(n_{1}) ⩽ v_{p} (R_{n_{2}}(a)) implies that gcd(n_{1}/p, R_{n_{2}}(a)) = gcd(n_{1}, R_{n_{2}}(a))/p. Finally, we obtain

O_{n_{1}}(a) = O_{n_{1}/p}(a) = O_{n_{2}}(a) · \frac{n_{1}/p}{gcd(n_{1}/p, R_{n_{2}}(a))} = O_{n_{2}}(a) · \frac{n_{1}}{gcd(n_{1}, R_{n_{2}}(a))}.

Second Case: v_{p}(n_{1}) > v_{p} (R_{n_{2}}(a)). If v_{2}(n_{1}) ⩽ 1, then (n_{1}/p)/ gcd(n_{1}/p, R_{n_{2}}(a)) is odd. Otherwise, if v_{2}(n_{1}) ⩾ 2, then v_{2}(n_{2}) ⩾ 2 and every integer coprime to n_{2}/2 is also coprime to n_{2}. In both cases, v_{2}(n_{1}) ⩽ 1 or v_{2}(n_{1}) ⩾ 2, we know, by Lemma 8, that there exists an integer u, coprime to n_{2}, such that

a^{O_{n_{1}/p}(a)} = a^{O_{n_{2}}(a)· \frac{n_{1}/p}{gcd(n_{1}/p,Rn_{2} (a))}} = 1 + u · R_{n_{2}}(a) · \frac{n_{1}/p}{gcd(n_{1}/p, R_{n_{2}}(a))} = 1 + u · \frac{R_{n_{2}}(a)}{gcd(n_{1}/p, R_{n_{2}}(a))} · \frac{n_{1}}{p} .

As v_{p} (R_{n_{2}}(a)) ⩽ v_{p} (n_{1}/p), it follows that R_{n_{2}}(a)/ gcd(n_{1}/p, R_{n_{2}}(a)) is coprime to p, and hence O_{n_{1}/p}(a) is a proper divisor of O_{n_{1}}(a) since

a^{O_{n_{1}/p}(a)} ≢ 1 (mod n_{1}).

Moreover, by Lemma 8 again, there exists an integer u_{p} such that

a^{O_{n_{1}/p}(a)·p} = 1 + u_{p} · R_{n_{1}/p}(a) · p ≡ 1 (mod n_{1}).

This leads to

O_{n_{1}}(a) = O_{n_{1}/p}(a) · p = O_{n_{2}}(a) · \frac{n_{1}}{gcd(n_{1}/p, R_{n_{2}}(a))} = O_{n_{2}}(a) · \frac{n_{1}}{gcd(n_{1}, R_{n_{2}}(a))}.

This completes the proof of Theorem 7.

We may view Theorem 7 as a generalization of Theorem 3.6 of [3], where n_{2} = p is an odd prime number and n_{1} = p^{k} for some positive integer k. Note that the conclusion of Theorem 7 fails in general in the case where v_{2}(n_{1}) ⩾ 2 and n_{2} = rad(n_{1}). For instance, for n_{1} = 24 = 3·2^{3}, n_{2} = 6 = 3·2 and a = 7, we obtain that O_{n_{1}}(a) = 2 while O_{n_{2}}(a)n_{1}/ gcd(n_{1}, R_{n_{2}}(a)) = 24/ gcd(24, 6) = 4.

We now turn to the proof of the main result of this paper.

Proof of Theorem 6. From Theorem 7, we obtain

α_{n_{1}}(a) \begin{matrix}= O_{n_{1}}(a^{n_{1}}) = \frac{O_{n_{1}}(a)}{gcd(O_{n_{1}}(a), n_{1})} = \frac{O_{n_{2}}(a) · \frac{n_{1}}{gcd(n_{1},R_{n_{2}}(a))}}{gcd (O_{n_{2}}(a) · \frac{n_{1}}{gcd(n_{1},R_{n_{2}}(a))}, n_{1})} \\ = \frac{O_{n_{2}}(a)}{gcd(O_{n_{2}}(a), n_{1}, R_{n_{2}}(a))}. \end{matrix}

Thus,

\frac{α_{n_{2}}(a)}{α_{n_{1}}(a)} = \frac{\frac{O_{n_{2}}(a)}{gcd(O_{n_{2}}(a),n_{2})}}{\frac{O_{n_{2}}(a)}{gcd(O_{n_{2}}(a),n_{1},R_{n_{2}}(a))}} = \frac{gcd(O_{n_{2}}(a), n_{1}, R_{n_{2}}(a))}{gcd(O_{n_{2}}(a), n_{2})}

= gcd (\frac{O_{n_{2}}(a)}{gcd(O_{n_{2}}(a), n_{2})}, \frac{n_{2}}{gcd(O_{n_{2}}(a), n_{2})} · \frac{gcd(n_{1}, R_{n_{2}}(a))}{n_{2}}) .

Finally, since we have

gcd (\frac{O_{n_{2}}(a)}{gcd(O_{n_{2}}(a), n_{2})}, \frac{n_{2}}{gcd(O_{n_{2}}(a), n_{2})}) = \frac{gcd(O_{n_{2}}(a), n_{2})}{gcd(O_{n_{2}}(a), n_{2})} = 1,

it follows that

\frac{α_{n_{2}}(a)}{α_{n_{1}}(a)} = gcd (\frac{O_{n_{2}}(a)}{gcd(O_{n_{2}}(a), n_{2})}, \frac{gcd(n_{1}, R_{n_{2}}(a))}{n_{2}}) = gcd (α_{n_{2}}(a), \frac{gcd(n_{1}, R_{n_{2}}(a))}{n_{2}}) .

Thus, the determination of α_{n} is reduced to the case where n is square-free.

Corollary 9. Let n be a positive integer such that v_{2}(n) ⩽ 1. Then, for every integer a, coprime to n, we have

α_{n}(a) = \frac{α_{rad(n)}(a)}{gcd (α_{rad(n)}(a), \frac{gcd(n,R_{rad(n)}(a))}{rad(n)})}.

Corollary 10. Let n be a positive integer such that v_{2}(n) ⩾ 2. Then, for every integer a, coprime to n, we have

α_{n}(a) = \frac{α_{2 rad(n)}(a)}{gcd (α_{2 rad(n)}(a), \frac{gcd(n,R_{2 rad(n)}(a))}{2 rad(n)})}.

3 The arithmetic function β_{n}

First, we can observe that, by definition of the functions α_{n} and β_{n}, we have

α_{n}(a) = β_{n}(a) = 0

for every integer a not coprime to n and

\frac{α_{n}(a)}{β_{n}(a)} ∈ \{1, 2\}

for every integer a coprime to n. There is no general formula known to compute α_{n}(a)/β_{n}(a) but, however, we get the following proposition.

Proposition 11. Let n_{1} and n_{2} be two positive integers such that rad(n_{1}) = rad(n_{2}). Let a be an integer coprime to n_{1} and n_{2}. If v_{2}(n_{1}) ⩽ 1, then we have

\frac{α_{n_{1}}(a)}{β_{n_{1}}(a)} = \frac{α_{n_{2}}(a)}{β_{n_{2}}(a)}.

If v_{2}(n_{1}) ⩾ 2, then we have

α_{n_{1}}(a) = β_{n_{1}}(a).

Proof. Let n_{1} be a positive integer such that v_{2}(n_{1}) ⩽ 1 and a be an integer coprime to n_{1}. Let p be an odd prime factor of n_{1} such that v_{p}(n_{1}) ⩾ 2. We will prove that

\frac{α_{n_{1}}(a)}{β_{n_{1}}(a)} = \frac{α_{n_{1}/p}(a)}{β_{n_{1}/p}(a)}.

If α_{n_{1}}(a) = 2β_{n_{1}}(a), then

a^{β_{n_{1}}(a)·n_{1}} ≡ −1 (mod n_{1})

and thus

a^{β_{n_{1}}(a)·p· \frac{n_{1}}{p}} ≡ −1 (mod \frac{n_{1}}{p}).

This implies that α_{n_{1}/p}(a) = 2β_{n_{1}/p}(a). Conversely, if α_{n_{1}/p}(a) = 2β_{n_{1}/p}(a), then we have

a^{β_{n_{1}/p}(a)· \frac{n_{1}}{p}} ≡ −1 (mod \frac{n_{1}}{p}).

Since v_{p}(n_{1}) ⩾ 2, it follows that

a^{β_{n_{1}/p}(a)· \frac{n_{1}}{p}} ≡ −1 (mod p)

and thus

a^{β_{n_{1}/p}(a)·n_{1}}+1 = 1−(−a^{β_{n_{1}/p}(a)· \frac{n_{1}}{p}} )^{p} = (1 + a^{β_{n_{1}/p}(a)· \frac{n_{1}}{p}} ) ∑_{k=0}^{p−1} (−a^{β_{n_{1}/p}(a)· \frac{n_{1}}{p}} )^{k} ≡ 0 (mod n_{1}).

This implies that α_{n_{1}}(a) = 2β_{n_{1}}(a). Continuing this process we have

\frac{α_{n_{1}}(a)}{β_{n_{1}}(a)} = \frac{α_{rad(n_{1})}(a)}{β_{rad(n_{1})}(a)}

and since rad(n_{1}) = rad(n_{2}),

\frac{α_{n_{1}}(a)}{β_{n_{1}}(a)} = \frac{α_{n_{2}}(a)}{β_{n_{2}}(a)}.

Now, let n_{1} be a positive integer such that v_{2}(n_{1}) ⩾ 2, and let a be a non-zero integer. Suppose that we have α_{n_{1}}(a) = 2β_{n_{1}}(a). Since

a^{β_{n_{1}}(a)·n_{1}} ≡ −1 (mod n_{1})

it follows that

(a^{β_{n_{1}}(a)· \frac{n_{1}}{4}} )^{4} ≡ −1 (mod 4)

in contradiction with

(a^{β_{n_{1}}(a)· \frac{n_{1}}{4}} )^{4} ≡ 1 (mod 4).

Thus α_{n_{1}}(a) = β_{n_{1}}(a).

If n is a prime power, then β_{n} = β_{rad(n)}, in analogy with Proposition 3 for α_{n}.

Proposition 12. Let p be a prime number and let a be an integer. Then we have

β_{p^{k}}(a) = β_{p}(a)

for every positive integer k.

Proof. This result is trivial for every integer a not coprime to p. Suppose now that a is coprime to p. For p = 2, then, by Proposition 11, we have

β_{2^{k}}(a) = α_{2^{k}}(a) = 1

for every positive integer k. For an odd prime number p ⩾ 3, Proposition 11 and Proposition 3 lead to

β_{p^{k}}(a) = \frac{α_{p^{k}}(a)}{α_{p}(a)} · β_{p}(a) = β_{p}(a)

for every positive integer k. This completes the proof.

Let n_{1} and n_{2} be two positive integers such that

\{ \begin{matrix}rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩽ 1; \\ 2 rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩾ 2. \end{matrix}

It immediately follows that β_{n_{1}}(a) = β_{n_{2}}(a) = 0 for every integer a not coprime to n_{1} and n_{2}. Finally, we determine the relationship between β_{n_{1}}(a) and β_{n_{2}}(a) for every integer a coprime to n_{1} and n_{2}.

Theorem 13. Let n_{1} and n_{2} be two positive integers such that

\{ \begin{matrix}rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩽ 1; \\ 2 rad(n_{1})|n_{2} and n_{2}|n_{1}, & if v_{2}(n_{1}) ⩾ 2. \end{matrix}

Let a be an integer coprime to n_{1} and n_{2}. Then, we have

β_{n_{1}}(a) = \frac{β_{n_{2}}(a)}{gcd (β_{n_{2}}(a), \frac{gcd(n_{1},R_{n_{2}}(a))}{n_{2}})}.

Proof. If v_{2}(n_{1}) ⩽ 1, then Theorem 6 and Proposition 11 lead to

\frac{β_{n_{2}}(a)}{β_{n_{1}}(a)} = \frac{α_{n_{2}}(a)}{α_{n_{1}}(a)} = gcd (α_{n_{2}}(a), \frac{gcd(n_{1}, R_{n_{2}}(a))}{n_{2}}) .

Since v_{2}(n_{2}) = v_{2}(n_{1}) ⩽ 1, it follows that gcd(n_{1}, R_{n_{2}}(a))/n_{2} is odd and hence, we have

\frac{β_{n_{2}}(a)}{β_{n_{1}}(a)} = gcd (α_{n_{2}}(a), \frac{gcd(n_{1}, R_{n_{2}}(a))}{n_{2}}) = gcd (β_{n_{2}}(a), \frac{gcd(n_{1}, R_{n_{2}}(a))}{n_{2}}) .

If v_{2}(n_{1}) ⩾ 2, then β_{n_{1}}(a) = α_{n_{1}}(a) and β_{n_{2}}(a) = α_{n_{2}}(a) by Proposition 11 and the result follows from Theorem 6.

Thus, as for α_{n}, the determination of β_{n} is reduced to the case where n is square-free.

Corollary 14. Let n be a positive integer such that v_{2}(n) ⩽ 1. Then, for every integer a, coprime to n, we have

β_{n}(a) = \frac{β_{rad(n)}(a)}{gcd (β_{rad(n)}(a), \frac{gcd(n,R_{rad(n)}(a))}{rad(n)})}.

Corollary 15. Let n be a positive integer such that v_{2}(n) ⩾ 2. Then, for every integer a, coprime to n, we have

β_{n}(a) = \frac{β_{2 rad(n)}(a)}{gcd (β_{2 rad(n)}(a), \frac{gcd(n,R_{2 rad(n)}(a))}{2 rad(n)})}.

4 Acknowledgments

The author would like to thank Shalom Eliahou for his help in preparing this paper. He also thanks the anonymous referee for his/her useful remarks.

References

[1] Jonathan Chappelon, On a problem of Molluzzo concerning Steinhaus triangles in finite cyclic groups, Integers 8 (2008), #A37.

[2] John C. Molluzzo, Steinhaus graphs, Theory and Applications of Graphs, Springer, volume 642 of Lecture Notes in Mathematics, Berlin / Heidelberg, 1978, pp. 394–402.

[3] Melvyn B. Nathanson, Elementary Methods in Number Theory, Springer, 2000, pp. 92–93.

2000 Mathematics Subject Classification: Primary 11A05; Secondary 11A07, 11A25. Keywords: multiplicative order, projective multiplicative order, balanced Steinhaus triangles, Steinhaus triangles, Molluzzo’s problem.

Received October 16 2009; revised version received January 20 2010. Published in Journal of Integer Sequences, January 27 2010.

Return to Journal of Integer Sequences home page.