mersenneforum.org > Math Basic Number Theory 8: equiv. relations and Fermat's little theorem
 Register FAQ Search Today's Posts Mark Forums Read

 2016-11-10, 23:10 #1 Nick     Dec 2012 The Netherlands 5×353 Posts Basic Number Theory 8: equiv. relations and Fermat's little theorem We have been looking at Euler's phi function. For any positive integer $$n$$, $$\phi(n)$$ is defined as the number of units in the integers modulo $$n$$, and we saw (in proposition 32) that this is also the number of integers in the range 0 to $$n-1$$ inclusive that are coprime to $$n$$. For any coprime positive integers $$m$$ and $$n$$, we also proved that $$\phi(mn)=\phi(m)\phi(n)$$ (proposition 33). Example What is $$\phi(25)?$$ The positive divisors of 25 are 1, 5 and $$25=5^2$$ so, for any integer $$a$$, we have $$\gcd(a,25)=1$$ if and only if $$a$$ is not divisible by 5. Consider the integers from 0 to 24 inclusive: Code:  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 The entries in this table that are divisible by 5 are precisely the 5 entries in the first column, so $$\phi(25)=25-5=20$$. Let us do this more generally. Proposition 34 Let $$p$$ be a prime number and $$n$$ a positive integer. Then $$\phi(p^n)=(p-1)p^{n-1}$$. proof Let $$S=\{0,1,2,\ldots,p^n-1\}$$ and $$T=\{a\in S:\gcd(a,p^n)>1\}$$. Then $$\phi(n)=\#S-\#T$$ by proposition 32. As $$p$$ is a prime number, the positive divisors of $$p^n$$ are $$1,p,p^2,p^3,\ldots,p^n$$ (and no others). So, for each $$a\in S$$, $$\gcd(a,p^n)>1$$ if and only if $$p|a$$. Thus $$T=\{0,p,2p,3p,\ldots,p^n-p\}$$ and therefore $$\#T=p^{n-1}$$. Hence $$\phi(n)=\#S-\#T=p^n-p^{n-1}=(p-1)p^{n-1}$$. ∎ Using propositions 33 and 34 together, we can find $$\phi(n)$$ for any positive integer $$n$$ small enough to be factorized into its product of prime numbers. The easy way to think of it is that you decrement one occurrence of each prime factor. For example, $$\phi(2\cdot 2\cdot 2\cdot 5\cdot 5\cdot 11)=1\cdot 2\cdot 2\cdot 4\cdot 5\cdot 10$$, i.e. $$\phi(2200)=800$$. Before we can go further with Number Theory, we need 2 more general mathematical concepts: partitions and equivalence relations. Let $$S$$ be a set. A partition of $$S$$ is a collection of non-empty subsets of $$S$$ such that each element of $$S$$ occurs in precisely one of the subsets. Example For any positive integer $$m$$, the $$m$$ subsets $\begin{eqnarray*} \bar{0} & = & \{mn:n\in\mathbb{Z}\} \\ \bar{1} & = & \{1+mn:n\in\mathbb{Z}\} \\ \bar{2} & = & \{2+mn:n\in\mathbb{Z}\} \\ \vdots \\ \overline{m-1} & = & \{(m-1)+mn:n\in\mathbb{Z}\} \end{eqnarray*}$ form a partition of $$\mathbb{Z}$$. We have already seen several examples of relations. ">" is a relation on $$\mathbb{R}$$: for any real numbers $$x,y$$, "$$x>y$$" is a statement that is true or false. "|" (i.e. "divides") is a relation on $$\mathbb{Z}$$: for any integers $$a,b$$, "$$a|b$$" is a statement that is true or false. "$$\subset$$" is a relation on any set of sets: for any sets $$A,B$$, "$$A\subset B$$" is a statement that is true or false. Let $$n$$ be a positive integer. Then $$\equiv\pmod{n}$$ is a relation on $$\mathbb{Z}$$: for any integers $$a,b$$, "$$a\equiv b\pmod{n}$$" is either true or false. "+" is not a relation: for any numbers $$x,y$$, $$x+y$$ is a number, not a statement. (Technically, a relation on a set $$A$$ is determined by the set of all ordered pairs of elements of $$A$$ that are related in that way, so we define a relation on $$A$$ as a subset of the Cartesian product $$A\times A$$. Similarly, for any sets $$A$$ and $$B$$, a relation from $$A$$ to $$B$$ is a subset of the Cartesian product $$A\times B$$. Functions can also be defined in terms of relations. But understanding the idea here is more important than the technical definition.) Notation We may draw a line through any relation symbol to say that the relation does not hold. For example, $$x\neq y$$ means $$x$$ is not equal to $$y$$, and $$A\not\subset B$$ means $$A$$ is not a subset of $$B$$. We may write a relation symbol backwards for the reverse relation. For example, $$yy$$, and $$B\supset A$$ means $$A\subset B$$. (This does not work if the symbol itself is symmetric!) Also, we may use several relations in a row to assert that they all hold. For example, $$x" on \(\mathbb{R}$$ is not reflexive or symmetric but is transitive: for any real numbers $$x,y,z$$, if $$x>y$$ and $$y>z$$ then $$x>z$$. The relation "|" on $$\mathbb{Z}$$ is reflexive (since, for all integers $$n$$ we have $$n|n$$) and transitive (exercise 5) but it is not symmetric. For all positive integers $$n$$, the relation $$\equiv\pmod{n}$$ is reflexive, symmetric and transitive, and hence an equivalence relation on $$\mathbb{Z}$$. Notation Let $$\sim$$ be an equivalence relation on a set $$A$$. For each $$a\in A$$, we write $$[a]=\{x\in A:x\sim a\}$$ and call this subset of $$A$$ the equivalence class of $$a$$ (under $$\sim$$). We call the element $$a$$ a representative of its equivalence class. (Any element of an equivalence class may be chosen to represent it.) Proposition 35 Let $$A$$ be a set and $$\sim$$ an equivalence relation on $$A$$. Then the equivalence classes under $$\sim$$ form a partition of $$A$$. proof The relation $$\sim$$ is reflexive so, for all $$a\in A$$ we have $$a\in [a]$$. Thus each equivalence class is a non-empty subset of $$A$$, and every element of $$A$$ is present in at least one equivalence class. Take any $$a,b\in A$$ and suppose that $$[a]\cap [b]\neq\emptyset$$, i.e. there exists an element $$c$$ which is present in both $$[a]$$ and $$[b]$$. Then $$c\sim a$$ and $$c\sim b$$. As $$\sim$$ is symmetric, we also have $$a\sim c$$, and $$\sim$$ is transitive too, so from $$a\sim c$$ and $$c\sim b$$ it follows that $$a\sim b$$. We now prove that $$[a]=[b]$$. Take any $$x\in [a]$$. Then $$x\sim a$$ and $$a\sim b$$ and $$\sim$$ is transitive so $$x\sim b$$ and therefore $$x\in [b]$$. Thus $$[a]\subset [b]$$. Conversely, take any $$x\in [b]$$. Then $$x\sim b$$ and $$b\sim a$$ (since $$a\sim b$$ and $$\sim$$ is symmetric) so $$x\sim a$$ (as $$\sim$$ is transitive) hence $$x\in [a]$$. Thus $$[b]\subset [a]$$ as well, so $$[a]$$ and $$[b]$$ have precisely the same elements, making them equal. We have shown that if two equivalence classes overlap then they are equal. It follows that each element of $$A$$ is present in only 1 equivalence class. This completes the proof that the equivalence classes form a partition of $$A$$. ∎ We can now return to Number Theory. For any numbers $$x,y$$, if $$x\neq 0$$ and $$y\neq 0$$ but $$xy=0$$ then we call $$x$$ and $$y$$ zero divisors. (Some people also count 0 as a zero divisor.) In $$\mathbb{Z}$$, there are no zero divisors (unless you count 0). In the integers modulo 10, for example we have $$\bar{4}\times\bar{5}=\bar{0}$$ so $$\bar{4}$$ and $$\bar{5}$$ are both zero divisors. It follows that if $$\bar{5}x=\bar{5}y$$ we cannot conclude that $$x=y$$ (e.g. we could have $$x=\bar{3}$$ and $$y=\bar{7}$$). This problem does not occur with units. For example, $$\bar{3}$$ is a unit in the integers modulo 10 with inverse $$\bar{7}$$ so if $$\bar{3}x=\bar{3}y$$ then $$x=\bar{7}\cdot\bar{3}x=\bar{7}\cdot\bar{3}y=y$$. In particular, if $$z$$ is also an inverse for $$\bar{3}$$ then $$\bar{3}z=\bar{1}=\bar{3}\cdot\bar{7}$$ so it follows that $$z=\bar{7}$$. Thus the inverse of a unit is indeed unique, and we are justified in writing $$\bar{7}=\bar{3}^{-1}$$. For units, the usual laws of indices then extend to negative powers, i.e. if $$a$$ and $$b$$ are units then, for all integers $$m,n$$, we have $$a^{m+n}=a^m\cdot a^n$$, $$a^{mn}=(a^m)^n$$ and $$(ab)^n=a^nb^n$$. (You can easily prove these by induction if you wish.) Proposition 36 Let $$m$$ be a positive integer and $$a\in(\mathbb{Z}/m\mathbb{Z})^*$$ (i.e. $$a$$ is a unit in the integers modulo $$m$$). Then $$a^n=\bar{1}$$ for some positive integer $$n$$. proof As $$a$$ is a unit, there exists $$b\in\mathbb{Z}/m\mathbb{Z}$$ such that $$ab=\bar{1}$$. There are only $$m$$ distinct integers modulo $$m$$, so the values $$\bar{1},a,a^2,a^3,\ldots,a^m$$ cannot all be different. Thus there exist non-negative integers $$i,j$$ such that $$i>j$$ but $$a^i=a^j$$. Let $$n=i-j$$. Then $$n>0$$ and $$a^n=a^ib^j=a^jb^j=1$$. ∎ The smallest positive integer $$n$$ for which $$a^n=\bar{1}$$ is called the order of $$a$$ in the unit group of the integers modulo $$m$$. Example In the integers modulo 9, $$\bar{4}$$ is a unit since $$\bar{4}\times\bar{7}=\bar{1}$$. We have $$\bar{4}\neq\bar{1}$$, $$\bar{4}^2\neq\bar{1}$$ but $$\bar{4}^3=\bar{1}$$, so we say $$\bar{4}$$ has order 3 in the unit group of integers modulo 9. It follows that $\ldots,\bar{4}^{-3}=\bar{1},\bar{4}^{-2}=\bar{4},\bar{4}^{-1}=\bar{7}, \bar{4}^0=\bar{1},\bar{4}^1=\bar{4},\bar{4}^2=\bar{7}, \bar{4}^3=\bar{1},\bar{4}^4=\bar{4},\bar{4}^5=\bar{7}, \bar{4}^6=\bar{1},\ldots$ Proposition 37 Let $$m$$ be a positive integer and $$a\in (\mathbb{Z}/m\mathbb{Z})^*$$. Let $$n$$ be the order of $$a$$ in this unit group. Then $$\bar{1},a,a^2,a^3,\ldots,a^{n-1}$$ are all distinct elements of $$(\mathbb{Z}/m\mathbb{Z})^*$$ and, for all integers $$k$$, $$a^k=\bar{1}$$ if and only if $$n|k$$. proof As $$a$$ is a unit, there exists $$b\in\mathbb{Z}/m\mathbb{Z}$$ such that $$ab=\bar{1}$$. Suppose there exist integers $$i,j\in\{0,1,2,\ldots,n-1\}$$ such that $$i>j$$ but $$a^i=a^j$$. Then \(0

 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 4 2016-10-31 22:26

All times are UTC. The time now is 15:57.

Tue Nov 29 15:57:52 UTC 2022 up 103 days, 13:26, 1 user, load averages: 0.85, 0.72, 0.84