Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
$\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? –  fgrieu May 6 at 7:58

1 Answer 1

up vote 2 down vote accepted

$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).

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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