3
$\begingroup$

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

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Oct 20, 2021 at 10:34
  • $\begingroup$ Shouldn't the order of the group be equal to 17 in both cases? Is it n-1 in multiplicative cyclic groups then? $\endgroup$ Oct 20, 2021 at 10:45
  • $\begingroup$ @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. $\endgroup$
    – Nayuki
    Oct 20, 2021 at 12:47
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 21, 2021 at 10:51
  • $\begingroup$ @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 $\endgroup$ Oct 21, 2021 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.