An Extension of a Result of Gauss to Finite Groups: A Linear Algebraic Approach

M. R. Pournaki^{*}

Abstract Let n be a positive integer and a be an integer. Gauss proved that ∑_{d|n} μ(n/d)a^{d} ≡ 0 (mod n), where μ is the Möbius function. This result generalizes both Fermat’s little theorem and Euler’s theorem. In this paper, a generalization of this result to finite groups is proved by methods of (multi-) linear algebra.

Keywords: Finite group, Congruence, Arithmetic function, Tensor product of vector spaces. 2000 Mathematics Subject Classification: Primary 20A05, 11A07, 11A25; Secondary 15A69.

1 Introduction

Fermat’s little theorem states that if p is a prime number, then

a^{p} ≡ a (mod p)  (1)

holds true for any integer a. One may ask what happens when p is not a prime. The answer to this question seems little known to mathematicians, even to number theorists. The reason for this seems to be its absence from most of the standard reference books. The missing result which is essentially due to Gauss is a beautiful one (see [2]): If n is any positive integer, then

∑_{d|n} μ(n/d)a^{d} ≡ 0 (mod n)  (2)

holds true for any integer a, where μ is the Möbius function defined by μ(1) = 1; μ(m) = 0, if m is not square-free; and μ(m) = (−1)^{r}, if m = p_{1} … p_{r}, where p_{i}’s are distinct primes.

Congruence (2) is a generalization of congruence (1); the left hand side of congruence (2) comes down to a^{n} − a if n is a prime number.

The history of congruence (2) is chronicled in Dickson [1, pp. 84-86]. — In his early draft of the planned eighth chapter of the Disquisitiones Arithmeticae, probably written in 1797 and never published in his lifetime – see the second volume of Gauss’s Collected Works (Göttingen 1863), pp. 212-240 –, C. F. Gauss treated congruences of polynomials with integer coefficients, modulo a prime number and an irreducible polynomial. In other words, he developed a theory of what we would treat today as general finite fields, or, equivalently, of residue fields of rings of cyclotomic integers. Warming up for this task, he counted the number of polynomials of a given degree modulo p by grouping them according to the degrees of their irreducible (modulo p) factors. As a consequence, he saw (loc. cit., p. 222, §347) that the left hand side of (2), for a prime number p instead of a, equals n times the number of irreducible (modulo p) polynomials of degree n. In particular, this left hand side is divisible by n. Gauss deduced a few variants of Fermat’s little theorem from this fact, admiring in passing the many diverse ways in which these theorems could be obtained.

*This research was in part supported by a grant from IPM.

According to Dickson, it was not until 1880-83 that four independent proofs of (2) for all a were published by Kantor, Weyr, Lucas, and Pellet (for precise references see [1]; see also [5]). In 1872, Petersen [3] proved Fermat’s little theorem (1) by using a combinatorial method, and Thue [6] in 1910 published a proof of congruence (2) by generalizing this idea. His proof is neatly summarized in [1, p. 82]. Thue uses congruence (2) to prove Euler’s generalization of congruence (1), which states

a^{φ(n)} ≡ 1 (mod n),  (3)

for relatively prime a, n, where φ(n) = n ∏_{p|n}(1 − 1/p) is Euler’s totient function. Szele [5] gives three proofs of congruence (2); his proofs are similar to those of Dickson, Thue, and Grandi, in 1895, 1910, and 1882, respectively. Finally, in 1986, Smyth [4] gives a coloring proof of a generalization of congruence (2).

2 The Main Theorem

As mentioned above, congruence (2) is a generalization of Fermat’s little theorem (1) and Euler’s theorem (3). In this paper, we prove the following generalization of congruence (2) to finite groups:

Main Theorem Let G be a finite group of order n and let ℂ^{×} be the multiplicative group of non-zero complex numbers. If f : G ⟶ ℂ^{×} is a group homomorphism, then

∑_{g∈G} f(g)a^{n/o(g)} ≡ 0 (mod n)  (4)

holds true for any integer a, where o(g) denotes the order of g.

With every choice of the finite group G and the homomorphism f : G ⟶ ℂ^{×} in the above general result, we get a polynomial expression in a that is guaranteed to be divisible by |G| for every integer a. Let us check that the Main Theorem really is a generalization of congruence (2):

Corollary 2.1 Let n be a positive integer and let a be an integer. Then

∑_{d|n} μ(n/d)a^{d} ≡ 0 (mod n)

holds true, where μ is the Möbius function.

Proof. Let G = ⟨x⟩ be a cyclic group of order n and let f : G ⟶ ℂ^{×} be the homomorphism sending x to exp(2πi/n). We find, writing (l, n) for the greatest common divisor of l and n:

