20161104, 23:06  #1 
Dec 2012
The Netherlands
3345_{8} Posts 
Basic Number Theory 7: idempotents and Euler's function
In computer science, an operation is called idempotent if doing it twice has the same effect as doing it just once.
Setting the value of a variable to zero, for example, is an idempotent operation, but incrementing its value is not. This distinction is important in the design of network protocols and distributed systems. In mathematics, we call a number \(x\) idempotent if \(x^2=x\). Thus 0 and 1 are both idempotent (since \(0^2=0\) and \(1^2=1\)). Conversely, for any integer (or, indeed, any real number) \(x\), if \(x\) is idempotent then \(x^2=x\) so \(x(x1)=x^2x=0\) and therefore \(x=0\) or \(x1=0\), i.e. \(x=0\) or \(x=1\). Hence 0 and 1 are the only idempotent numbers (and you may be wondering why we introduced the idea at all). Consider the integers modulo 10. As we have seen, there are 2 ways of looking at them. One is that we just use the integers from 0 to 9 inclusive, and we add, subtract or multiply in the usual way but then divide by 10 and take the remainder. For any integer \(a\), we write \(a\bmod{10}\) for the remainder on dividing \(a\) by 10. The other way of seeing them is that we use all the integers but regard two integers as equivalent if they differ by a multiple of 10. At any stage in a calculation, we may replace any of the numbers involved with an equivalent number, and we will get an equivalent result (we proved this in proposition 22). For an integer \(a\), we write \(\bar{a}\) to denote \(a\) or any integer equivalent to it. With this notation, we see that \(\bar{0}^2=\bar{0}\) and \(\bar{1}^2= \bar{1}\), just as with the integers, but we also have \(\bar{5}^2=\bar{5}\) and \(\bar{6}^2=\bar{6}\). To understand where this extra pair of idempotent numbers has come from, let us use the Chinese Remainder Theorem. We introduced the idea of calculating with pairs of integers, whereby addition, subtraction and multiplication are done coordinate by coordinate. As \(5\times 2=10\) and \(\gcd(5,2)=1\), the Chinese Remainder Theorem tells us that if we take pairs of integers and use modulo 5 arithmetic on the 1st coordinate and modulo 2 arithmetic on the 2nd, then the pairs will behave just like individual integers modulo 10. Here is the correspondence table again, for convenience: Code:
a mod 10 (a mod 5,a mod 2) 0 (0,0) 1 (1,1) 2 (2,0) 3 (3,1) 4 (4,0) 5 (0,1) 6 (1,0) 7 (2,1) 8 (3,0) 9 (4,1) If we add them, we get \(7+4=1\pmod{10}\) on the left side of the table and \((2,1)+(4,0)=(1,1)\) on the right side and, indeed, 1 corresponds with \((1,1)\). If we subtract them, we get \(74=3\pmod{10}\) and \((2,1)(4,0)=(3,1)\)  and 3 corresponds with \((3,1)\). Also if we multiply them, we get \(7\times 4=8\pmod{10}\) and \((2,1)(4,0)= (3,0)\) and, again, 8 corresponds with \((3,0)\). So the calculations on the two sides of the above table mirror each other exactly. (We proved this formally in theorem 29.) Now any pair \((a,b)\) will be idempotent if \(a\) and \(b\) are both idempotent. In particular, this holds if \(a\) and \(b\) are each 0 or 1. But that gives us 4 combinations: \((0,0)\), \((0,1)\), \((1,0)\) and \((1,1)\). And in the table we see that these correspond with 0, 5, 6 and 1, the idempotents that we found in the integers modulo 10. (5 is 0 mod 5 and 1 mod 2, while 6 is 1 mod 5 and 0 mod 2.) Note also that \(5+6=1\) and \(5\times 6=0\) (modulo 10). Proposition 30 Let \(x\) be idempotent and \(y=1x\). Then \(y\) is also idempotent, \(x+y=1\) and \(xy=0\). proof As \(x^2=x\), we have \(y^2=(1x)^2=12x+x^2=1x=y\). As \(y=1x\), it follows immediately that \(x+y=1\), and \(xy=x(1x)=xx^2=0\) since \(x^2=x\). ∎ Let \(f\) be the function which takes an integer modulo 10 as on the left side of the above table and returns the corresponding pair on the right, i.e. \(f(a\bmod{10})=(a\bmod{5},a\bmod{2})\). Then \(f\) is bijective so it has an inverse, \(f^{1}\). How could we calculate this inverse? In other words, given an integer \(b\) modulo 5 and an integer \(c\) modulo 2, how do we find the unique integer \(a\) modulo 10 for which \(a\bmod{5}=b\) and \(a\bmod{2}=c\) (without having to search through the table)? We can use the idempotents we have already found: just put \(a=6b+5c \bmod{10}\). Proposition 31 Let \(m\) and \(n\) be integers with \(\gcd(m,n)=1\). Then there exist integers \(a,b\) such that \(am+bn=1\), and \(am\) and \(bn\) are both idempotent in the integers modulo \(mn\). proof The required integers \(a,b\) exist by corollary 10 (and can be calculated using the extended Euclidean Algorithm). In the integers modulo \(mn\), we then have \((am)^2=am(1bn)=am\) and \((bn)^2=bn(1am)=bn\). ∎ Another application of the Chinese Remainder Theorem concerns units in modular arithmetic. (Recall that units are the numbers with an inverse under multiplication.) Proposition 32 Let \(n\) be a positive integer and \(a\) an integer. Then \(a\) is a unit in the integers modulo \(n\) if and only if \(\gcd(a,n)=1\). proof Suppose \(\gcd(a,n)=1\). Then there exist integers \(r,s\) such that \(ra+sn=1\) by corollary 10, so in the integers modulo \(n\) we have \(ra=1\), making \(a\) a unit. Suppose instead that \(\gcd(a,n)=d\) for some integer \(d>1\). Then \(a\mathbb{Z}+n\mathbb{Z}=d\mathbb{Z}\) by proposition 9, and \(1\notin d\mathbb{Z}\) so no integer multiple of \(a\) yields 1 modulo \(n\), and therefore \(a\) is not a unit modulo \(n\). ∎ For each positive integer \(n\), we define \(\phi(n)\) to be the number of units in the integers modulo \(n\). By proposition 32, this is also the number of integers from 0 to \(n1\) inclusive that are coprime with \(n\). This function is known as Euler's phi function or Euler's totient function. (The \(\phi\) symbol is a lowercase Greek letter phi.) For example, \(\phi(5)=4\) by proposition 23. Proposition 33 Let \(m,n\) be integers with \(\gcd(m,n)=1\). Then \(\phi(mn)=\phi(m)\phi(n)\). proof For all integers \(a\), it follows from the Chinese Remainder Theorem (theorem 29) that \(a\bmod{mn}\) is a unit in the integers modulo \(mn\) if and only if \(a\bmod{m}\) and \(a\bmod{n}\) are units in the integers modulo \(m\) and \(n\) respectively, and that all possible combinations occur. The result follows. ∎ Exercises 31. Find the unique 3digit integer (in decimal) which is 0 mod 8 and 1 mod 125. 32. Show that 1 is the only idempotent number which is also a unit. 33. Let \(p\) be a prime number and \(n\) a positive integer. Prove that the only idempotent numbers in the integers modulo \(p^n\) are 0 and 1. 34. Calculate \(\phi(n)\) for each integer \(n\) from 1 to 20 inclusive. Show that \(\phi(n)\) is even for all \(n>2\). 35. Let \(n\) be a positive integer and suppose that \(ab=1\) in the integers modulo \(n\). Prove that \(b=a^m\) (modulo \(n\)) for some positive integer \(m\). 
20161107, 04:25  #2  
"Gang aft agley"
Sep 2002
EAA_{16} Posts 
"32. Show that 1 is the only idempotent number which is also a unit."
I'm a little scattered on this. Here are my ramblings. It's true that I am overrelying on what others say and am still weak at working through from first principles. A unit has a multiplicative inverse. Wilson's Theorem uses this. Quote:
0 has no inverse because 0n ≠ 1. 1 is its own inverse. The other idempotent numbers in Nick's example are pairwise orthogonal. When one of these other idempotent residues is in \(\bar{1}\) for a prime modulus, it is in \(\bar{0}\) for the other prime modulus. These are also zero divisors of a composite modulus. Quote:
Quote:
Last fiddled with by only_human on 20161107 at 04:35 Reason: s/GCD(m,a) > 1/GCD(m,a) ≠ 1/ 

