View Single Post
 2017-01-07, 13:15 #1 Nick     Dec 2012 The Netherlands 6E516 Posts Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic Last time, we introduced the idea of a group, which is any set that comes with a binary operation satisfying 3 conditions: the operation is associative, the set has a neutral/identity element, and each element of the set has an inverse. This time, we develop a little more Group Theory and then see how it gives us extra insight into Number Theory. Let $$G$$ be a group and $$g\in G$$ an element. Using the group's binary operation, we can combine $$g$$ with itself, getting $$gg$$ which we write as $$g^2$$, $$ggg$$ which we write as $$g^3$$, etc. Similarly, we write $$g^{-2}$$ for $$g^{-1}g^{-1}$$, $$g^{-3}$$ for $$g^{-1}g^{-1}g^{-1}$$, etc. More formally, for each integer $$n$$, we define $$g^n$$ to be the following element of $$G$$: if $$n=0$$ then $$g^n=1$$ (i.e. the neutral element of the group $$G$$); if $$n>0$$ then $$g^n=g^{n-1}g$$; if $$n<0$$ then $$g^n=(g^{-1})^{-n}$$. Note that this is consistent with our notation of $$g^{-1}$$ for the inverse of $$g$$, and agrees with the usual definition of powers if the elements are numbers. Proposition 74 Let $$G$$ be a group and $$a\in G$$. Then, for all integers $$m,n$$, i) $$a^{m+n}=a^ma^n$$; and ii) $$a^{(mn)}=(a^m)^n$$. proof We first claim that, for all integers $$n$$, $$(a^{-1})^n=a^{-n}$$. If $$n=0$$ then $$(a^{-1})^n=1=a^{-n}$$. If $$n>0$$ then (by definition) $$a^{-n}=(a^{-1})^{--n}=(a^{-1})^n$$. And if $$n<0$$ then $$(a^{-1})^n=((a^{-1})^{-1})^{-n}=a^{-n}$$. This proves the claim. i) Suppose $$m\geq 0$$ and $$n\geq 0$$. Induction on $$n$$. In the case $$n=0$$: $$a^ma^n=a^ma^0=a^m\cdot 1=a^m=a^{m+0}=a^{m+n}$$. Take any integer $$N>0$$ and suppose (i) holds for all non-negative $$n0$$ and suppose (i) holds for all $$m0$$ and suppose (ii) holds for all non-negative $$nj$$ but $$g^i=g^j$$. Then $$0j$$ such that $$h^i=h^j$$. Putting $$n=i-j$$, we have $$h^n=h^ih^{-j}=h^jh^{-j}=1$$ with $$n>0$$. If $$n=1$$ then $$h=1$$ and $$h^{-1}=h\in H$$, as required. Suppose $$n>1$$. Then $$n-1>0$$ so $$h^{n-1}\in H$$. And $$hh^{n-1}=h^n=1=hh^{-1}$$ so (by proposition 73) $$h^{-1}=h^{n-1}\in H$$. This proves the claim. For any $$x,y\in H$$, we have $$y^{-1}\in H$$ (by the claim) and $$H$$ is closed under the binary operation (by assumption) so $$xy^{-1}\in H$$. It follows by proposition 78 that $$H$$ is a subgroup of $$G$$. ∎ Let $$H$$ be a subgroup of a group $$G$$. For each element $$g\in G$$, we define $$gH=\{gh:h\in H\}$$, called a left coset of $$H$$ in $$G$$, and $$Hg=\{hg:h\in H\}$$, called a right coset of $$H$$ in $$G$$. Proposition 80 Let $$H$$ be a subgroup of a group $$G$$ and define a relation $$\sim$$ on $$G$$ by $$x\sim y\Leftrightarrow y^{-1}x\in H$$. Then $$\sim$$ is an equivalence relation on $$G$$ and, for each $$g\in G$$, the equivalence class of $$g$$ is precisely $$gH$$. proof Take any $$x,y,z\in G$$. Then $$x^{-1}x=1\in H$$ as $$H$$ is a subgroup, so $$x\sim x$$. If $$x\sim y$$ then $$y^{-1}x\in H$$ and, as a subgroup, $$H$$ contains the inverses of all its elements so, by lemma 76, $$x^{-1}y=(y^{-1}x)^{-1}\in H$$ and therefore $$y\sim x$$. If $$x\sim y\sim z$$ then $$y^{-1}x\in H$$ and $$z^{-1}y\in H$$, and $$H$$ is closed under the group's binary operation (since $$H$$ is a subgroup) so $$z^{-1}x=z^{-1}yy^{-1}x\in H$$ hence $$x\sim z$$. Thus $$\sim$$ is an equivalence relation on $$G$$. Take any $$g\in G$$, and write $$[g]$$ for the equivalence class of $$g$$ under $$\sim$$, i.e. $$[g]=\{x\in G:x\sim g\}$$. Then, for any $$x\in [g]$$, we have $$x\sim g$$ so $$g^{-1}x=h$$ for some $$h\in H$$ and therefore $$x=gh\in gH$$. Thus $$[g]\subset gH$$. Conversely, for any $$x\in gH$$, we have $$x=gh$$ for some $$h\in H$$ so $$g^{-1}x=g^{-1}gh=h\in H$$ and therefore $$x\sim g$$ so $$x\in [g]$$. Thus $$gH\subset [g]$$ as well,hence $$[g]=gH$$. ∎ In the same way, if $$H$$ is a subgroup of a group $$G$$ and $$g\in G$$ then the right coset $$Hg$$ is the equivalence class of $$g$$ under the relation $$x\sim y\Leftrightarrow xy^{-1}\in H$$. Proposition 81 Let $$H$$ be a subgroup of a group $$G$$ and $$g\in G$$. Then the function $$f:H\rightarrow gH,x\mapsto gx$$ is a bijection. proof For any $$x,y\in H$$, if $$f(x)=f(y)$$ then $$gx=gy$$ so, by proposition 73, $$x=y$$. Thus $$f$$ is injective. And every element of $$gH$$ can be expressed in the form $$gh$$ for some $$h\in H$$ (by definition) with $$gh=f(h)$$ so $$f$$ is surjective as well, and hence bijective. ∎ Notation Let $$H$$ be a subgroup of a group $$G$$. We write $$G/H$$ for the set of all left cosets of $$H$$ in $$G$$, and $$H\backslash G$$ for the set of all right cosets of $$H$$ in $$G$$. Proposition 82 Let $$H$$ be a subgroup of a group $$G$$, and define a function $$f:G/H\rightarrow H\backslash G,gH\mapsto Hg^{-1}$$. Then $$f$$ is a well-defined bijection. proof For any $$x,y\in G$$, if $$xH=yH$$ then $$y^{-1}x\in H$$ and $$y^{-1}x=y^{-1}(x^{-1})^{-1}$$ so $$Hx^{-1}=Hy^{-1}$$. Thus the definition of $$f$$ is independent of the chosen representative of the coset, making it well-defined. For any $$x,y\in G$$, if $$f(xH)=f(yH)$$ then $$Hx^{-1}=Hy^{-1}$$ so $$y^{-1}x=y^{-1}(x^{-1})^{-1}\in H$$ and therefore $$xH=yH$$. Thus $$f$$ is injective. Also, any element of $$H\backslash G$$ has the form $$Hy$$ for some $$y\in G$$ and, putting $$x=y^{-1}$$, we have $$f(xH)=Hx^{-1}=H(y^{-1})^{-1}=Hy$$. So $$f$$ is surjective, too, making it bijective. ∎ Notation Let $$H$$ be a subgroup of a group $$G$$. By proposition 82, the number of left cosets of $$H$$ in $$G$$ is finite if and only if the number of right cosets of $$H$$ in $$G$$ is finite, and then both numbers are equal (exercise 28). In that case, we call this positive integer the index of $$H$$ in $$G$$, written $$[G:H]$$. Theorem 83 (Lagrange's theorem) Let $$G$$ be a finite group and $$H$$ a subgroup of $$G$$. Then $$\#G=\#H\cdot [G:H]$$. In particular, the order of $$H$$ divides the order of $$G$$. proof The left cosets of $$H$$ in $$G$$ are the equivalence classes under the relation $$\sim$$ of propostion 80, so they form a partition of $$G$$ (by proposition 35). And the number of elements in each left coset equals the number of elements in $$H$$ by proposition 81, so the number of elements in $$G$$ is the number of elements in $$H$$ times the number of left cosets of $$H$$ in $$G$$. ∎ Corollary 84 Let $$G$$ be a finite group and $$g\in G$$. Then the order of the element $$g$$ divides the order of the group $$G$$. proof Let $$n$$ be the order of $$g$$ in $$G$$, which is finite since $$G$$ is a finite group, and let $$H=\{1,g,g^2,g^3,\ldots,g^{n-1}\}$$. Then $$H$$ is non-empty and closed under the group's binary operation (since $$g^n=1$$) so $$H$$ is a subgroup of $$G$$ by proposition 79. And the order of $$H$$ is $$n$$ (proposition 75) so $$n$$ divides $$\#G$$ by Lagrange's theorem. ∎ Example Let $$n$$ be a positive integer and $$G$$ the unit group $$(\mathbb{Z}/n\mathbb{Z})^*$$ of the integers modulo $$n$$. Then the order of $$G$$ is $$\phi(n)$$ (where $$\phi$$ is Euler's function) and, for any integer $$a$$ with $$\gcd(a,n)=1$$, $$\bar{a}$$ is an element of $$G$$ so the order of $$\bar{a}$$ divides $$\phi(n)$$ hence $$\bar{a}^{\phi(n)}=1\in G$$ (proposition 75). Thus Fermat's little theorem becomes trivial once we understand Lagrange's theorem. We call a group $$G$$ cyclic if it has an element $$g\in G$$ with the following property: for all $$x\in G$$ there exists an integer $$n$$ such that $$g^n=x$$. Thus, in a cyclic group, every element is simply a power of some fixed element $$g$$, and we say that $$G$$ is generated by $$g$$. Proposition 85 Let $$p$$ be a prime number and $$G$$ a group of order $$p$$. Then $$G$$ is cyclic. proof There exists $$g\in G$$ with $$g\neq 1$$ (since $$\#G=p\geq 2$$). By corollary 84, the order of $$g$$ divides $$p$$, so it is 1 or $$p$$ itself, as $$p$$ is prime. But the neutral element $$1\in G$$ is the unique element with order 1, so $$g$$ has order $$p$$. By proposition 75, the powers of $$g$$ give $$p$$ distinct elements of $$G$$, namely $$1=g^0,g=g^1,g^2,g^3,\ldots,g^{p-1}$$. But $$G$$ has only $$p$$ elements, so this list includes them all, hence $$G$$ is cyclic. ∎ Proposition 86 Let $$G$$ be a finite cyclic group of order $$n$$ generated by $$g\in G$$. Then, for each positive integer $$d$$ which divides $$n$$, $$G$$ has a subgroup of order $$d$$ which is also cyclic, generated by $$g^{\frac{n}{d}}$$, and $$G$$ has no other subgroups. proof We have $$G=\{1,g,g^2,\ldots,g^{n-1}\}$$ (all distinct elements) with $$g^n=1$$. Take any positive divisor $$d$$ of $$n$$ and let $$m$$ be the positive integer $$\frac{n}{d}$$. Let $$H=\{1,g^m,g^{2m},\ldots,g^{(d-1)m}\}$$. By proposition 79, $$H$$ is a subgroup of $$G$$ (since $$g^{dm}=1$$), it has precisely $$d$$ distinct elements, and is cyclic, generated by $$g^m=g^{\frac{n}{d}}$$. Now take any subgroup $$K$$ of $$G$$, and let $$d=\#K$$. By Lagrange's theorem, $$d$$ divides $$n$$, so $$dm=n$$ for some positive integer $$m$$. Each element of $$K$$ has the form $$g^i$$ for some $$i\in\{0,1,\ldots,n-1\}$$ and $$g^{id}=1$$ (corollary 84) so $$n|id$$ (proposition 75). But $$n=dm$$ so $$i$$ is a multiple of $$m$$. As $$K$$ contains $$d$$ elements and there are only $$d$$ multiples of $$m$$ in the set $$\{0,1,\ldots,n-1\}$$, it follows that $$K=\{1,g^m,g^{2m},\ldots,g^{(d-1)m}\}$$, which is the cyclic subgroup of $$G$$ generated by $$g^m=g^{\frac{n}{d}}$$. ∎ A cyclic group may have more than 1 element that generates it. Proposition 87 Let $$G$$ be a finite cyclic group of order $$n$$ generated by $$g\in G$$. Then, for all $$i\in\mathbb{Z}$$, $$g^i$$ also generates $$G$$ if and only if $$\gcd(i,n)=1$$. proof For any integer $$i$$, the element $$g^i$$ generates $$G$$ if and only if $$(g^i)^k=g$$ for some integer $$k$$ (since all elements of $$G$$ can be written as powers of $$g$$). And, for any integer $$k$$, $$g^{ik}=g$$ if and only if $$g^{ik-1}=1$$ which, by proposition 75, holds if and only if $$n|ik-1$$, i.e. $$ik\equiv 1\pmod{n}$$. So such a $$k$$ exists if and only if $$\bar{i}$$ is a unit in the integers modulo $$n$$, which is the case if and only if $$\gcd(i,n)=1$$ by proposition 32. ∎ Proposition 88 Let $$G$$ be a finite cyclic group of order $$n$$. Then, for each positive divisor $$d$$ of $$n$$, $$G$$ contains precisely $$\phi(d)$$ distinct elements of order $$d$$ (where $$\phi$$ is Euler's function). proof Take any positive integer $$d$$ that divides $$n$$. By proposition 86, $$G$$ has a cyclic subgroup $$H$$ of order $$d$$. Let $$g$$ be a generator of $$H$$, giving $$H=\{1,g,g^2,\ldots,g^{d-1}\}$$. For any element $$x\in G$$ of order $$d$$, the subset $$\{1,x,x^2,\ldots,x^{d-1}\}$$ is a subgroup of $$G$$ (by proposition 79) but $$H$$ is the unique subgroup of $$G$$ with order $$d$$ (by proposition 86), so this subset is $$H$$, and therefore $$H$$ is generated by $$x$$. Conversely, any element $$x\in H$$ that generates the cyclic subgroup $$H$$ has order $$d$$, so the elements of $$G$$ with order $$d$$ are precisely those elements of the cyclic subgroup $$H$$ which generate $$H$$. For each $$i\in\{0,1,\ldots,d-1\}$$, $$g^i$$ is a generator of $$H$$ if and only if $$\gcd(i,d)=1$$ (by proposition 87), and this holds if and only if $$\bar{i}$$ is a unit in the integers modulo $$d$$ (by proposition 32), so the number of elements of $$G$$ with order $$d$$ equals the number of units in the integers modulo $$d$$, which is $$\phi(d)$$. ∎ Corollary 89 (Gauss) Let $$n$$ be a positive integer, $$r$$ the number of positive integers that divide $$n$$, and $$d_1,d_2,\ldots,d_r$$ the positive divisors themselves. Then $$\phi(d_1)+\phi(d_2)+\ldots +\phi(d_r)=n$$. proof There exists a finite cyclic group $$G$$ of order $$n$$ (exercise 69 below). By proposition 88, it has $$\phi(d_1)$$ elements of order $$d_1$$, $$\phi(d_2)$$ elements of order $$d_2$$, etc. As the order of each element of $$G$$ divides $$n$$ by corollary 84, and the group has precisely $$n$$ elements, it follows that $$\phi(d_1)+\phi(d_2)+\ldots +\phi(d_r)=n$$. ∎ Theorem 90 For all prime numbers $$p$$, the unit group $$(\mathbb{Z}/p\mathbb{Z})^*$$ of the integers modulo $$p$$ is cyclic. proof Take any prime number $$p$$, and let $$G=(\mathbb{Z}/p\mathbb{Z})^*$$, the unit group of the integers modulo $$p$$. Let $$n=\phi(p)$$, the order of $$G$$ (which is $$p-1$$). Take any $$a\in G$$, let $$d$$ be the order of the element $$a$$, and define $$H=\{1,a,a^2,\ldots,a^{d-1}\}$$. Then every element of $$H$$ satisfies the equation $$x^d-1=0$$ (by proposition 75). But there are no zero divisors in the integers modulo $$p$$ (since $$p$$ is a prime number) so this equation has at most $$d$$ solutions (by propostion 60), and therefore $$H$$ contains all of them. Moreover, any element of $$G$$ with order $$d$$ satisfies this equation, so $$H$$ contains all elements of $$G$$ which have order $$d$$. And $$H$$ contains precisely $$\phi(d)$$ distinct elements of order $$d$$ (by proposition 88), so $$G$$ has exactly $$\phi(d)$$ elements of order $$d$$. Let $$d_1,d_2,\ldots,d_r$$ be the distinct positive integers dividing $$n$$. We have shown, for each $$i\in\{1,2,\ldots,r\}$$ that if $$G$$ contains an element of order $$d_i$$ then it contains precisely $$\phi(d_i)$$ elements of order $$d_i$$. But the order of every element of $$G$$ divides $$n$$ (corollary 84) and $$\phi(d_1)+\phi(d_2)+\ldots +\phi(d_r)=n$$ (corollary 89) so, for each $$i\in\{1,2,\ldots,r\}$$, if $$G$$ does not contain an element of order $$d_i$$ then $$G$$ has fewer than $$n$$ elements, a CONTRADICTION. Thus $$G$$ has an element of order $$d$$ for every positive integer $$d$$ that divides $$n$$ and, in particular, $$G$$ has an element $$g$$ of order $$n$$. It follows that $$G=\{1,g,g^2,\ldots,g^{n-1}\}$$, making $$G$$ cyclic. ∎ Example Every non-zero integer modulo 7 is a power of 3: $\begin{eqnarray*} \bar{1} & = & \bar{3}^6 \\ \bar{2} & = & \bar{3}^2 \\ \bar{3} & = & \bar{3}^1 \\ \bar{4} & = & \bar{3}^4 \\ \bar{5} & = & \bar{3}^5 \\ \bar{6} & = & \bar{3}^3 \end{eqnarray*}$ Exercises 69. Let $$n$$ be a postive integer. Find a cyclic group of order $$n$$. 70. Find an infinite cyclic group. 71. Let $$G$$ be a group and $$g\in G$$ with order $$n$$ (a positive integer). Show that $$g^{-1}$$ also has order $$n$$. 72. Let $$G$$ be an infinite cyclic group. Show that $$G$$ has no finite subgroups other than the trivial one $$\{1\}$$. 73. Let $$G$$ be a group such that $$g^2=1$$ for all $$g\in G$$. Prove that $$G$$ is abelian. 74. Let $$G$$ be a group. Show that $$G$$ is finite with prime order if and only if $$G$$ has exactly 2 subgroups.