Category Archives: Number theory

Jordan-Hölder theorem

I am cramming for my algebra comprehensive exam so I will probably be posting stuff like this for a while.

A chain of subgroups \{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_n=G of a finite group G with H_{i+1}/H_i simple for all i is called a composition series of G. (The H_{i+1}/H_i are called composition factors.) The theorem in question states that every group has a composition series, and the composition factors in any two such series are unique up to reordering.

We can easily prove the first part of the theorem, that any finite group has a composition series, using the extreme principle. Let n\ge 0 be the largest integer for which there is a chain \{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_n=G of subgroups. (Such an n exists because there is trivially a chain with n=1, and our group is finite.) We claim that the composition factors in this case are simple. If not, WLOG H_{i+1}/H_i has a non-trivial normal subgroup \widetilde N. By correspondence, \widetilde N=N/H_i for some H_i\triangleleft N\triangleleft H_{i+1}. But then

\{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_i\triangleleft N\triangleleft H_{i+1}\cdots\triangleleft H_n=G

is a longer chain, a contradiction.

While the proof of the general theorem requires some non-trivial group theory (e.g. see here), we can easily prove the theorem for finite abelian groups using elementary number theory. For such a group, the orders of the composition factors must exactly be the prime factors—listed with multiplicity—of the order of the group. So the result follows immediately from the fundamental theorem of arithmetic.

Advertisements

Leave a comment

Filed under Algebra, Number theory

Midy’s theorem

Let b have order d modulo p. Then the base b expansion of 1/p has period L=(b^d-1)/p of length d. To see this, note that if b^d-1=mp, then

\displaystyle\frac 1p=\frac{m}{b^d-1}=\frac{m}{b^d}+\frac{m}{b^{2d}}+\frac{m}{b^{3d}}+\cdots.

Note also that aL<b^d for any 1\le a\le p-1. Hence a/p has period aL. Now suppose that d is even. Since b has order d modulo p, it follows that b^{d/2}\equiv -1\pmod p. Hence p-a\equiv b^{d/2}a\pmod p. This means that at their midpoints the two numbers aL and (p-a)L are mirror images of one another. This means that splitting aL midway into two equal parts and adding them gives b^{d/2}-1, i.e., a string of (b-1)‘s in base b. This is known as Midy’s theorem.

For example, with p=7 and b=10 we get d=6, and L=142857. Split L into two equal parts 142 and 857, adding which gives

142+857=999.

In general, if m is any divisor of d, then

\begin{aligned} b^d-1&=(b^m-1)(1+b^{d/m}+b^{2d/m}+\cdots+b^{(m-1)d/m})\\&\equiv 0\pmod p\end{aligned}

so

b^{d/m}+b^{2d/m}+\cdots+b^{(m-1)d/m}\equiv -1\pmod p

and so splitting L into m equal parts and adding them will always give a multiple of b^{d/m}-1.

Leave a comment

Filed under Number theory

Permutation of digits by multiplication

Here is an expository write-up of this post.

The number N=142857 is interesting because of the following property

\begin{aligned}N&=142857\\ 2N&=285714\\ 3N&=428571\\ 4N&=571428\\ 5N&=714285\\ 6N&=857142\end{aligned}

and 7N=999999. The last equation means that

\displaystyle\frac 17=0.\overline{142857}.

So multiplying N by 1,2,3,4,5,6 simply permutes the digits of N. As elements of S_6 these permutations correspond to (using cycle notation)

\hbox{id}, (153)(264), (165432), (135)(246), (123456), (14)(25)(36)

respectively. We can read off the following from this list.

  • Since (165432) and (123456) are full-length cycles, 3 and 5 are primitive roots modulo 7.
  • 2 and 4 have order 3 modulo 7, while 6 has order 2.

In general, if p is an odd prime and b is a positive integer with order d modulo p, then 1/p will have period (b^d-1)/p of length d in base b. This follows simply from observing that if b^d-1=mp then

\displaystyle\frac 1p=\frac{m}{b^d-1}=\frac{m}{b^d}+\frac{m}{b^{2d}}+\frac{m}{b^{3d}}+\cdots.

Now let b>p be a primitive root modulo p. We shall work in base b. Then 1/p will have period L=(b^{p-1}-1)/p of length p-1. Since the periods of 1/p,2/p,\dots,(p-1)/p are L,2L,\dots,(p-1)L, all of length p-1, which are all powers of some permutation of the digits of L, and no two of which are congruent modulo b, it follows that the digits of L are all distinct. So we’ve shown the following.

Theorem. If p is an odd prime and b>p is a primitive root modulo p, then the base b expansion of 1/p has period of length p-1 with distinct digits.

Taking p=7, b=10 gives our previous example. So the prime 7 in base 10 is indeed very special, since it is the only prime less than 10 for which 10 is a primitive root.

1 Comment

Filed under Number theory

A bound on the multiplicative order

Let n=p_1^{a_1}\cdots p_k^{a_k} factored uniquely into primes, and let a be an integer coprime to n. If we denote by \hbox{ord}_na the multiplicative order of a modulo n then Euler’s theorem tells us that \hbox{ord}_na\mid\phi(n), so that \hbox{ord}_na\le\phi(n). Can we do better?

Note that a^{p_i^{a_i-1}(p_i-1)}\equiv 1\pmod{p_i^{a_i}} for each i by Euler’s theorem. Hence

(*)\qquad\qquad\begin{aligned}\hbox{ord}_na&\le [p_1^{a_1-1}(p_1-1),\dots,p_k^{a_k-1}(p_k-1)]\\ &=\frac{\phi(n)}{(p_1^{a_1-1}(p_1-1),\dots,p_k^{a_k-1}(p_k-1))^{k-1}}\end{aligned}

using a result from this post. Now if 2\parallel n, then the GCD on the right-hand side is equal to 1. Otherwise 2 divides the GCD, so that

(**)\qquad\qquad\qquad\qquad\displaystyle\hbox{ord}_na\le\frac{\phi(n)}{2^{k-1}}=\frac{\phi(n)}{2^{\omega(n)-1}}.

By the Chinese Remainder Theorem we can choose a to be a primitive root modulo p_i^{a_i} for i=1,\dots,k simultaneously. Hence equality can be achieved in (*) for any n. Further, if one of the p_i is 2 and one is congruent to 3\pmod 4 then the GCD in (*) is exactly 2, so that equality is achieved in (**). So (**) is the best uniform bound if n\not\equiv 2\pmod 4, while if n\equiv 2\pmod 4 then \hbox{ord}_na\le \phi(n) is uniformly the best possible.

Leave a comment

Filed under Number theory

GCD and LCM via groups and rings

Let a and b be integers. Consider the ring

G=\{ax+by:x,y\in\mathbb Z\}.

This is a well-ordered group. So by a result in this post it is infinite cyclic. We call the positive generator (a,b) the greatest common divisor (GCD) of a and b.

Consider now the ring

L=\{m\in\mathbb Z:m is divisible by both a and b\}.

It is also a well-ordered group. Hence it is generated by a single positive element [a,b], called the least common multiple (LCM) of a and b.

Let

M_a=\{ax:x\in\mathbb Z\} and M_b=\{by:y\in\mathbb Z\}.

M_a, M_b and L are subings of G. Moreover, G=M_a+M_b and L=M_a\cap M_b. So by the Chinese remainder theorem,

G/L\cong G/M_a\times G/M_b,

which can be written as

(\mathbb Z/L)/(\mathbb Z/G)\cong(\mathbb Z/M_a)/(\mathbb Z/G)\times(\mathbb Z/M_b)/(\mathbb Z/G)

by the third isomorphism theorem. The groups in brackets are all finite groups of orders [a,b], (a,b), a and b. Hence [a,b]/(a,b)=ab/(a,b)^2, i.e.,

\boxed{ab=(a,b)[a,b]}.


In general, let a_1,\dots,a_n\in\mathbb Z. As before, we can define

G=\{a_1x_1+\cdots+a_nx_n:x_i\in\mathbb Z\ \forall i\}

L=\{m\in\mathbb Z:m is divisible by a_i\ \forall i\}

M_i=\{a_ix:x\in\mathbb Z\} for i=1,\dots,n.

Then G=M_1+\cdots+M_n and L=M_1\cap\cdots\cap M_n. As before,

G/L\cong\displaystyle\prod_{i=1}^n(G/M_i),

i.e.,

(*)\qquad\qquad\qquad (\mathbb Z/L)/(\mathbb Z/G)\cong\displaystyle\prod_{i=1}^n((\mathbb Z/M_i)/(\mathbb Z/G)).

So \displaystyle [a_1,\dots,a_n]/(a_1,\dots,a_n)=a_1\cdots a_n/(a_1,\dots,a_n)^n, i.e.

\boxed{a_1\cdots a_n=(a_1,\dots,a_n)^{n-1}[a_1,\dots,a_n]}.


If we replace \mathbb Z by \mathcal O_K for any number field K, then (*) takes the form

(\mathcal O_K/L)/(\mathcal O_K/G)\cong\displaystyle\prod_{i=1}^n((\mathcal O_K/M_i)/(\mathcal O_K/G)).

Taking cardinalities gives the following equation in terms of ideal norms

N(L)/N(G)=\displaystyle\prod_{i=1}^n(N(M_i)/N(G)).

Thus

\boxed{N_{K/\mathbb Q}(a_1\cdots a_n)=N(G)^{n-1}N(L)}.

1 Comment

Filed under Algebra, Number theory