# 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.

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 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$.

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.

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