2
$\begingroup$

I wanna show that the non-zero elements of $\mathbb Z_p$ ($p$ prime) form a group of order $p-1$ under multiplication, i.e., the elements of this group are $\{\overline1,\ldots,\overline{p-1}\}$. I'm trying to prove that every element is invertible in the following manner:

Proof (a)

By Bézout's lemma given $\bar a\in\mathbb Z_p$, there are $x,y \in \mathbb Z$ such that

$ax+py=1\implies\overline {ax+py}=\overline 1\implies \overline a \overline x+\overline p\overline y=\overline1\implies \overline a \overline x+\overline 0=\overline1\implies \overline a\overline x=\overline1$

There are two problems with this proof, first $\overline 0$ is not defined, because $\overline 0$ is not defined because isn't in $\{\overline 1,\ldots \overline {p-1}\}$ secondly the sum is not defined, because I'm using multiplication in this case.

Proof (b)

By Fermat's little theorem, for each $\overline a \in \mathbb Z_p$, we have:

$a^{p-1}\equiv 1$ (mod $p$), then $\overline {a^{p-2}}$ is an inverse to $\overline a$.

My problem with this proof is why $\overline {a^{p-2}}\in \{\overline1,\ldots,\overline{p-1}\}$.

I've already known these proofs, but with a little bit more experience, I found these lacks of rigor.

Thanks in advance.

$\endgroup$
  • $\begingroup$ A finite integral domain is a field: this is because for any nonzero $a$ the multiplicative map $x\mapsto ax$ is injective and hence bijective, so in particular $1$ has a preimage $a^{-1}$. Thus every nonzero $a$ has a multiplicative inverse. No number theory needed. By the way, all of the terms you reference - $\bar{0}$, "the sum," and $\overline{a^{p-2}}$ - are perfectly well-defined and the latter are in $\{\bar{1},\cdots,\overline{p-1}\}$. You should make sure that you understand the basics of the quotient ring first - how the elements (equivalence classes) and its operations are defined. $\endgroup$ – anon Jul 27 '13 at 7:30
  • $\begingroup$ @anon I would like to prove this without using ring concepts, in an abstract algebra course, we start with groups, before rings. $\endgroup$ – user42912 Jul 27 '13 at 7:57
1
$\begingroup$

With respect to (a) first:

Why isn't $\bar0$ defined? It seems you're working in $\mathbb{Z}/p\mathbb{Z}$ and not only the group of units; thus $\bar{0}$ is defined just fine. Secondly, it seems you are deliberately forgetting that $\mathbb{Z}/p\mathbb{Z}$ is a ring and not just a group, i.e. that you have both addition and multiplication. Perhaps you thought in both cases that you were working in the group of units instead of the ring of integers mod $p$?

What you should do is work in the ring, realize $a$ has a (non-zero unital) inverse, and conclude that $a$ is in the group of units. This angle is the one espoused by (a), and is what makes it fine.

With respect to (b):

I like this one a lot less because standard proofs of Fermat's little theorem use (often explicitly) the size of the group of units (and Lagrange's theorem). Or they use the size of the group of units and then multiply them all together, do a little cancellation (maybe with Wilson's theorem), and get the result. But in both cases, you use the size of the group of units, so there is danger of self-referentiality.

But there are ways of proving Fermat's little theorem avoiding knowing the size of the group of units; so let's assume we've done that.

A priori, you only know that $a^{p-2} \in \mathbb{Z}/p\mathbb{Z}$, i.e. that it could be $0$. Well, is it $0$? If it were $0$, this means that $p \mid a^{p-2}$. But $p$ is prime, so if $p \nmid a$ then $p \nmid a^{x}$. So $a^{p-2} \neq 0$, and thus is in $1, \ldots, p-1$. (I stopped using bars, but every number here is in $\mathbb{Z}/p\mathbb{Z}$).

$\endgroup$
  • $\begingroup$ $\overline 0$ is not defined because isn't in $\{\overline 1,\ldots \overline {p-1}\}$ $\endgroup$ – user42912 Jul 27 '13 at 7:43
  • $\begingroup$ I'm trying to do this without the definition of ring, as if I would be a student who have never studied this before. $\endgroup$ – user42912 Jul 27 '13 at 7:44
1
$\begingroup$

$\overline{0}$ is the equivalence class of $0$, that is, the multiples of $p$. We can use this because multiplication and addition are well defined ring operations in $\mathbb Z_n$. The precursor to this proof is to show that addition and multiplication over the integers modulo $n$ are, in fact, well defined (i.e. give you the same answer regardless of which representative of an equivalence class is chosen). By using $\overline{0}$, we have stepped away from the multiplicative group. However, the math still works, and it tells us that every non-zero element of $\mathbb Z_p$ has a multiplicative inverse.

The answer to your second question is "because of a)".

$\endgroup$
1
$\begingroup$

Don't talk about rings if you don't want to, but you still must talk about the additive abelian group $\,\Bbb Z_p\,$ and you can work with it all along, remarking

$$\forall\,k\in\Bbb Z\;,\;\;kp=\overline 0=0\pmod p$$

Then you can work comfortably with Bezout's lemma as you did, including $\,\overline 0\,$ and the sum, of course.

Certainly the above is the same as talking about the ring of residues, which as far as I know is usually done even in the first undergraduate year as an example of field which is not one of the ones beginning students are used to, so I don't think a beginner wouldn't work without the additive operation and only with the multiplicative one.

About question (2):

$$\forall\,\overline a\in \Bbb Z_p^*\;\wedge\;\forall\,k\in\Bbb Z\;,\;\;\overline a^k\in\Bbb Z_p^*$$

and this much is true for any group (written multiplicatively), abelian or not, finite or not.

$\endgroup$
0
$\begingroup$

You don't need to have ring concepts at hand to define $\overline{0}$. Congruences, i.e. basic properties of integers are enough to do that.

In a typical first course in abstract algebra the order of presentation of material is: integers, residue classes of integers (with primes, gcds, Bezout and FTA interspersed), arithmetic with residue classes... Only then groups and later rings at which point we make the observation that we get examples of groups, rings and fields from certain sets of residue classes.

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