problem with a discrete logarithm/cyclic groups example... can anyone clarify this concept for me?

Question

I was watching this really short video about the discrete logarithm example: https://www.youtube.com/watch?v=SL7J8hPKEWY and at 0:38 they show all the possible values that you can get if $p = 17$ and $g = 3$. At 1:00 they state that the solution is equally likely to be any integer between 1 and 17.

My questios are;

• What about $0$? From what I learned about cyclic groups, $17 \bmod 17$ is just $0$. I suppose they meant a number between $0$ and $16$ then, but... why isn't the $3^x = 0 \bmod 17$ shown in the video then?

• If $3$ is really a primitive root of 17, a.k.a, a generator, that value of $x$ should exist, right? Or am I missing something?

• If $p = 17$, shouldn't the order of the group be equal to $17$ too? They are missing a value of $x$ then.

• If I'm right, what is the value of $x$ in $3^x = 0 \bmod 17$?

Answer 1

The group you are looking at is the multiplicative group modulo $17$ which the powers of $3$ generate. As a set, for general $n$ this does not include $0$ and is usually written as $$ (\mathbb{Z}_n^\ast,\cdot) $$ where $\mathbb{Z}_n^\ast \subseteq \{1,2,\ldots,n-1\}$ for any positive integer $n\geq 2.$

If $n=p$ is a prime then this set is actually all of $\{1,2,\ldots,p-1\}$ Otherwise, it is just the set of elements in $\mathbb{Z}_n$ that is relatively prime to $n.$ If $n=p$ a prime, then the group is also cyclic meaning a single element $g$ can generate all its members as powers $g^i\pmod p.$

For your example $p=17,$ and $g=3.$

Edit: If $n$ is nonprime, say $n=pq$ where $p\neq q$ are primes then there are $n/p$ elements in $\{0,1,\ldots, n-1\}$ that are divisible by $p.$ There are $n/q$ elements in $\{0,1,\ldots, n-1\}$ that are divisible by $q$. Since zero is divisible by both we get $$ n\left(1-\frac{1}{p}\right)\left(1-\frac{1}{q}\right) $$ elements that are relatively prime to $n$ which is the size of the multiplicative group.

For general $n$ we have $\varphi(n)$ elements in the group, where $\varphi(\cdot)$ is Euler’s totient function.