Next:
Solving Congruences
Up:
The classical sets of
Previous:
Applications of prime factorisation
Contents
Modular Arithmetic
Definition 6.7.1
If
and
,
we say that
and
are ``congruent mod(ulo)
'' if
. We write
.
It is a bit like
but less restrictive. It has some nice properties:
,
if
then
,
if
and
then
.
Also, if
and
,
.
Lemma 6.7.2
For a fixed
, each integer is congruent to precisely one of the integers
Proof
. Take
. Then
for
and
. Then
.
If
then
, so
and thus
.
Example 6.7.3
No integer congruent to
is the sum of two squares.
Proof
. [Solution] Every integer is congruent to one of
. The square of any integer is congruent to 0 or
and the result is immediate.
Similarly, using congruence modulo 8, no integer congruent to
is the sum of 3 squares.
Next:
Solving Congruences
Up:
The classical sets of
Previous:
Applications of prime factorisation
Contents
root 2002-06-10