[Back] In number theory, \(Z_n\) is the set of non-negative integers less than n ({0,1,2,3...n-1}). \(Z^*_n\) is then a subnet of this which is the multiplicative group for \(Z_n\) modulo \(n\). The set \(Z^*_n\) is the set of integers between 1 and n that are relatively prime to n (ie they do not share any factors). If n is prime, then \(Z^*_n\) is the values up to (n − 1).

## Multiplicative group for \(Z_n\) [ \(Z^*_n \)] modulo \(n\) |

## Theory

In number theory, \(Z_n\) is the set of nonnegative integers less than n ({0,1,2,3...n-1}). \(Z_n\) also defines a set of the residues modulo *n*.

\(Z^*_n\) is then a subnet of this which is the multiplicative group for \(Z_n\). The set \(Z^*_n\) is the set of integers between 1 and *n* that are relatively prime to *n* (ie they do not share any factors). If *n* is prime, then \(Z^*_n\) is the values up to (*n* − 1).

If we want \(g\) to be generated from multiplicative group for \(Z_n\) modulo \(n\), we would define: \(g \in Z^*_n\).

If we want \(g\) to be generated from multiplicative group for \(Z_n\) modulo \(n^2\), we would define: \(g \in Z^*_{n^2}\). An example is [here].

For example, if we have 9, then the \(Z^*_n\) group is:

Multiplicative group for Zn up to 100 is: 1 2 4 5 7 8

because 3 is a factor of 9, along with 6 (2x3).

For 91 we get:

Multiplicative group for Zn up to 100 is: 1 2 3 4 5 6 8 9 10 11 12 15 16 17 18 19 20 22 23 24 25 27 29 30 31 32 33 34 36 37 38 40 41 43 44 45 46 47 48 50 51 53 54 55 57 58 59 60 61 62 64 66 67 68 69 71 72 73 74 75 76 79 80 81 82 83 85 86 87 88 89 90 The number of values is: 72

We can see that factors of 7 are not included, such as 14, 21, etc, and also factors of 13, such as 26, 39, and so on.

If the value is a prime number, all the values will be included up to (n-1), as it will not share any factors. For example, 97 is a prime number:

Value is: 97 Multiplicative group for Zn up to 100 is: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 The number of values is: 96

## Coding

The following is an outline of the code:

number=1763*1763 import sys if (len(sys.argv)>1): number=int(sys.argv[1]) count=0 def gcd(a,b): while b > 0: a, b = b, a % b return a print "Value is:\t",number print "Multiplicative group for Zn up to 100 is:" for i in range(1,100): if (gcd(number,i)==1): print i, count=count+1 print "\nThe number of values is: ",count