Next: Index
Up: Numbers
Previous: A. Hints and Answers
  Index
B. Associativity and Distributivity of Operations in
Let
satisfy
. Let
. Let
and
be the binary operations on
defined by
Thus for all
,
![\begin{displaymath}
a+b=r\cdot n+(a\oplus_n b)\mbox{ for some }r\in\mbox{{\bf N}}.
\end{displaymath}](img1846.gif) |
(B.1) |
![\begin{displaymath}
a\cdot b=s\cdot n+(a\odot_n b)\mbox{ for some }s\in\mbox{{\bf N}}.
\end{displaymath}](img1847.gif) |
(B.2) |
We will show that
and
are associative by using the usual
properties of addition and multiplication on
.
B.3
Lemma.
Let
,
. If
, then
and
.
Proof:
- Case 1. Suppose
. Then by our assumptions,
and
So
Since
, it follows that
and since
is an integer
, so
. Then
, so
.
- Case 2. If
, use Case 1 with
and
interchanged.
B.4
Theorem.
is associative on
.
Proof: Let
. Then
![\begin{displaymath}
a+b=n\cdot t+(a\oplus_n b)\mbox{ for some }t\in\mbox{{\bf Z}}.
\end{displaymath}](img1863.gif) |
(B.5) |
![\begin{displaymath}
b+c=n\cdot r+(b\oplus_nc)\mbox{ for some }r\in\mbox{{\bf Z}}.
\end{displaymath}](img1864.gif) |
(B.6) |
![\begin{displaymath}
(a\oplus_n b)+c=n\cdot s+\left((a\oplus_n b)\oplus_n c\right)\mbox{ for
some }s\in\mbox{{\bf Z}}.
\end{displaymath}](img1865.gif) |
(B.7) |
![\begin{displaymath}
a+(b\oplus_n c)=n\cdot w+(a\oplus_n(b\oplus_n c))\mbox{ for
some }w\in\mbox{{\bf Z}}.
\end{displaymath}](img1866.gif) |
(B.8) |
By adding
to both sides of (B.5), we get
![\begin{displaymath}
(a+b)+c=nt+\left((a\oplus_n b)+c\right),
\end{displaymath}](img1867.gif) |
(B.9) |
and by adding
to both sides of (B.6), we get
![\begin{displaymath}
a+(b+c)=nr+\left(a+(b\oplus_n c)\right).
\end{displaymath}](img1868.gif) |
(B.10) |
Replace
in (B.9) by its value from (B.7) to get
![\begin{displaymath}
(a+b)+c=n(s+t)+\left((a\oplus_n b)\oplus_n c\right)
\end{displaymath}](img1870.gif) |
(B.11) |
and replace
in (B.10) by its value from (B.8) to
get
![\begin{displaymath}
a+(b+c)=n(r+w)+\left(a\oplus_n (b\oplus_n c)\right.)
\end{displaymath}](img1872.gif) |
(B.12) |
By (B.11) and (B.12) and the associative law in
,
the associativity of
follows from lemma (B.3).
B.13
Theorem.
is associative on
.
Proof: The proof is nearly identical with the proof that
is associative.
B.14
Theorem.
The distributive law holds in
; i.e., for all
,
Proof: We have
![\begin{displaymath}
b+c=n\cdot t+(b\oplus_n c)\mbox{ for some }t\in\mbox{{\bf Z}}.
\end{displaymath}](img1875.gif) |
(B.15) |
![\begin{displaymath}
a\cdot(b\oplus_n c)=n\cdot s + \left(a\odot_n(b\oplus_n c)\right)\mbox{ for
some }s\in\mbox{{\bf Z}}.
\end{displaymath}](img1876.gif) |
(B.16) |
![\begin{displaymath}
a\cdot b=n\cdot u+(a\odot_n b)\mbox{ for some }u\in\mbox{{\bf Z}}.
\end{displaymath}](img1877.gif) |
(B.17) |
![\begin{displaymath}
a\cdot c=n\cdot v+(a\odot_n c)\mbox{ for some }v\in\mbox{{\bf Z}}.
\end{displaymath}](img1878.gif) |
(B.18) |
Multiply both sides of (B.15) by
to get
![\begin{displaymath}
a\cdot(b+c)=n\cdot at+a\cdot(b\oplus_n c).
\end{displaymath}](img1879.gif) |
(B.19) |
Replace
in (B.19) by its value from (B.16) to get
![\begin{displaymath}
a\cdot(b+c)=n(at+s)+(a\odot_n(b\oplus_n c)).
\end{displaymath}](img1881.gif) |
(B.20) |
Now add equations (B.17) and (B.18) to get
![\begin{displaymath}
a\cdot b+a\cdot c=n\cdot(u+v)+\left((a\odot_n b)+(a\odot_n c)\right).
\end{displaymath}](img1882.gif) |
(B.21) |
We know that for some
,
and if we substitute this into (B.21), we obtain
![\begin{displaymath}
a\cdot b+a\cdot c=n(u+v+w)+\left((a\odot_n b)\oplus_n(a\odot_n
c)\right).
\end{displaymath}](img1885.gif) |
(B.22) |
From (B.20) and (B.22) and the distributive law in
, we conclude
The distributive law follows from lemma B.3.
Next: Index
Up: Numbers
Previous: A. Hints and Answers
  Index