Show that the set $$ \mathbb{Z}^*_p=\{1,2, \dots, p-1\} $$ where $p \in \mathbb{N}$ is prime, is a group under multiplication.


Associativity and identity:

Obviously, multiplication $\bmod p$ is associative and $1 \in \mathbb{Z}^*_p$ (identity element).


Let $k \in \mathbb{Z}^*_p$. Since $k<p$, $\gcd(k,p)=1$ and therefore Bezout's Lemma ensures that there exist $a,b \in \mathbb{N}$ s.t. $$ ak+bp=1\iff ak+bp \equiv 1 \space\bmod p \iff ak \equiv1 \bmod p $$

However, is the fact $a<p$ guaranteed, so that $a=k^{-1}\in \mathbb{Z}^*_p?$

Is it because the congruence class $\bar{a}$ with $a<p$ contains every $a_i$ you choose s.t. $ a_ik \equiv 1 \bmod p $?

  • 3
    $\begingroup$ I think you're mixing up integers and classes of integers modulo $p$. $\endgroup$ – Junkyards Jan 30 at 15:40
  • $\begingroup$ If that $a\in \Bbb Z$ is not in the list of the explicitly declared representatives, choose the one representative which is $a$ modulo $p$. $\endgroup$ – dan_fulea Jan 30 at 15:41
  • $\begingroup$ @Junkyards So, it would make more sense to work with classes: since there exists $a \in \mathbb{N}$ s.t. $$ a \bar{k} \equiv 1 \bmod p $$ the inverses exist? $\endgroup$ – LoneBone Jan 30 at 15:44
  • 1
    $\begingroup$ Yes, this is exactly the idea behind reasoning modulo $p$ $\endgroup$ – Junkyards Jan 30 at 15:46
  • $\begingroup$ If you show that if $gcd(a,p)=1$ and $gcd(b,p)=1$ than $gcd(a \cdot b,p)=1$ you are done, are'nt you? $\endgroup$ – Shaq Jan 30 at 15:49

I think you are mixing up integers and classes of integers modulo $p$. The set you just gave should not be set of integers, but a set of classes of integers modulo $p$. Indeed, it if was a set of integers, it would not be a group : $(p-1) \times 2$ is not in this set !

But if you consider these elements as classes of integers modulo $p$, then all of your reasoning makes sense, and the element $a$ you get is indeed the inverse you are looking for : it's a class of integers. It just turns out that there is a representative of it between $1$ and $p-1$.


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.