PRELIMINARIES AND PROPERTIES OF NUMBER SETS

Lecture 1

I hear and I forget.

I see and I remember.

I do and I understand.

---Chinese Proverb

ASSESSMENT of ALGEBRA COURSE

The unit consists of two components:

the lecture

the classroom tutorials.

In order to pass the unit first you must pass the tutorial
component and then pass the final exam at the end of the
semester.
During this semester you will take two tests. The dates of
the tests will be announced at least one week before the
tests take place.
You can obtain from each test at most 50 points.

To pass the tutorials you have to pass each test,
obtain 25 or more points from each test

.

If you obtain a sum of more than 80 points (grades
4+ or 5) from both of the tests you are exempt
from the examination (you don't have to take the
exam)

Points

Grad

e

Remark

[100,

90]

5

Excellent

(90,

80]

4+

Very Good

(80,

70]

4

Good

(70,

60]

3+

Fair

(60,

50]

3

Satisfactory

(50, 0]

2

Fail

Tutorial Classification:

If you don’t pass one or both of the tests you can

retake

the test/tests

at the end of the semester. In this case you obtain

at most grade at

level 4

(meaning that you can not be exempt from the examination).

To pass the exam you have to obtain 50% of the maximum score.

Text-books:

1,

“Algebra Liniowa 1,2”,

T. Jurlewicz, Z.Skoczylas, GiS

Wroclaw (you can buy it in the “basement” book store or
from senior students),

2.

“Theory and problems of matrices”,

F. Ayres Jr,

3.

"Matrix Analysis and Applied Linear Algebra

", C. D.

Meyer,

4. “Linear Algebra with Applications”,

G. Williams

5. “Linear Algebra with Applications”,

O.Bretscher

6. “Linear Algebra with Applications”,

S.J.Leon

or any other text-book, at university level, on Algebra.

Useful links:

http://mathforum.org/library/drmath/drmath.college.html

http://www.clarku.edu/~djoyce/complex/
http://www.math.odu.edu/~bogacki/lat/
http://www.ping.be/~ping1339/lintf.htm
etc.

library

ALGEBRA,
the word was derived from the title of a book written
in the yearly 800s, by

Mohammed Ibn Musa Al-Khowarizimi

Al Jabr Wa'l Muqabalah

It is concerned with straightforward solutions of equations
of first and second degree.

The title of the book means
"restoration by transposing terms from one side of an equation
to the other".

C: 1+ i, 2 +
3i,...

NATURAL

‘N’

INTEGERS ‘Z’

RATIONAL ‘Q’

REAL ‘R’

Leopold Kronecker:
„God Himself made the natural numbers; all else is the work of man”



,

,

,

e

5

2

7

COMPLEX ‘C’

Z: -1, -2, -3 ...

Q: 1/2, -1/2, 5/7...

R: ,

-
0.875

0

1

2

1

2

Numbers as points on a line

1.

Natural numbers

: 0, 1, 2, 3, 4, 5, .....

2.

Integers

(to subtract)

-4, 4,-9,...

3.

Rationals (to divide)

1/2, -4/6, 5/567,...

The rationals do not fill the whole line. To supplement them we
introduce
4.

Real numbers

(to fill up the whole line, divide area)

: 1, 0.2,

-0.5, , , ...

(are defined by limits of rational sequences or pairs of intervals)

Complex numbers

(to solve x

2

= -1)

are pairs of real numbers:

(3, 0) = 3 + i , (1,1) = 1+i , (0,1) = i

Other examples of 'number' sets and operations on them.

INTEGERS: ... , -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

Lets choose every third number,

... ,

-9

, -8, -7,

-6

, -5, -4,

-3

, -2, -1,

0

, 1, 2,

3

, 4, 5,

6

, 7, 8,

9

, ...

... ,-9,

-8

, -7, -6,

-5

, -4, -3,

-2

, -1, 0,

1

, 2, 3,

4

, 5, 6,

7

, 8, 9, ...

... , -9, -8,

-7

, -6, -5,

-4

, -3, -2,

-1

, 0, 1,

2

, 3, 4,

5

, 6, 7,

8

, 9, ...

glue them together

... ,

-9

