Basic Number Theory 7: idempotents and Euler's function

[Nick]

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(x-1)=x^2-x=0\) and therefore \(x=0\) or \(x-1=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:

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)

As an example, 7 corresponds with (2,1) and 4 corresponds with (4,0).
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 \(7-4=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=1-x\).
Then \(y\) is also idempotent, \(x+y=1\) and \(xy=0\).

proof
As \(x^2=x\), we have \(y^2=(1-x)^2=1-2x+x^2=1-x=y\).
As \(y=1-x\), it follows immediately that \(x+y=1\),
and \(xy=x(1-x)=x-x^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(1-bn)=am\) and \((bn)^2=bn(1-am)=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 \(n-1\) 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 3-digit 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\).

[only_human]

"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.

Since the residue classes (mod p) are a field, every non-zero a has a unique multiplicative inverse, a^-1

But when the modulus, m, is composite (this is not a field) there are elements, a, that are not units iff GCD(m,a) ≠ 1.

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.

An idempotent element e ≠ 1of a ring is always a two-sided zero divisor, since e(1-e) = 0 = (1-e)e

From the definition of a multiplicative inverse, I see:

If the multiplication is associative, an element x with a multiplicative inverse cannot be a zero divisor (x is a zero divisor if some nonzero y, xy = 0). To see this, it is sufficient to multiply the equation xy = 0 by the inverse of x (on the left), and then simplify using associativity.

So to do some actual work I need to show that idempotent numbers > 1 are zero divisors and that zero divisors have no multiplicative inverse.

[Nick]

Originally Posted by only_human

So to do some actual work I need to show that idempotent numbers > 1 are zero divisors and that zero divisors have no multiplicative inverse.

That's a good strategy (though be careful to keep ">" for the integers, not integers modulo something.)
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.

[only_human]

Originally Posted by Nick

That's a good strategy (though be careful to keep ">" for the integers, not integers modulo something.)
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.

Looking at your hint I can do the following although this is borrowing from a proof to Proposition 30 that you supplied.

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.

Proposition 30
Let \(x\) be idempotent and \(y=1-x\).
Then \(y\) is also idempotent, \(x+y=1\) and \(xy=0\).

proof
As \(x^2=x\), we have \(y^2=(1-x)^2=1-2x+x^2=1-x=y\).
As \(y=1-x\), it follows immediately that \(x+y=1\),
and \(xy=x(1-x)=x-x^2=0\) since \(x^2=x\). ∎

[Nick]

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=1-x in order to apply proposition 30:
"Suppose x is an idempotent number and a unit, and let y=1-x.
By proposition 30, xy=0, so y=x⁻¹0=0 ..."
And then it works!

[only_human]

Originally Posted by Nick

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.

Thank you for this assistance. I think that I'm still lost in the weeds a bit but that can be solved by my doing more work in an offline manner which certainly need not disrupt things here.

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.

[Nick]

Originally Posted by only_human

I think maybe you meant they can't be paired up differently.

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!

[science_man_88]

Originally Posted by Nick

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!

most things like binary relations before functions might be useful to a lower audience in that case they can find the R.D.S. number theory homework thread I made a long while back.

[Nick]

Originally Posted by science_man_88

most things like binary relations before functions might be useful to a lower audience in that case they can find the R.D.S. number theory homework thread I made a long while back.

OK, we'll take a look at some relations next time.

[only_human]

Originally Posted by Nick

Exercises
31. Find the unique 3-digit integer (in decimal) which is 0 mod 8 and 1 mod 125.

Well the brute force way is add one to a multiple of 125 and see if divisible by 8.
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³, and 8 is 2³ and 8 * 125 = 10³
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.

[Nick]

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 1-376 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.