 mersenneforum.org > Math Basic Number Theory 16: unit group structure in modular arithmetic
 Register FAQ Search Today's Posts Mark Forums Read 2017-01-19, 20:22 #1 Nick   Dec 2012 The Netherlands 22×3×5×29 Posts Basic Number Theory 16: unit group structure in modular arithmetic Let $$n$$ be a positive integer. The set $\mathbb{Z}/n\mathbb{Z}=\{\bar{0},\bar{1},\bar{2},\ldots,\overline{n-1}\}$ of integers modulo $$n$$ forms a group under addition modulo $$n$$. It does not form a group under multiplication modulo $$n$$ (unless $$n=1$$) because not every element has a multiplicative inverse. Those elements which do have such an inverse are called the units in the integers modulo $$n$$, and the subset containing all the units $\left(\mathbb{Z}/n\mathbb{Z}\right)^* =\{\bar{a}\in\mathbb{Z}/n\mathbb{Z}:\gcd(a,n)=1\}$ is a group under multiplication (modulo $$n$$). Its order (i.e. the number of elements in the group) is $$\phi(n)$$, where $$\phi$$ is Euler's phi function (also known as Euler's totient function). If we take a prime number $$p$$, then every positive integer smaller than $$p$$ is coprime to $$p$$, so we get $$\phi(p)=p-1$$ and $\left(\mathbb{Z}/p\mathbb{Z}\right)^*=\{\bar{1},\bar{2},\bar{3},\ldots, \overline{p-1}\}.$ We saw last time that this is actually a cyclic group, i.e. there exists an integer $$a$$ such that $\left(\mathbb{Z}/p\mathbb{Z}\right)^*=\{\bar{a}^0=\bar{1},\bar{a}^1=\bar{a}, \bar{a}^2,\bar{a}^3,\ldots, \bar{a}^{p-2}\}.$ Such an integer $$a$$ is called a primitive root modulo $$p$$. We have proved that a primitive root modulo $$p$$ exists for every prime number $$p$$, but there is no simple method known for finding them. (For relatively small prime numbers, we can just try all possibilities, of course.) The next logical step is to analyze the structure of $$\left(\mathbb{Z}/p^m\mathbb{Z}\right)^*$$, i.e. the units in the integers modulo $$p^m$$ where $$p$$ is a prime number and $$m$$ any positive integer. Once we understand this, the Chinese Remainder Theorem immediately shows how the units fit together in $$\left(\mathbb{Z}/n\mathbb{Z}\right)^*$$ for all positive integers $$n$$. Let $$a,b$$ be any numbers. You are probably familiar with the following equations: $\begin{eqnarray*} (a+b)^2 & = & a^2+2ab+b^2 \\ (a+b)^3 & = & a^3+3a^2b+3ab^2+b^3 \\ (a+b)^4 & = & a^4+4a^3b+6a^2b^2+4ab^3+b^4 \\ (a+b)^5 & = & a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5 \\ & \vdots & \end{eqnarray*}$ The constants involved come from Pascal's triangle, in which each entry is the sum of the two entries directly above it (left and right). More formally, for each non-negative integer $$n$$, we define $$n$$ factorial, written $$n!$$, by $n!=1\cdot 2\cdot 3\cdot\ldots\cdot n$ Thus $$0!=1$$ (the product of no integers is defined to be 1), $$1!=1$$, $$2!=1\times 2=2$$, $$3!=1\cdot 2\cdot 3=6$$, $$4!=1\cdot 2\cdot 3\cdot 4=24$$, etc. For any integers $$r,n$$ with $$0\leq r\leq n$$, we then define $\binom{n}{r}=\frac{n!}{r!(n-r)!}.$ Take any non-negative integer $$n$$. From the above definition, we immediately get $$\binom{n}{0}=1$$ and $$\binom{n}{n}=1$$. And for any integer $$r$$ with $$02$$ and suppose the lemma holds for all $$n3$$ and suppose the claim holds for all $$m m$$, so $$\bar{5}$$ has order $$2^{m-2}$$ in the group $$(\mathbb{Z}/2^m\mathbb{Z})^*$$, and it follows that the first $$2^{m-2}$$ elements listed are distinct (proposition 75). Also, for any integer $$n$$, if $$5^n\equiv -1\pmod{2^m}$$ then $$5^n\equiv -1\pmod{4}$$, but $$5^n\equiv 1\pmod{4}$$, a CONTRADICTION. It follows that all $$2^{m-1}$$ elements listed are distinct. As $$\phi(2^m)=2^{m-1}$$, these are all the elements of $$(\mathbb{Z}/2^m\mathbb{Z})^*$$. ∎ To see more clearly what this tells us, we introduce an important concept. Let $$G,H$$ be groups. An isomorphism from $$G$$ to $$H$$ is a function $$f:G\rightarrow H$$ such that $$f$$ is bijective and, for all $$x,y\in G$$, $$f(xy)=f(x)f(y)$$. More informally, $$f$$ pairs the elements of $$G$$ off with the elements of $$H$$ and preserves the binary operation: if $$xy=z$$ in $$G$$ then $$f(x)f(y)=f(z)$$ in $$H$$. We say $$G$$ is isomorphic with $$H$$, and write $$G\cong H$$, if there exists an isomorphism from $$G$$ to $$H$$. Example Here are the addition table for the integers modulo 6 and the multiplication table for the units in the integers modulo 7. Code: Addition modulo 6 Multiplication modulo 7 0 1 2 3 4 5 1 2 3 4 5 6 ┏━━━━━━━━━━━━ ┏━━━━━━━━━━━━ 0 ┃0 1 2 3 4 5 1 ┃1 2 3 4 5 6 1 ┃1 2 3 4 5 0 2 ┃2 4 6 1 3 5 2 ┃2 3 4 5 0 1 3 ┃3 6 2 5 1 4 3 ┃3 4 5 0 1 2 4 ┃4 1 5 2 6 3 4 ┃4 5 0 1 2 3 5 ┃5 3 1 6 4 2 5 ┃5 0 1 2 3 4 6 ┃6 5 4 3 2 1 In the second table, if we write the numbers in the order 1,3,2,6,4,5 instead of 1,2,3,4,5,6, we get the following: Code: Multiplication modulo 7 1 3 2 6 4 5 ┏━━━━━━━━━━━━ 1 ┃1 3 2 6 4 5 3 ┃3 2 6 4 5 1 2 ┃2 6 4 5 1 3 6 ┃6 4 5 1 3 2 4 ┃4 5 1 3 2 6 5 ┃5 1 3 2 6 4 This table has the same pattern as the first one: take the table for addition modulo 6 and replace every occurrence of 0 with 1 and (simultaneously) replace every 1 with 3 and every 3 with 6, and you get the table for multiplication modulo 7 (with rows and columns in this order). Thus $$\mathbb{Z}/6\mathbb{Z}$$ is isomorphic with $$(\mathbb{Z}/7\mathbb{Z})^*$$. Properties of the first group which depend solely on its addition automatically translate to properties about the second group and its multiplication. For example, $$(\mathbb{Z}/7\mathbb{Z})^*$$ has an element of order 6 because $$\mathbb{Z}/6\mathbb{Z}$$ has an element of order 6. If we are only interested in their properties as groups, then there is no need to distinguish between them, and they can be viewed as two concrete instances of the same underlying, abstract group. Proposition 97 The relation $$\cong$$ is an equivalence relation on any set of groups. proof For any group $$G$$, the identity function $$i_G:G\rightarrow G,x\mapsto x$$ is an isomorphism so $$G\cong G$$. Take any groups $$G,H$$ and suppose $$G\cong H$$. Then there exists an isomorphism $$f:G\rightarrow H$$. In particular, $$f$$ is bijective so it has an inverse $$f^{-1}:H\rightarrow G$$ (proposition 25) and $$f^{-1}$$ is also bijective (corollary 27). Take any $$x,y\in H$$ and let $$a=f^{-1}(x)$$ and $$b=f^{-1}(y)$$. Then $$f(a)=x$$ and $$f(b)=y$$, and$$f$$ is an isomorphism so $f^{-1}(xy)=f^{-1}(f(a)f(b))=f^{-1}(f(ab))=ab=f^{-1}(x)f^{-1}(y).$ Hence $$f^{-1}$$ is also an isomorphism and therefore $$H\cong G$$. Finally, take any groups $$G,H,K$$, and suppose $$G\cong H$$ and $$H\cong K$$. Then there exist isomorphisms $$f:G\rightarrow H$$ and $$g:H\rightarrow K$$. In particular, $$f,g$$ are each bijective so their composition $$g\circ f:G\rightarrow K$$ is also bijective (exercise 29). And, for any $$x,y\in G$$, $(g\circ f)(xy)=g(f(xy)=g(f(x)f(y))=g(f(x))g(f(y))=(g\circ f)(x)(g\circ f)(y)$ so $$g\circ f$$ is an isomorphism and $$G\cong K$$. ∎ Proposition 98 Any two cyclic groups of the same finite order are isomorphic. proof Let $$n$$ be a positive integer, $$G$$ a cyclic group of order $$n$$ generated by $$g\in G$$ and $$H$$ also a cyclic group of order $$n$$, generated by $$h\in H$$. Define $$f:G\rightarrow H$$ as follows: for each $$x\in G$$, there exists an integer $$i$$ such that $$x=g^i$$, and we define $$f(x)=h^i\in H$$. This is well-defined since, for any integers $$i,j$$, if $$g^i=g^j$$ then $$n$$ divides $$i-j$$ so $$h^i=h^j$$ as well (proposition 75). It is injective since, for all integers $$i,j$$, if $$h^i=h^j$$ then $$n$$ divides $$i-j$$ so $$g^i=g^j$$ too. And for each $$y\in H$$ there exists an integer $$i$$ such that $$y=h^i$$, so $$f(g^i)=y$$ and therefore $$f$$ is surjective too, making it bijective. For any $$x,y\in G$$, $$x=g^i$$ and $$y=g^j$$ for some integers $$i,j$$, and $$f(xy)=f(g^{i+j})=h^{i+j}=h^ih^j=f(x)f(y)$$ hence $$f$$ is an isomorphism from $$G$$ to $$H$$. ∎ Thus, if we are only concerned with group properties, we may speak of the cyclic group of order $$n$$, for any positive integer $$n$$. For any groups $$G,H$$, we may form the Cartesian product $$G\times H$$, which is the set of all ordered pairs $$(g,h)$$ where $$g\in G$$ and $$h\in H$$. We may turn this set into a group by defining a binary operation on it: $$(g_1,h_1)(g_2,h_2)=(g_1g_2,h_1h_2)$$, i.e. we apply the existing binary operation of $$G$$ to combine the first coordinates, and the binary operation of $$H$$ for the second coordinates. The resulting group is called the direct product of $$G$$ with $$H$$. Now we can return to proposition 96. Let $$m\geq 3$$ be an integer. Then the unit group $$(\mathbb{Z}/2^m\mathbb{Z})^*$$ of the integers modulo $$2^m$$ has a subgroup $$G=\{-\bar{1},\bar{1}\}$$, which is cyclic of order 2, generated by $$-\bar{1}$$, and also a subgroup $$H=\{\bar{5}^i:i\in\mathbb{Z}\}$$ which is cyclic of order $$2^{m-2}$$, generated by $$\bar{5}$$. Proposition 96 tells us that the unit group $$(\mathbb{Z}/2^m\mathbb{Z})^*$$ is isomorphic with the direct product $$G\times H$$ of these 2 cyclic subgroups. Let $$n=p^sq^t$$ where $$p,q$$ are distinct prime numbers and $$s,t$$ positive integers. By the Chinese Remainder Theorem (theorem 29), the integers modulo $$n$$ behave exactly like ordered pairs of integers $$(a,b)$$ where the first coordinate is taken modulo $$p^s$$ and the second coordinate modulo $$q^t$$. In particular, $$(a,b)$$ is a unit if (and only if) $$a$$ is a unit in the integers modulo $$p^s$$ and $$b$$ is a unit modulo $$q^t$$. It follows that the unit group $$(\mathbb{Z}/n\mathbb{Z})^*$$ is isomorphic with the direct product $$(\mathbb{Z}/p^s\mathbb{Z})^*\times (\mathbb{Z}/q^t\mathbb{Z})^*$$. And we know how these behave by propositions 95 and 96, so we can deduce how the unit group of the integers modulo $$n$$ is built out of cyclic groups. More generally, if $$n$$ is a product of more than 2 distinct prime numbers, we can apply the Chinese Remainder Theorem more than once, and in this way we can analyze the unit group of the integers modulo $$n$$ for any positive integer $$n$$. Exercises 75. List the element(s) of $$(\mathbb{Z}/2\mathbb{Z})^*$$ and of $$(\mathbb{Z}/4\mathbb{Z})^*$$ (the only cases not covered by propositions 95 and 96). 76. Find all the primitive roots modulo 11. 77. Show that any two infinite cyclic groups are isomorphic. 78. Let $$p$$ be a prime number such that $$p\equiv 1\pmod{4}$$. Show that, for any integer $$a$$, $$a$$ is a primitive root modulo $$p$$ if and only if $$-a$$ is a primitive root modulo $$p$$. Last fiddled with by Nick on 2017-02-19 at 13:16 Reason: Typo in proof of lemma 94, and in proof of proposition 96.  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 17 2017-12-23 20:10 Nick Number Theory Discussion Group 5 2017-04-25 14:32 Nick Number Theory Discussion Group 0 2017-01-07 13:15 Nick Number Theory Discussion Group 0 2016-12-29 13:47 Nick Number Theory Discussion Group 1 2016-10-21 22:21

All times are UTC. The time now is 05:58.

Sat Oct 16 05:58:02 UTC 2021 up 85 days, 27 mins, 0 users, load averages: 1.56, 1.29, 1.17