∑_{g∈G} f(g)a^{n/o(g)} = ∑_{l=1}^{n} exp(2πi\frac{l}{n})a^{n/o(x^{l})}

= ∑_{l=1}^{n} exp(2πi\frac{l}{n})a^{(l,n)}

= ∑_{d|n} ( ∑_{\begin{matrix}l = 1 \\ (l, n) = d \end{matrix}}^{n} exp(2πi\frac{l}{n}))a^{d}

= ∑_{d|n} ( ∑_{\begin{matrix}l′ = 1 \\ (l′, n/d) = 1 \end{matrix}}^{n/d} exp(2πi\frac{l′d}{n}))a^{d}

= ∑_{d|n} μ(n/d)a^{d}.

Here the last identity follows from the general fact that μ(N) equals the sum over all primitive N-th roots of unity. (A very classical proof of this fact is obtained by repeating C. F. Gauss’s reasoning in §81 of the Disquisitiones Arithmeticae, where the same relation is established for N = p − 1, and for the primitive roots of unity which are the generators of the multiplicative group of the integers modulo p. — To be sure, the “Möbius function” was only called like this, with a reference to a 1832 paper of Möbius, by Mertens in 1875, i.e., 74 years after the appearance of Gauss’s seminal book.)

Now, by the Main Theorem, ∑_{g∈G} f(g)a^{n/o(g)} is divisible by n, so the above equalities imply that ∑_{d|n} μ(n/d)a^{d} is divisible by n, and thus the corollary follows. □

We can also obtain some generalizations of Fermat’s little theorem (1) by reducing congruence (4) to special cases. For example, if, in congruence (4), we consider f(g) = 1, for all g ∈ G, then we find that

∑_{g∈G} a^{n/o(g)} ≡ 0 (mod n)  (5)

holds true for any integer a, and any group G of order n. In the special case where G is cyclic of prime order p, G contains one element of order 1 and p − 1 elements of order p, thus congruence (5) yields 0 ≡ a^{p} + (p − 1)a ≡ a^{p} − a (mod p), for all integers a.

Applying congruence (5) to the case where G is cyclic of order n, we obtain the following corollary which generalizes Fermat’s little theorem (1).

Corollary 2.2 Let n be a positive integer and let a be an integer. Then

∑_{d|n} φ(n/d)a^{d} ≡ 0 (mod n)

holds true, where φ is the Euler’s totient function.

Proof. Let G = ⟨x⟩ be a cyclic group of order n. We have

∑_{g∈G} a^{n/o(g)} = ∑_{l=1}^{n} a^{n/o(x^{l})}

= ∑_{l=1}^{n} a^{(l,n)}

= ∑_{d|n} ( ∑_{\begin{matrix}l = 1 \\ (l, n) = d \end{matrix}}^{n} 1)a^{d}

= ∑_{d|n} φ(n/d)a^{d}.

On the other hand, by congruence (5), ∑_{g∈G} a^{n/o(g)} is divisible by n, so the above equalities imply that ∑_{d|n} φ(n/d)a^{d} is divisible by n as well, and thus the corollary follows. □

Let us now explain how (a generalization of) the Main Theorem may be deduced from the representation theory of finite groups. — Let G be an arbitrary finite group acting (on the right) faithfully on an arbitrary finite set S. For each group element g ∈ G, write c(g) for the number of orbits of ⟨g⟩ on S. Note that c(g) is the total number of cycles, including trivial “1-cycles”, when the permutation of S induced by g is written in cycle notation. Thus, for example, if G is the symmetric group on 5 letters in the natural action on five digits, and g is the element (1 2)(3 4) of order 2, then c(g) = 3. An important example occurs when S = G, with the finite group G acting on itself by right multiplication. In this case, one has c(g) = n/o(g), where n = |G| — this is the regular action.

Now look at the set M of all maps from S into a finite set A, where |A| = a. (It can be useful to think of the members of A as “colors” and the members of M as colorings of the points in S.) The group G then acts on the set M as follows: Let g ∈ G and m ∈ M. Then m · g is the new member of M defined by the formula (m · g)(x) = m(x · g^{−1}) for all x ∈ S. (It is routine to check that (m · g) · h = m · (gh) for g, h ∈ G, and so this really does define an action.)

Given g ∈ G, write π(g) for the number of members of M that are fixed by g, so that π is the permutation character of the action of G on M. How can we compute π(g)? It is easy to see that a coloring m is fixed by g if and only if all of the points in each orbit of ⟨g⟩ in its action on S are assigned the same color. It follows from this that π(g) = a^{c(g)}. In particular, in the regular action of a group G of order n, we have π(g) = a^{n/o(g)}.

