INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A36

SOME PROPERTIES OF THE EULER QUOTIENT MATRIX

Ikhalfani Solan

Department of Mathematics and Computer Science, University of the West Indies, Jamaica

                       ikhalfani.solan@uwimona.edu.jm

Received: 2/15/06, Revised: 10/18/06, Accepted: 11/1/06, Published: 11/22/06

Abstract

Let a and m be integers such that (a, m) = 1. Let q_{a} = \frac{a^{ϕ(m)}−1}{m}. We call q_{a} the Euler Quotient of m with base a. This is called the Fermat Quotient when m is a prime. We consider some properties of the matrix of Euler Quotients reduced modulo m and show that these quotients are uniformly distributed modulo m.

1. Introduction

Let m and a be integers such that (m, a) = 1. Let q_{a} = \frac{a^{ϕ(m)}−1}{m}. We call q_{a} the Euler Quotient of m with base a. This is called the Fermat Quotient when m is a prime.

The following theorem summarizes some of the logarithmic properties of q_{a}.

Theorem 1.1 Let a, b ∈ ℤ and r ∈ ℕ with (a, m) = (b, m) = 1. Then

(a) q_{1} ≡ 0 mod m

(b) q_{ab} ≡ q_{a} + q_{b} mod m

(c) q_{a^{r}} ≡ rq_{a} mod m

Additional properties of q_{a} are given by the following generalization of a theorem of Wells [4]. It provides conditions when q_{a} vanishes modulo m.

Theorem 1.2 Let (a, m) = 1. If l and t are integers with (l, m) = 1 and α is a positive integer, then for a = l + tm^{α}

q_{a} ≡ q_{l} mod m + \frac{ϕ(m)t}{l}m^{α−1} (mod m^{α}).

2. The Euler Quotient Matrix

Let a be the i^{th} integer such that 1 ≤ a ≤ m and (a, m) = 1. The Euler Quotient Matrix, M_{m}, is the m×ϕ(m) matrix where the entries in column i are the least non-negative residues of q_{k}(mod m) for k ≤ m^{2} and k ≡ a(mod m). To be more precise we may call this the order 2 matrix and define the order r matrix for k ≤ m^{r}, r = 1, 2 …, to be the m^{r−1} × ϕ(m) matrix M_{m^{r}}.

Example 2.1 The Euler Quotient Matrices for m = 7, 12 and 9 are given below.

a= 1 2 3 4 5 6 1 0 2 6 4 6 1 2 6 5 1 2 3 2 3 5 1 3 0 0 3 4 4 4 5 5 4 4 5 3 0 0 3 1 5 6 2 3 2 1 5 6 7 1 6 4 6 2 0 a= 1 5 7 11 1 0 4 8 8 2 4 0 0 4 3 8 8 4 0 4 0 4 8 8 5 4 0 0 4 6 8 8 4 0 7 0 4 8 8 8 4 0 0 4 9 8 8 4 0 10 0 4 8 8 11 4 0 0 4 12 8 8 4 0 a= 1 2 4 5 7 8 1 0 7 5 8 4 3 2 6 1 2 2 1 6 3 3 4 8 5 7 0 4 0 7 5 8 4 3 5 6 1 2 2 1 6 6 3 4 8 5 7 0 7 0 7 5 8 4 3 8 6 1 2 2 1 6 9 3 4 8 5 7 0

Definition 2.2 Let π_{i} be the maximum size of the blocks of non-repeated entries in the i^{th} column. We call π_{i} the period of column i.

Theorem 2.3 The period of column i is given by π_{i} = \frac{m}{(ϕ(m),m)} for all i ≤ ϕ(m).

Proof. Suppose column i contains the least non-negative residue of q_{a}(mod m) such that a ≡ l + tm, l < m and (l, m) = 1. Then by Theorem 1.2, taking α = 1, we have q_{a} ≡ q_{l} + ϕ(m)tl^{−1}(mod m). The residues of q_{a} and q_{l} are equal precisely when m divides ϕ(m)t. This occurs for the first time when t = \frac{m}{(ϕ(m),m)} and subsequently for every integer multiple of t. Thus period of column i, π_{i} = \frac{m}{(ϕ(m),m)}.

Definition 2.4 We define the period of M_{m} to be the period of each column. That is, period of M_{m} is given by π_{m} = \frac{m}{(ϕ(m),m)}.

Let A_{r}^{m} = {q_{a} mod m : 0 ≤ a < m^{r}}. It is of interest to know the size of A_{r}^{m}. We list some properties of A_{r}^{m}.