, -8, -7,

-6

, -5, -4,

-3

, -2, -1,

0

, 1, 2,

3

, 4, 5,

6

, 7, 8,

9

, ...

... ,-9,

-8

, -7, -6,

-5

, -4, -3,

-2

, -1, 0,

1

, 2, 3,

4

, 5, 6,

7

, 8, 9, ...

... , -9, -8,

-7

, -6, -5,

-4

, -3, -2,

-1

, 0, 1,

2

, 3, 4,

5

, 6, 7,

8

, 9, ...

and call them ‘supernumbers’

0

1

2







How do we add and multiply
‘superumbers”?

Definition
For ‘supernumbers’ 0,1,2 let us define:

SuperAddition:

(p + q)

SUPER

= remainder after dividing p + q

by 3,

SuperMultiplication:

(p

 q)

SUPER

= remainder after dividing p



q by 3.

+

0

1

2

0

0

1

2

1

1

2

0

2

2

0

1

0

1

2

0

0

0

0

1

0

1

2

2

0

2

1



OR a  b (mod m) iff

the numbers a and b have the same remainder when divided by m.

Example
1. for all

a  b (mod 1).

(The remainder is zero)

2.

8  13 (mod 5)

because

(13 - 8) = 1· 5
or 8=1·5 + 3 and 13=2·5 + 3

3.

-17  1 (mod 6)

because

(1+17) = 3· 6
or -17= -3·6 + 1 and 1=0·6 + 1

Can we generalise the above ‘supernumbers’?

Yes,

and we obtain the congruence ‘modulo m’.

*

iff = ‘if and only if’

Definition
Numbers are congruent modulo m,
a  b (mod m) iff

*

m |( b – a ).

Read:

a is congruent to b modulo

m.

gluing

PROPERTIES

(reflexiv)

a  a (mod m);

(symmetric) a  b (mod m) then b  a (mod

m);

(transitive) a  b  c (mod m) then a  c (mod

m).

The congruence class (equivalence class) of the integer a is
denoted by
[a]

n

= { ..., a − 2n, a − n, a, a + n, a + 2n, a + 3n, ...}.

PROPERTIES

If a  b (mod m) and c  d (mod m),

then:

1. a + c  (b + d) (mod m)

2. a



c  (b  d) (mod m)

3. a

N

 b

N

(mod m).

Definition (modulo operations)

p, q are integers

(p + q) (mod m) = remainder after dividing p + q by m,
(p



q) (mod m) = remainder after dividing p



q by m.

The sum and product of 'glued' numbers

NOTE !!!!!

There is another

similar notation

in Computer Sciences: the modulo operation.

It is the remainder in division sometimes written as "

mod

",

so we write "

14 mod 12 = 2

".

This meaning of "mod" is different from the congruence "mod"

it is true to say "

38 ≡ 14 (mod 12)

" ,

but it is

not true to say "38 = 14 mod 12"

— 38 is congruent to 14

modulo 12,
but the remainder of 14 divided by 12 is 2, not 38.

To avoid this confusion,
the congruence relation is sometimes expressed by using modulo
instead of mod
like "38 ≡ 14 (modulo 12)" in computer science.

In

CRYPTOGRAPHY

, modular arithmetic is used in public key systems

such as RSA and Diffie-Hellman, and is used in and a variety of
symmetric key algorithms including AES, IDEA, and RC4.

In

COMPUTER SCIENCE

, modular arithmetic is often applied in

bitwise operations and other operations involving fixed-width,
cyclic data structures.

In the

VISUAL ARTS

, modular arithmetic can be used to create

artistic patterns based on the multiplication and addition tables modulo n.

In

MUSIC,

modular arithmetic is used, where octave and enharmonic

equivalency occurs.

APPLICATIONS

POSITIONAL NUMBER SYSTEMS

The previously proven facts give the possibilities to express the
notation of
a number in another positional system other than the popular
decimal one.

Let us fix a natural number m > 0, which shall be treated as
the base of the positional system.

Theorem
Every natural number can be uniquely represented as:
n = a

k

m

k

+ a

k-1

m

k-1

+ ..... + a

1

m + a

0

, where 0

 a

0

< m.

The number