20161107, 09:41  #3  
Dec 2012
The Netherlands
3345_{8} Posts 
Quote:
It may help to think of it this way: if x is a unit and xy=z then y=x⁻¹z. Bringing in zero divisors is a good idea  thank you! I'll include something on it next time. 

20161107, 11:14  #4  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
Quote:
Suppose x, y are distinct idempotent numbers, not equal to 0 or 1, Assume that x, y are units. let xy = z y = x⁻¹z, x = y⁻¹z But from Proposition 30, xy = 0 Therefore z = 0 y = x⁻¹z = 0, and x = y⁻¹z = 0 a contradiction to both the supposition that they are not 0 or 1 and also that they are distinct values. Quote:
Last fiddled with by only_human on 20161107 at 11:30 Reason: s/idempotent/distinct/ s/proof/proof to Proposition 30/ 

20161107, 13:56  #5 
Dec 2012
The Netherlands
11011100101_{2} Posts 
Ah! There is something I evidently failed to make clear here.
If x and y are distinct idempotent numbers, neither equal to 0 or 1, it does not necessarily follow that they form a matching pair with x+y=1 and xy=0. That was indeed the case in the examples we have considered, but not, for example, in the integers modulo 30. We can write 30=2x15 with gcd(2,15)=1 or 30=3x10 with gcd(3,10)=1 or 30=5x6 with gcd(5,6)=1 and each time we get an extra pair of idempotent numbers: \(\overline{16}\) & \(\overline{15}\), \(\overline{10}\) & \(\overline{21}\) and \(\overline{6}\) & \(\overline{25}\) respectively. (An alternative way to handle the integers modulo 30 would be to apply the Chinese Remainder Theorem twice in succession: individual integers modulo 30 behave like pairs of integers modulo 2 and 15 respectively, but individual integers modulo 15 behave like pairs of integers modulo 3 and 5 respectively, so individual integers modulo 30 behave like ordered triples of integers modulo 2,3 and 5 respectively. Choosing 0 or 1 for each of the three coordinates then yields 8 idempotent numbers, namely the 6 listed above together with 0 & 1.) So in your proof, we must explicitly choose y=1x in order to apply proposition 30: "Suppose x is an idempotent number and a unit, and let y=1x. By proposition 30, xy=0, so y=x⁻¹0=0 ..." And then it works! 
20161108, 14:22  #6  
"Gang aft agley"
Sep 2002
2×1,877 Posts 
Quote:
In the case of this example mod 30, it still looks to me that these pairs of nontrivial idempotent numbers are still forming matching pairs with x+y=1 and xy=0. Using your pairs of residue class members (dropping the overbar merely for my tablet convenience), don't x+y=1 and xy=0 apply to the pairs 16 & 15, 10 & 21, 6 & 25? Each pair has a sum of 1 mod 30. And their products 240, 210, 150 are 0 mod 30. added: I think maybe you meant they can't be paired up differently. Last fiddled with by only_human on 20161108 at 14:33 

