0
$\begingroup$

For $n \in \mathbb{N}$, $n>1$, let $\mathbb{Z}_n^\times := \{1, \dots, n-1\}$

For positive integers $a$ and $n$, show that $ax \bmod{n} = 1$ has a solution if and only if $\gcd(a,n)=1$.

I have this part of the proof solved.

Using the above show that $(\mathbb{Z}_n^\times,\cdot)$, where $a\cdot b := (ab) \bmod{n}$, is a group if $n$ is a prime.

This is the part I am having trouble solving. I am using Euclids lemma and that multiplication is associative in the DA. I think I have to show closure, but I am not sure how using the above proof.

$\endgroup$
  • $\begingroup$ It's saying "use the above proof" just to help you realize that $$\{ 1, 2, \dots, p-1\} = \mathbb Z_p^\times$$ when $p$ is prime. To prove that what you have is a group, show that it satisfies the group axioms. $\endgroup$ – Andrew Tawfeek Oct 22 '17 at 23:31
0
$\begingroup$

Closure is actually enough in a finite group. Not sure if you have proven that or not yet. Otherwise, the key is that every element of $\{1, 2, \ldots, p-1\}$ is relatively prime to $p$. Suppose $d$ was a common divisor with $d>1$, then $d \mid p$, a prime, which is impossible. This means from what you have shown above it has an inverse under multiplication.

$\endgroup$

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.