Now the permutation character π is actually a character of G. It is possible, therefore, to write π as a non-negative integer linear combination of the irreducible characters of G. If χ is one of these irreducible characters, then it follows from the orthogonality relations for irreducible characters that the coefficient of χ in the permutation character π is exactly (1/n) ∑_{g∈G} χ(g)π(g), where n = |G|. In particular, ∑_{g∈G} χ(g)π(g) is a positive integer multiple of n for each choice of irreducible character χ. We see now that

∑_{g∈G} χ(g)a^{c(g)} = ∑_{g∈G} χ(g)π(g) ≡ 0 (mod n).

Now a group homomorphism f from G into the multiplicative group ℂ^{×} is also an irreducible character. In particular, we see that our Main Theorem is exactly the case of the general fact described here when the action is regular and the irreducible character is one-dimensional.

Therefore, most of the ideas of this paper are known, even in a more general form. But perhaps they are not as well known as they might be. In the next section we present a proof of the Main Theorem in a simpler language, using (multi-) linear algebra. We refer the reader to [2] for yet another approach.

3 Proof of the Main Theorem via Linear Algebra

We continue the paper by proving the Main Theorem. Without loss of generality, we may suppose G = {1, …, n}. In the sequel, we will be using G as an index set freely, writing simply “ij” for the composition of the group elements i and j. Firstly, we suppose a is a positive integer. Let V be an a-dimensional vector space over the complex field ℂ and ⊗^{n}V be the n-th tensor power of V. Write v_{1} ⊗ … ⊗ v_{n} for the decomposable tensor product of the indicated vectors. For each i ∈ G, define

A_{i} : ×^{n}V ⟶ ⊗^{n}V by

A_{i}(v_{1}, …, v_{n}) = v_{i1} ⊗ … ⊗ v_{in}.

It can be easily seen that A_{i} is an n-linear function, so by the universal property of the tensor product, there exists a unique linear transformation T_{i} : ⊗^{n}V ⟶ ⊗^{n}V which is completely determined by the rule

T_{i}(v_{1} ⊗ … ⊗ v_{n}) = v_{i1} ⊗ … ⊗ v_{in}.

The following lemma can be obtained by a straightforward computation.

Lemma 3.1 For each i, j ∈ G, T_{i}T_{j} = T_{ij}.

We now construct a linear transformation T : ⊗^{n}V ⟶ ⊗^{n}V by averaging:

T = \frac{1}{n} ∑_{i∈G} f(i)T_{i}.

Lemma 3.2 T is an idempotent. In particular, the trace tr T of T is a nonnegative integer.

Proof.

T^{2} = (\frac{1}{n} ∑_{i∈G} f(i)T_{i})(\frac{1}{n} ∑_{j∈G} f(j)T_{j})

= \frac{1}{n^{2}} ∑_{i∈G} ( ∑_{j∈G} f(i)f(j)T_{i}T_{j})

= \frac{1}{n^{2}} ∑_{i∈G} ( ∑_{j∈G} f(ij)T_{ij})

= \frac{1}{n^{2}} ∑_{i∈G} ( ∑_{j∈G} f(j)T_{j})

= \frac{1}{n} ∑_{j∈G} f(j)T_{j}

= T.

The trace of an idempotent is the dimension of its image, and therefore in particular a non-negative integer. □

We now compute the trace of T. The following lemma will be useful for this purpose. We put Γ_{a}^{n} = ×^{n}{1, …, a}.

Lemma 3.3 For each i ∈ G, the number of (γ_{1}, …, γ_{n}) ∈ Γ_{a}^{n} for which (γ_{1}, …, γ_{n}) = (γ_{i1}, …, γ_{in}) is equal to a^{n/o(i)}.

Proof. Suppose ⟨i⟩j_{1}, …, ⟨i⟩j_{s} are the distinct right cosets of ⟨i⟩ in the group G, where s = [G : ⟨i⟩] = n/o(i). It is easy to see that (γ_{1}, …, γ_{n}) = (γ_{i1}, …, γ_{in}) if and only if

γ_{ij_{t}} = … = γ_{i_{o(i)}j_{t}},

for all 1 ≤ t ≤ s. Therefore, the number of (γ_{1}, …, γ_{n}) ∈ Γ_{a}^{n} for which (γ_{1}, …, γ_{n}) = (γ_{i1}, …, γ_{in}) is equal to the number of (γ_{1}, …, γ_{n}) ∈ Γ_{a}^{n} such that

γ_{ij_{t}} = … = γ_{i_{o(i)}j_{t}},

for all 1 ≤ t ≤ s. But we have a choices for defining

γ_{ij_{t}} = … = γ_{i_{o(i)}j_{t}},

for each 1 ≤ t ≤ s, so the requested number is equal to a^{s} = a^{n/o(i)}. □

We now let B = {e_{1}, …, e_{a}} be a basis of V, therefore,