m is called the base

of the system.

The number n, with fixed m, is represented by a system of coefficients
a

k

a

k-1

... a

1

a

0

which is the representation of n in a system of

base m;

a

k

, a

k-1

, ... ,a

0

are the digits

in this representation.

One can convert a number from base n to
base m.

2 binary

3 ternary
4 quaternary
5 quinary
6 senary
7 septimal

8 octal

9 monary

10 decimal

12 duodecimal

16
hexadecimal

Every real number can be represented by a "nonterminating
decimal"

POSITIONAL NUMBER SYSTEMS OF BASE N

Sometimes three or four of the digits are grouped together,
this means that the new base is 2

3

(octal)

or 2

4

(hexadecimal).

A

bit

refers to a digit in the binary numeral system

(base 2).
(

b

inary

dig

it

)

For example, the number 1001011 is 7 bits long.

A

bit

of storage is like a light switch; it can be either on (

1

) or off (

0

).

A single bit is a one or a zero, a true or a false, a "flag" which is "on" or "off",

Binary digits

are almost always used as the basic unit of

information storage and communication in digital computing.

DEFINITION

The

prime numbers

are those natural numbers p, excluding p =

0, p = 1 which are only divisible by 1 and itself,

i.e. for every natural n: if n |p then n = p or n = 1.

The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19,...

Fundamental Theorem of Arithmetic

Any integer N can be represented as a product of primes.
Such a representation is unique up to the order of prime factors

6 = 2·3, 15 = 3 ·5, 36 = 2 ·2 ·3 ·3

DEFINITION

For non-negative integers m

1

, m

2

, ..., m

k

,

their

Greatest Common Divisor

is defined as

 GCD(m

1

, m

2

, ..., m

k

) = max{s: s|m

i

, for i = 1, ..., k},

where, as always, "s|m" means that s divides m exactly.

The Greatest Common Divisor

- the largest number which divides all m

1

, m

2

, ..., m

k

The algorithm is based on the following two observations

:

1. If b|a then GCD(a, b) = b.
This is indeed so because no number (b, in particular) may have
a divisor greater than the number itself (I am talking here of non-negative

integers.)

2. If a = bt + r, for integers t and r, then GCD(a, b) = GCD(b, r).

Indeed, every common divisor of a and b also divides r.
(a)Thus, GCD(a, b) divides r.
(b) And of course, GCD(a, b) divides b.
Therefore, GCD(a, b) is a common divisor of b and r and hence GCD(a, b) ≤

GCD(b, r).

The reverse GCD(b, r) ≤ GCD(a, b)

is also true because

every divisor of b and r also divides a.

EUCLID'S
ALGORITHM

Given two numbers a,b not prime to one another, find their
greatest common divisor.
GCD(a,b)=?

!

Corollary
For every pair of whole numbers a and b there exist
two integers

s

and

t

such that a

s

+ b

t

= GCD(a, b).

Example
2322×20 + 654×(-71) = 6.

Example 1
Use the Euclidean Algorithm to find the GCD(13013, 390).
a=

13013

, b =

390

.

a = b · t + r

13013

=

390

 33 + 143,

390

= 143 2 + 104

143 =104  1 + 39

104 = 39  2 + 26

39 = 26  1 + 13

26 = 13  2 + 0

GCD(13013, 390) = 13.

First mentions:
by Brahmagupta (बबबबबबबबबबब) (589–668) an Indian
mathematician and astronomer.

The Chinese Remiander Theorem
Introduction

The original form of the theorem, was contained in a third-
century AD book by a Chinese mathematician Sun Tzu.

It is a statement about simultaneous congruences.

Counting the number of soldiers in an army.

The general has the soldiers quickly line up in groups of 3, 5, 7, 11
and counts the remaining soldiers that can't make complete groups.

After enough of these tests are made, the general can quickly calculate
how many soldiers he has exactly;

thus he has done a 3 hour ‘headcount’

in 2 minutes.

The larger the product n = p

1

...p

k

the more accurate we are.

Chinese Remainder Theorem

Suppose p

1

, p

2

, ..., p

n

are positive integers which are pair wise relatively

prime

(meaning GCD( p

i

, p

j

) = 1 whenever i  j) .

