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. For \(Q_n\) we represent with (Z/nZ)* is the subgroup of squares, and where we determine the valid values for \(x=y^2 \pmod p\) and where GCD(x,N)==1.
(Z/nZ)* - the multiplicative group of Z / nZ and Qn - the subgroup of squares in (Z/nZ)* |
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\).
\(Q_n\) - (Z/nZ)* is the subgroup of squares
FOr this we determine the valid values for \(x=y^2 \pmod p\) and where GCD(x,N)==1. For N=16 we get get:
x=0 y=0 (mod 16) = 0 gcd(0,16)=16 x=1 y=1^2 (mod 16) = 1 gcd(1,16)=1 Success! x=2 y=2^2 (mod 16) = 4 gcd(2,16)=2 x=3 y=3^2 (mod 16) = 9 gcd(3,16)=1 Success! x=4 y=4^2 (mod 16) = 0 gcd(4,16)=4 x=5 y=5^2 (mod 16) = 9 gcd(5,16)=1 Success! x=6 y=6^2 (mod 16) = 4 gcd(6,16)=2 x=7 y=7^2 (mod 16) = 1 gcd(7,16)=1 ...
In the end we get: {1,9} and the order is 2.
Coding
The coding is:
import math import sys N=36 a = set() if (len(sys.argv)>1): N=int(sys.argv[1]) for x in range(N): if (math.gcd(x,N)!=1): continue; if (x not in a ): a.add(x) print (f"N={N}") print("\n(Z/nZ)* is the multiplicative group of Z/nZ") print (sorted(a)) print(f"Order is {len(a)}") a = set() for x in range(N): if (math.gcd(x,N)!=1): continue; y=pow(x,2,N) if (y not in a ): a.add(y) print("\nQn - (Z/nZ)* is the subgroup of squares") print (sorted(a)) print(f"Order is {len(a)}")
A sample run is:
N=17 (Z/nZ)* is the multiplicative group of Z/nZ [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] Order is 16 Qn - (Z/nZ)* is the subgroup of squares [1, 2, 4, 8, 9, 13, 15, 16] Order is 8
If we try N=10 we get:
N=10 (Z/nZ)* is the multiplicative group of Z/nZ [1, 3, 7, 9] Order is 4 Qn - (Z/nZ)* is the subgroup of squares [1, 9] Order is 2