2016-11-10, 23:10 | #1 |
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 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.
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, \(y<x\) means \(x>y\), 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<y<z\) means \(x<y\) and \(y<z\), while \(a\in A\subset B\) means \(a\in A\) and \(A\subset B\). Let \(A\) be a set and \(\sim\) a relation on \(A\). We call the relation \(\sim\) reflexive if it has the following property: for all \(x\in A\), we have \(x\sim x\). We call the relation \(\sim\) symmetric if if has this property: for all \(x,y\in A\), if \(x\sim y\) then \(y\sim x\). And we call the relation \(\sim\) transitive if the following holds: for all \(x,y,z\in A\), if \(x\sim y\) and \(y\sim z\) then \(x\sim z\). We call \(\sim\) an equivalence relation on \(A\) if it is reflexive, symmetric and transitive. Examples The relation ">" 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<i-j<n\) but \(a^{i-j}=a^ib^j=a^jb^j=\bar{1}\) so \(n\) is not the smallest positive power of \(a\) equal to \(\bar{1}\), a CONTRADICTION. Hence \(\bar{1},a,a^2,\ldots,a^{n-1}\) are all distinct in \(\mathbb{Z}/m\mathbb{Z}\). Take any integer \(k\). By proposition 5, there exist unique integers \(q\) and \(r\) such that \(k=qn+r\) and \(0\leq r<n\) (division with remainder). If \(n|k\) then \(r=0\) and \(a^k=(a^n)^q=\bar{1}^q=\bar{1}\). If \(n\) does not divide \(k\) then \(0<r<n\) and \(a^k=a^{qn+r}=(a^n)^qa^r=\bar{1}\cdot a^r\neq \bar{1}\) since \(\bar{1},a,a^2,\ldots,a^{n-1}\) are all distinct in \(\mathbb{Z}/m\mathbb{Z}\). ∎ Theorem 38 Let \(m\) be a positive integer, \(a\in (\mathbb{Z}/m\mathbb{Z})^*\) and \(n\in\mathbb{Z}\) the order of \(a\). Define a relation \(\sim\) on the unit group \((\mathbb{Z}/m\mathbb{Z})^*\) as follows: \(x\sim y\) if and only if \(y^{-1}x=a^k\) for some integer \(k\). Then \(\sim\) is an equivalence relation on \((\mathbb{Z}/m\mathbb{Z})^*\) and every equivalence class has precisely \(n\) distinct elements. proof Take any \(x,y,z\in\mathbb{Z}/m\mathbb{Z}\). Then \(x^{-1}x=1=a^0\) so \(x\sim x\). If \(x\sim y\) then \(y^{-1}x=a^k\) for some integer \(k\) so \(x^{-1}y=a^{-k}\) and therefore \(y\sim x\). And if \(x\sim y\sim z\) then \(y^{-1}x=a^r\) and \(z^{-1}y=a^s\) for some integers \(r,s\) so \(z^{-1}x=z^{-1}yy^{-1}x=a^{s+r}\) hence \(x\sim z\). Thus \(\sim\) is an equivalence relation on \((\mathbb{Z}/m\mathbb{Z})^*\). Take any unit \(b\in(\mathbb{Z}/m\mathbb{Z})^*\). For all integers \(k\), \(b^{-1}(ba^k)=a^k\) so \(ba^k\sim b\) and therefore \(ba^k\in [b]\). Conversely, for any unit \(c\) if \(c\in [b]\) then \(c\sim b\) so \(b^{-1}c=a^k\) for some integer \(k\) and therefore \(c=ba^k\). Thus \([b]=\{ba^k:k\in\mathbb{Z}\}\). Take any integers \(r,s\). If \(a^r=a^s\) then \(ba^r=ba^s\). Conversely, if \(ba^r=ba^s\) then (since \(b\) is a unit with an inverse \(b^{-1}\) in the integers modulo \(m\)), \(b^{-1}ba^r=b^{-1}ba^s\), i.e. \(a^r=a^s\). By proposition 37, it follows that \(\#[b]=n\). ∎ Corollary 39 Let \(m\) be a positive integer, \(a\in (\mathbb{Z}/m\mathbb{Z})^*\) and \(n\in\mathbb{Z}\) the order of \(a\). Then \(n|\phi(m)\). proof Under the equivalence relation defined in theorem 38, each equivalence class has precisely \(n\) elements. And the equivalence classes form a partition of \((\mathbb{Z}/m\mathbb{Z})^*\) by proposition 35, so \(n\) divides the number of elements in \((\mathbb{Z}/m\mathbb{Z})^*)\), which is \(\phi(n)\) (by definition). ∎ Corollary 40 Let \(m\) be a positive integer and \(a\) an integer with \(\gcd(a,m)=1\). Then \(a^{\phi(m)}\equiv 1\pmod{m}\). proof As \(\gcd(a,m)=1\), we have \(\bar{a}\in(\mathbb{Z}/m\mathbb{Z})^*\) by proposition 32. Let \(n\) be the order of \(\bar{a}\). By corollary 39, \(n|\phi(m)\) so, by proposition 37, \(\bar{a}^{\phi(m)}=\bar{1}\), i.e. \(a^{\phi(m)}\equiv 1\pmod{m}\). ∎ In particular, if \(p\) is a prime number then \(\phi(p)=p-1\) by proposition 34 so, for any integer \(a\) not divisible by \(p\), \(a^{p-1}\equiv 1\pmod{p}\). Corollary 41 (Fermat's little theorem) For all prime numbers \(p\) and all integers \(a\), \(a^p\equiv a\pmod{p}\). proof If \(p|a\) then \(a\equiv 0\pmod{p}\) and the result follows immediately. Otherwise, \(a^{p-1}\equiv 1\pmod{p}\) by corollary 40, so \(a^p\equiv a\pmod{p}\). ∎ Exercises 36. Let \(m,n\) be positive integers and \(a\) a unit of order \(n\) in the integers modulo \(m\). Show that \(a^{-1}\) also has order \(n\). 37. Calculate \(11^{345^{678}}\bmod{13}\) without using a computer. 38. Let \(p\) be a prime number greater than 2 and suppose there exists \(x\) in the integers modulo \(p\) such that \(x^2+\bar{1}=\bar{0}\). Prove that \(p\bmod{4}=1\). 39. (RSA) Let \(p,q\) be distinct prime numbers, \(n=pq\) and \(e,d\) non-negative integers less than \((p-1)(q-1)\) such that \(\bar{e}\) is a unit with inverse \(\bar{d}\) in the integers modulo \((p-1)(q-1)\). Show that, for any non-negative integer \(m\) with \(m<n\), we have \(m^{ed}\bmod{n}=m\). Last fiddled with by Nick on 2016-12-14 at 09:50 Reason: Variable typo in statement of Corollary 41 (replaced m with p). |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Basic Number Theory 1 & 2 | Nick | Number Theory Discussion Group | 17 | 2017-12-23 20:10 |
Basic Number Theory 20: polynomials | Nick | Number Theory Discussion Group | 5 | 2017-04-25 14:32 |
Basic Number Theory 15: Lagrange's theorem, cyclic groups and modular arithmetic | Nick | Number Theory Discussion Group | 0 | 2017-01-07 13:15 |
Basic Number Theory 14: a first look at groups | Nick | Number Theory Discussion Group | 0 | 2016-12-29 13:47 |
Basic Number Theory 6: functions and the Chinese Remainder Theorem | Nick | Number Theory Discussion Group | 4 | 2016-10-31 22:26 |