The multiplicative group of integers modulo \(n\) is represented by \(\mathbb{Z}^*_n\), and represents the numbers which do not share a factor with \(n\). If \(n\) is a prime number, the values will range from 1 to \(n-1\). If \(n=6\), we have two factors of 2 and 3, and where \(\mathbb{Z}^*_{6}\) will thus be {\(1, 5\)}, and the other values share 2 or 3 as a factor.
Multiplicative group of \(\mathbb{Z}_n\) (\(\mathbb{Z}^*_{n}\)) |
Theory
Let's try \(n=10\), and which has the prime factors of \(2\) and \(5\):
Computing Z_n (showing first 50) and Z^*_n p=10 Z_10= {1, 2, 3, 4, 5, 6, 7, 8, 9} Z*_10= [1, 3, 7, 9] phi(n)= 4
In this case \(\varphi\) is 4, as there are four elements in \(\mathbb{Z}^*_{10}\). As 2, 4, 5, 6, and 8 share a factor with 10, they are not included in \(Z^*_{10}\). For a prime number, \(\mathbb{Z}^*_{n}\) will be the same as \(\mathbb{Z}_{n}\). For example, for \(n=13\):
Computing Z_n (showing first 100) and Z^*_n p=13 Z_13= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} Z*_13= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] phi(n)= 12
In this case, \(\varphi=n-1 = 12\).
Coding
The coding is:
import sys import libnum def getZ(p): res = [] for x in range(1,p): if (libnum.gcd(x,p)==1): res.append(x) if (len(res)>50): break return res n=97 if (len(sys.argv)>1): n=int(sys.argv[1]) print("Computing Z_n (showing first 50) and Z^*_n") g=getZ(n) print(f"p={n}") z = set(range(1, n)) if (n>50): z = set(range(1, 50)) print(f"Z_{n}= {z}") print(f"\nZ*_{n}= {g}") print(f"\nphi(n)= {len(g)}")
Euler's Theorem
If we recall, \(p=10\), the multiplicative group of \(\mathbb{Z}_{10}\) is:
Computing Z_n (showing first 50) and Z^*_n p=10 Z_10= {1, 2, 3, 4, 5, 6, 7, 8, 9} Z*_10= [1, 3, 7, 9] phi(n)= 4
Thus \(\varphi\) is 4. We can check these, with Euler's Theorem, and where :
\(a^{\varphi(n)} \equiv 1 \pmod n \)
So for \(\mathbb{Z}_{10}\):
\(1^{\varphi(10)} = 1^4 = 1 \pmod {10}\)
\(3^{\varphi(10)} = 3^4 = 1 \pmod {10}\)
\(7^{\varphi(10)} = 7^4 = 1 \pmod {10}\)
\(9^{\varphi(10)} = 9^4 = 1 \pmod {10}\)