B^{⊗} = {e_{γ_{1}}⊗ … ⊗e_{γ_{n}}| (γ_{1}, …, γ_{n}) ∈ Γ_{a}^{n}}

is a basis of ⊗^{n}V. For each i ∈ G,

T_{i}(e_{γ_{1}}⊗ … ⊗e_{γ_{n}}) = e_{γ_{i1}}⊗ … ⊗e_{γ_{in}},

which shows that the elements of the matrix of T_{i} with respect to B^{⊗} are equal to 0 or 1. Therefore, tr T_{i} is equal to the number of (γ_{1}, …, γ_{n}) ∈ Γ_{a}^{n} for which e_{γ_{1}}⊗ … ⊗e_{γ_{n}} = e_{γ_{i1}}⊗ … ⊗e_{γ_{in}}. Lemma 3.3 now implies that tr T_{i} = a^{n/o(i)}. So,

tr T = tr (\frac{1}{n} ∑_{i∈G} f(i)T_{i})

= \frac{1}{n} ∑_{i∈G} f(i) tr T_{i}

= \frac{1}{n} ∑_{i∈G} f(i)a^{n/o(i)}.

Hence, by Lemma 3.2,

∑_{i∈G} f(i)a^{n/o(i)} ≡ 0 (mod n).

Thus the Main Theorem follows, but only for positive a. The following lemma will complete the proof of the Main Theorem.

Lemma 3.4 Let F (X) be a polynomial in ℂ[X] that takes on values in ℤ for non-negative integer values of X. Then F (X) takes on values in ℤ for all values of X in ℤ.

Proof. For integers k ≥ 0 define the polynomials \binom{X}{k} of degree k, as follows. For k = 0, this is just the constant polynomial 1 and for k > 0,

\binom{X}{k} = \frac{X(X − 1) … (X − k + 1)}{k!} .

Now these “binomial coefficients” form a basis for the full space ℂ[X], and thus we can write

F (X) = ∑_{k=0}^{m} a_{k}\binom{X}{k},

where the coefficients a_{k} are complex numbers and m is the degree of F. Since the binomial-coefficient polynomials \binom{X}{k} take on integer values for all integer values of X, it suffices to show that all of the coefficients a_{j} lie in ℤ for 0 ≤ j ≤ m. We prove this by induction on j, starting with j = 0. We have \binom{j}{j} = 1 and \binom{j}{k} = 0 for k > j, and thus

a_{j} = F (j) − ∑_{k=0}^{j−1} a_{k}\binom{j}{k}.

We see, therefore, that each coefficient a_{j} is an integer combination of the integer F (j) and the integers a_{k} for 0 ≤ k < j. The result then follows. □

We now apply this lemma to the polynomial

F (X) = \frac{1}{n} ∑_{i∈G} f(i)X^{n/o(i)} ∈ ℂ[X].

By the remarks just before Lemma 3.4, F (X) takes on values in ℤ for non-negative integer values of X. Therefore, by Lemma 3.4, F (X) takes on values in ℤ for all values of X in ℤ. In other words,

∑_{i∈G} f(i)a^{n/o(i)} ≡ 0 (mod n)

holds true for any integer a, thus the Main Theorem follows. □

Acknowledgment: This work was done while the author was a Postdoctoral Research Associate at the School of Mathematics, Institute for Studies in Theoretical Physics and Mathematics (IPM). He would like to thank the IPM for the financial support. Also he would like to express his thanks to Professor I. M. Isaacs for making useful suggestions and comments which led to improvement and simplification of the first draft.

References

[1] L. E. Dickson, “History of the Theory of Numbers”, vol. 1, Chelsea, New York, 1971.

[2] I. M. Isaacs, M. R. Pournaki, Generalizations of Fermat’s Little Theorem via Group Theory, Amer. Math. Monthly 112 (2005), no. 8, 734-740.

[3] J. Petersen, Tidsskrift for Mathematik (3) 2 (1872), 64-65.

[4] C. J. Smyth, A Coloring Proof of a Generalization of Fermat’s Little Theorem, Amer. Math. Monthly 93 (1986), no. 6, 469-471.

[5] T. Szele, Une Généralisation de la Congruence de Fermat, Mat. Tidsskr. B. 1948 (1948), 57-59.

[6] A. Thue, “Ein Kombinatorischer Beweis eines Satzes von Fermat”, In Selected Mathematical Papers of Axel Thue, Universitelsforlaget, 1977 (Originally Kra. Vidensk. Selsk, Skrifter. I. Mat. Nat. Kl. 1910, No. 3).

The Author’s Address

M. R. Pournaki, School of Mathematics, Institute for Studies in Theoretical Physics and Mathematics, P.O. Box 19395-5746, Tehran, Iran.

E-mail address: pournaki@ipm.ir