0
$\begingroup$

In RSA proof it can be proved that $\mathbb{Z}^*_n$ is closed under multiplication. Can it be also proved that $\mathbb{Z}_n$ is closed under multiplication? If yes, then how?

$\endgroup$
  • 1
    $\begingroup$ $\mathbb{Z}_n$ is closed under multiplication by definition of the multiplication in $\mathbb{Z}_n$; which is about: $a\cdot b$ is $b+\dots+b$ repeated $a$ times, where $+$ is addition in $\mathbb{Z}_n$ (that is, modulo $n$), which result is in $\mathbb{Z}_n$. Perhaps you are really asking something else? $\endgroup$ – fgrieu May 6 '14 at 7:58
2
$\begingroup$

$Z_n=\{0,\ldots,n-1\}$ is not a multiplicative group (I assume that this is what you mean by closed under multiplication in this context, see below) because it contains the zero (this element is not invertible) and furthermore if $n$ is not prime, all elements that are not co-prime to $n$ also have no multiplicative inverse. $Z_n^*$ are the elements from $1$ to $n-1$ that are co-prime to $n$ and thus all invertible and thus this set forms a group under multiplication (modulo $n$).

To expand on the "closed under multiplication": The set $\{0,\ldots,n-1\}$ is indeed closed under multiplication modulo $n$ meaning that whenever you multiply two elements modulo $n$ the result will be in this set. However, this is not sufficient to form a multiplicative group (you require an identity, inverses and to show the associativity of the group law).

$\endgroup$
  • 1
    $\begingroup$ "this element is not invertible", but that does not necessarily stop the set from being closed under multiplication. $\;$ $\endgroup$ – user991 May 6 '14 at 6:12
  • $\begingroup$ @Ricky Demer You are right. I assumed that the OP means a group under multiplication when saying closed under multiplication in this context. $\endgroup$ – DrLecter May 6 '14 at 6:15

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.