(a) When m = p, a prime and r = 1, Vandiver [5] showed that \sqrt{p} ≤ |A_{1}^{p}| ≤ p − (1 + \sqrt{2p − 5})/2.

(b) When r = 2 and m is a prime or a strong psuedoprime |A_{2}^{m}| = m.

(c) I don’t know of any bounds apart from the trivial bounds for |A_{1}^{m}| when m is not prime.

(d) Let m be an integer with m > 2. Then we have that

\frac{m}{(m, ϕ(m))} ≤ |A_{2}^{m}| ≤ \frac{m}{(m, ϕ(m))} \frac{ϕ(m)}{2}.

We note that these bounds are the best possible. For example, when m is a prime, m = 4, or m = 12, the lower bound is achieved. When m = 3^{α}, α ≥ 2, the upper bound is achieved.

In fact we have

\frac{m}{(m, ϕ(m))} ≤ |A_{r}^{m}| ≤ \frac{m}{(m, ϕ(m))} \frac{ϕ(m)}{2}

whenever r ≥ 2.

Another area of interest is the vanishing of the quotients modulo m.

The following theorem appearing in [1] characterizes the elements of M_{m} and gives a formula for the number of vanishing quotients modulo m in M_{m}.

Theorem 2.5 Let m = p^{α_{1}} … p^{α_{k}} be the prime factorization of the integer m ≥ 2 and q the homomorphism from (ℤ/m^{2}ℤ)^{×} into (ℤ/mℤ, +) induced by the Euler quotient of m. For 1 ≤ r ≤ k put m_{r} = p^{α_{r}} and

d_{r} = \{ \begin{matrix}(m_{r}, 2 ∏_{j=1}^{k}(p_{j} − 1), when m_{r} = 2^{α_{r}}; α_{r} ≥ 2, \\ (m_{r}, ∏_{j=1}^{k}(p_{j} − 1), otherwise. \end{matrix}

Let d = ∏_{r=1}^{k} d_{r}. Then the image q((ℤ/m^{2}ℤ)^{×}) equals {td + mℤ : 0 ≤ t ≤ (m/d) − 1}; it is therefore isomorphic to (ℤ/(m/d)ℤ, +) for m > 2.

The above theorem immediately leads to the fact that the number of quotients to vanish modulo m in M_{m} is dϕ(m). A quick glance at the matrices for m = 7, 12 and 9 shows that a matrix may have columns containing no vanishing quotients. Using the period of the Euler quotient matrix and the total number of zero entries we obtain the following.

Theorem 2.6 Let d be as defined in Theorem 2.5 and m ≥ 2 be an integer. Then the number of columns of M_{m} containing zeros is given by \frac{dϕ(m)}{(ϕ(m),m)}.

Proof. The proof is just to recognize that the number of zeros in each column with a zero is given by \frac{m}{π_{m}} = (ϕ(m), m). Now, by Theorem 2.5 the total number of zeros in M_{m} is dϕ(m). Thus, there are exactly \frac{dϕ(m)}{(ϕ(m),m)} columns with a least one zero.

The formula for the number of columns without zeros is more interesting. This is given by ϕ(m)(1 − \frac{d}{(ϕ(m),m)}). If one notes that when m is a prime or a strong pseudoprime d = (ϕ(m), m) = 1, then the term \frac{d}{(ϕ(m),m)} can be considered as measure of the primeness of m.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A36 4

3. Sum of Quotients in the Columns and Rows of M_{m} In the next two theorems we, respectively, show that the sum of the entries in each column of M_{m} is congruent to 0 modulo m and that all rows sum to the same constant modulo m. Theorem 3.1 Let 1 ≤ a < m with (a, m) = 1. If k < m^{2} and k ≡ a(mod m), then

∑_{k≡a (mod m)} q_{k} ≡ 0 (mod m).

Proof. Let k = a + im, i < m. Then

∑_{k≡a (mod m)} q_{k} = \frac{1}{m} ∑_{i=0}^{m−1}(a + im)^{ϕ(m)−1} = ∑_{i=0}^{m−1} q_{a} + (\begin{matrix}ϕ(m) \\ 1 \end{matrix}) ∑_{i=0}^{m−1} i a^{ϕ(m)−1} +

m\{ (\begin{matrix}ϕ(m) \\ 2 \end{matrix}) ∑_{i=0}^{m−1} i^{2} a^{ϕ(m)−2} + ⋯ + (\begin{matrix}ϕ(m) \\ ϕ(m) \end{matrix}) ∑_{i=0}^{m−1} i^{2}(mi)^{ϕ(m)−2}\}

= mq_{a} + ϕ(m)m(m − 1)a^{ϕ(m)−1} ≡ 0 (mod m)

Theorem 3.2 ∑_{\begin{matrix}a=km+1 \\ (a,m)=1 \end{matrix}}^{(k+1)m−1} q_{a} ≡ ∑_{\begin{matrix}a=1 \\ (a,m)=1 \end{matrix}}^{m−1} q_{a}(mod m), for each k ∈ \{1, 2, …, m − 1\}.

Proof. For any k ∈ {1, 2, …, m − 1} we have

∑_{\begin{matrix}a=km+1 \\ (a,m)=1 \end{matrix}}^{(k+1)m−1}q_{a} = ∑_{\begin{matrix}a=1 \\ (a,m)=1 \end{matrix}}^{m−1} \frac{(km + a)^{ϕ(m)} − 1}{m}

= _{†} \frac{1}{m}\{ϕ(m)m^{ϕ(m)} + (\begin{matrix}ϕ(m) \\ 1 \end{matrix}) ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} m^{ϕ(m)−1}a + (\begin{matrix}ϕ(m) \\ 2 \end{matrix}) ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} m^{ϕ(m)−2}a^{2} + ⋯ +

(\begin{matrix}ϕ(m) \\ ϕ(m) − 1 \end{matrix}) ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} m a^{ϕ(m)−1} + ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}}(a^{ϕ(m)} − 1)\}

