Why does not generator of multiplicative group generate all the members of group?

217 Views Asked by At

Generator(g) of multiplicative group (Zp where p is primary) is an element the power of which by modulo(g^i mod p) can produce all the elements of this group.

I have just tested this definition via python code and have not got the expected results. For example, lets take

p=11, so Z* = {1,2,3,4,5,6,7,8,9,10}

I found only 4 elements, powers of which are actually generates all the memebers: {8, 2, 6, 7}. That is what I got (for 1<=i<=p, but i tested i up to 10^10):

1^i  :{1}
2^i  :{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
3^i  :{1, 3, 4, 5, 9}
4^i  :{1, 3, 4, 5, 9}
5^i  :{1, 3, 4, 5, 9}
6^i  :{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
7^i  :{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
8^i  :{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
9^i  :{1, 3, 4, 5, 9}
10^i :{1, 10}

Does this mean nothing but 2,6,7,8 are generators? Could you explain what is it I misunderstood?

1

There are 1 best solutions below

0
On

Here is a (hopefully) simple explanation for the example of $3$:

$2$ is a generator of $(\mathbf Z/11\mathbf Z)^\times$, and $2^8=3$.

Now the order of $^k$, by definition, is the least natural number $r$ such that $\;(2^k)^r=2^{kr}\equiv 1\mod 11$; i.e.it is the least $r$ such that $kr$ is a multiple of $10$ (the order of $2$). In other words $kr$ is the l.c.m. of $k$ and $10$.

Now, we know that $\;10 k=\gcd(10,k)\cdot\operatorname{lcm}(10,r)$, so that $$ r=\frac{\operatorname{lcm}(10,k)}{k}=\frac{10}{\gcd(10,k)}=\frac{10}2. $$