Exercise [16.01]

Sameed Zahoor · 16 Jul 2008, 12:30

Let the given set be represented by,
$\{a_{i}\in{Z^{+}\cup{\{0\}}|0\leq{a_{i}}<\ p}\}$ where p is the prime under consideration.Those who are familiar with number theory will recognize that these $a_{i}$ are what we call least residues modulo p.
For two arbitrary elements(i=m,n) we have
$a_{m}\equiv{a_{m}(mod\ p)}$ and
$a_{n}\equiv{a_{n}(mod\ p)}$
then
$a_{m}+a_{n}\equiv{a_{k}(mod\ p)}$ where $a_{k}$ is the remainder when $a_{m}+a_{n}$ is divided by

.(The division algorithm guarantees its existence)

If $a_{k}=0$ then $a_{n}$ can be considered the additive inverse of $a_{m}$ .It can be easily proved that every $a_{i}$ has an inverse $-a_{i}$ such that $0\leq{-a_{i}}<\ p$ .Hence, we can define subtraction just by replacing the "+" in the above equations by the "-" sign.(The given set forms a cyclic group under addition modulo p and hence the existence of an inverse is guaranteed)

We now need to define the multiplication operation for this set .Again,
$a_{m}\equiv{a_{m}(mod\ p)}$ and
$a_{n}\equiv{a_{n}(mod\ p)}$
Therefore,we have,
$a_{m}a_{n}\equiv{a_{j}(mod\ p)}$ (where $a_{j}$ is the remainder when $a_{m}a_{n}$ is divided by

)Note that

may be equal to

or

.

Unlike addition,every element will have a multiplicative inverse under this scheme only if "p" is prime!If we carefully examine the addition table for any value of "p" we will find that 0 appears in every row.Due to the commutativity of the addition operation every column will also have a 0 somewhere.Hence every element has an inverse.But the multiplication table won't contain 1(the multiplicative identity)in each row and column unless we choose p to be prime.In order to prove it we require the following lemma.

LEMMA.Given that $a_{m}a_{n}\equiv{a_{q}(mod\ p)}$ and $a_{m}a_{k}\equiv{a_{r}(mod\ p)}$ ,if $a_{n}$ is not equal to $a_{k}$ then $a_{q}$ is not equal to $a_{r}$ ( $a_{m}$ is not zero )
PROOF:(BY CONTRAPOSITIVE-If $a_{q}=a_{r}$ then $a_{n}=a_{k}$ )
We have ,
$a_{m}a_{n}\equiv{a_{q}(mod\ p)}$ and
$a_{m}a_{k}\equiv{a_{q}(mod\ p)}$
Subtracting the congruences we have,
$a_{m}(a_{n}-a_{k})\equiv{0(mod\ p)}$ or
$\frac{a_{m}(a_{n}-a_{k})}{p}=\lambda$ (an integer)
Since the numerator is relatively prime to the denominator $\lambda=0$ or
$a_{m}(a_{n}-a_{k})=0$
$\Rightarrow a_{n}=a_{k}$ (because $a_{m}$ is not zero)
QED

We disallowed $a_{m}$ to be zero because under multipication the first row and the first column will only contain zeroes.(It signifies multiplication of an arbitrary element by zero)What this lemma tells us is that for every non-zero element,the product with two different elements would yield two different residues.This means that there will be 'p' different residues in each row.(including zero)Hence,the multiplicative identity '1' would be present in each row.In formal terms,the non-zero elements constitute a group under multiplication.Hence,a multiplicative inverse exists for every non-zero element.We can thus,define division as multiplying by an inverse analogous to subtraction satisfying the requirements of a field in the process.

Exercise [16.01]

Who is online