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

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$$?

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.

• Thank you very much! however I'm a little confused even after I searched about multiplicative groups, in this wikipedia page: en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n they state they start from 0 to n-1. I thought that the additive or multiplicative notation changed only the internal binary operation without changing any property of the group itself... so an additive cyclic group goes from 0 to n, and a multiplicative cyclic group goes from 1 to n-1? Is this correct? So sorry for my confusion, I started this topic only two days ago Oct 20, 2021 at 10:34
• Shouldn't the order of the group be equal to 17 in both cases? Is it n-1 in multiplicative cyclic groups then? Oct 20, 2021 at 10:45
• @AndreaFarneti The article starts by saying "the integers coprime (relatively prime) to n from the set {0, 1, ..., n-1}". That means you have to filter the set and only keep the coprime integers. Oct 20, 2021 at 12:47
• @AndreaFarneti: …and 0 is never coprime to anything. Honestly, the lead paragraph of that Wikipedia article is a bit confusingly phrased. I can see why they do it that way — it's rather natural to start with the $n$-element ring of integers modulo $n$, drop the additive part and the elements with no multiplicative inverse, and study what remains as a multiplicative group. But if you're not starting that way, listing 0 as a potential element even though it can never be coprime to $n$ is kind of confusing. Oct 21, 2021 at 10:51
• @IlmariKaronen thank you very much! Now its pretty clear to me... or at least to a some degree just to know what we are talking about haha Oct 21, 2021 at 10:57