Then for any given integers q

1

, q

2

, ...,q

n

,

there exists an integer q solving the system of simultaneous

congruencies :

q  q

i

(mod p

i

) for i =1…n.

Furthermore, all solutions x to this system are

congruent modulo the product n = p

1

...p

k

i.e. can be obtained by adding a multiple of n = p

1

...p

k

to x

Example
Find a number q, which divided by 5 will give remainder 3, and which

divided by 7

will give remainder 4:
q  3(mod5) i.e. q = 5·k + 3

q  4(mod7) i.e. q = 7·m + 4

We have to find k and m such that 5 · k + 3 = 7 · m + 4
or 5 · k - 7 · m = 1
--------------------------------------------------------------------------------------------------------

----

The Euclid's Algorithm:
7 = 5·1 + 2  2 = 7 - 1·5

5 = 2·2 + 1  1 = 5 - 2·2

2 = 1·2 + 0
--------------------------------------------------------------------------------------------------------

----

So we can write
1= 5 - 2·2 = 5 - 2·(7- 1·5) = 5 - 2·7 + 2·1·5 =

| we group the terms with ‘5’

and the terms with ‘7’ |

= 3 ·5 - 2 ·7

5 · 3 - 7· 2 = 1

We see that k = 3 and m = 2, so q = 5·3 + 3 = 18.

Thus one of the possible solutions can be number q = 18 or
all solutions q = 18 + n·5·7 for any integer n.

THE CIPHER ALGORITHM:

RSA algorithm – public key cryptography (by Ronald Rivest, Adi

Shamir, Leonard Adleman)

1. We have to choose two prime numbers P and Q (large ones
more than 1024 – bit),
2. Calculate the product N = PQ,
3. Choose a special E – using PQ and (P-1)(Q-1) (on next page),
4. Compute a D using PQ and (P-1)(Q-1) (on next page),
5. Destroy P and Q.

We have

(PQ, E) - the public key

, (PQ – modulus, E - public exponent)

D - the private key

– very secret!!! (D – private exponent)

You can publish your public key freely, because there are no
known fast and easy methods of calculating D, P, or Q given
only

(PQ, E)

(your public key).

If

P

and Q are each 1024 bits long, the sun will burn out

before the most powerful computers presently in existence
can factor your modulus into P and Q.

We have two large P and Q.

We choose E such that E is greater than 1, E is less than PQ, and E
and
(P-1)(Q-1) are relatively prime. E does not have to be prime, but it
must be odd.

Compute D such that (DE - 1) is evenly divisible by (P-1)(Q-1). We
write this as DE = 1 (mod (P-1)(Q-1)).

The encryption function is

C = T

E

(mod PQ)

where C is the encripted text (a positive integer), T is the plaintext (a
positive integer). The message being encrypted, T, must be less than
the modulus, PQ.

The decryption function is

T = C

D

(mod PQ)

EXAMPLE (for primes P=5, Q=17)

PQ

=

85

= 5  17 (public),

E

=

5

(public exponent),

D

=

13

(private)
(

P

-1)(

Q

-1) = 64 GCD(

E

, 64) = 1

64|(

5

D

- 1 )

Decrypting

(with the use of the private key

D

=

13

):

79

13

(mod 85) = 24.

So we recovered the original message x.

We want to

encrypt

the letter ‘x’ = 24

(x is the 24-th letter of

the alphabet)

24

5

(mod

85

) = 79 .

The encryptyed ‘x’ is 79.

Rev. Euklid

The floor function of a real number x, denoted

 

   or

floor(x),

is the largest integer less than or equal to x i.e.

 

x

 





x

n

Z

n

x







:

sup

For example: floor(2.9) = 2, floor(−2) = −2 and floor(−2.3)
= −3.

For nonnegative x, a more traditional name for floor(x)
is
the integral part or integral value of x sometimes
denoted by E(x)

The floor function

The ceiling function, given x, ceiling(x) also denoted by

 

     is the function

defined as

 

        . This is, the smallest integer not less than x.

The ceiling function

For example, ceiling(2.3) = 3, ceiling(2) = 2 and ceiling(−2.3) = −2.

 

x