20161108, 17:23  #7 
Dec 2012
The Netherlands
5·353 Posts 
Exactly. If we say: "Suppose x, y are distinct idempotent numbers, not equal to 0 or 1", then it does not necessarily follow that xy=0. (In the integers modulo 30, someone could pick \(x=\overline{6}\) and \(y=\overline{16}\) and get \(\overline{6}\times\overline{16}=\bar{6}\).) To be certain that xy=0 we have to stipulate that x+y=1 as well.
Thank you for your reaction: feedback helps me to guage whether the tempo is right and whether there are things I have forgotten to include! 
20161108, 18:14  #8  
"Forget I exist"
Jul 2009
Dumbassville
3·2,797 Posts 
Quote:


20161108, 20:43  #9 
Dec 2012
The Netherlands
1765_{10} Posts 

20161109, 03:07  #10  
"Gang aft agley"
Sep 2002
7252_{8} Posts 
Quote:
126 is divisible by 2 but not 8. 251 is not divisible by 2 376 is 1 mod 125, and 0 mod 8. This is a unique 3 digit (in decimal) answer because 376 + 8 * 125 > 1000 unless we also want to consider the negative number 376  8 * 125 = 624 depending on our intended domain. So now what's the smart way? 125 is 5^{3}, and 8 is 2^{3} and 8 * 125 = 10^{3} Of course gcd(2,5) = 1 as is also true for these integers raised to a power. Perhaps I need to look at an extended Euclidean Algorithm here on the numbers 125 & 8 to get a linear expression = 1. 

20161109, 08:51  #11 
Dec 2012
The Netherlands
5·353 Posts 
Absolutely right  all of it!
It follows that 376 mod 1000 corresponds with the pair (1,0) modulo 125 and modulo 8 respectively under the Chinese Remainder Theorem, and is therefore idempotent in the integers modulo 1000. That is why a number ending in 376 multiplied by a number ending in 376 always gives a number ending in 376. The other idempotent number in this matching pair is 1376 mod 1000=625. So a number ending in 625 multiplied by a number ending in 625 always gives a number ending in 625 as well. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 1 & 2  Nick  Number Theory Discussion Group  17  20171223 20:10 
Basic Number Theory 21: ideals and homomorphisms  Nick  Number Theory Discussion Group  5  20170604 12:36 
Basic Number Theory 20: polynomials  Nick  Number Theory Discussion Group  5  20170425 14:32 
Basic Number Theory 14: a first look at groups  Nick  Number Theory Discussion Group  0  20161229 13:47 
Basic Number Theory 4: a first look at prime numbers  Nick  Number Theory Discussion Group  6  20161014 19:38 