= ϕ(m)m^{ϕ(m)−1} + m^{ϕ(m)−2} (\begin{matrix}ϕ(m) \\ 1 \end{matrix}) ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} a + m^{ϕ(m)−3} (\begin{matrix}ϕ(m) \\ 2 \end{matrix}) ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} a^{2} + ⋯ +

ϕ(m) ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} a^{ϕ(m)−1} + ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} q_{a}

≡ ∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} q_{a} (mod m).

1† From this point on we suppressed, without loss, the use of k in the proof.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 6 (2006), #A36 5

4. Equidistribution of the Euler Quotients A result due to Heath-Brown [3] shows that the Fermat Quotients are uniformly distributed mod p for 1 ≤ a < p. This result generalized nicely to the Euler Quotients. We obtain Theorem 4.1 For any integers a, h with (a, m) = (h, m) = 1, we have

∑_{\begin{matrix}M<a<M+N \\ (a,m)=1 \end{matrix}} exp(\frac{hq_{a}}{m}) ≪ N^{1/2}m^{3/8} uniformly for M, N ≥ 1.

In particular

∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} exp(\frac{hq_{a}}{m}) ≪ m^{7/8} uniformly.

Proof. The proof is similar to that of Heath-Brown [3]. From Theorem 1.1 we have q_{ab} ≡ q_{a} + q_{b}(mod m) whenever (a, m) = (b, m) = 1. Thus

χ(a) = \{ \begin{matrix}0, (a, m) ≠ 1 \\ exp(\frac{hq_{a}}{p}), (a, m) = 1. \end{matrix}

is a non-principal character of order m. Hence we have

∑_{M<a<M+N} exp(\frac{hq_{a}}{m}) = ∑_{M<a<M+N} χ(a).

Now Burgess [2] proved that for composite modulus m

∑_{M<a<M+N} χ(a) ≪ N^{1/2}m^{3/8}.

Taking M = 1 and N = m, we obtain

∑_{\begin{matrix}a<m \\ (a,m)=1 \end{matrix}} exp(\frac{hq_{a}}{m}) ≪ m^{7/8}, uniformly.

Acknowledgments We would like to thank the referee for the valuable suggestions.

References

[1] Agoh, Dilcher and Skula, Fermat Quotients for Composite Moduli, Journal of Number Theory, 66, (1997), 29-50.

[2] D.A. Burgess, On the character sums and L-functions, II., Proc. London Math. Soc. (3), 13(1963), 524-536.

[3] D.R. Heath-Brown, An estimate for Heilbronn’s exponential sum, Analytic Number Theory: Vol 2. Birkhauser Boston, PM, 139, (1996),451-463.

[4] W. Johnson, On the nonvanishing of Fermat quotients (mod p), J. Reine Angew. Math., 292 (1977), 196-200.

[5] H.S. Vandiver, An aspect of the linear congruence with applications to the theory of Fermat quotients, Bull. Amer. Math. Soc 22 (1915), 61-67.