Mark Lemmon Close - Mathematics for Computer Scientists

Gareth J. Janacek & Mark Lemmon Close

Mathematics for Computer Scientists

Mathematics for Computer Scientists
2014 Gareth J. Janacek, Mark Lemmon Close & Ventus Publishing ApS ISBN 978-87-7681-426-7

Mathematics for Computer Scientists Contents

Contents

Mathematics for Computer Scientists Introduction

Introduction

The aim of this book is to present some the basic mathematics that is needed by computer scientists. The reader is not expected to be a mathematician and we hope will find what follows useful.

Just a word of warning. Unless you are one of the irritating minority mathematics is hard. You cannot just read a mathematics book like a novel. The combination of the compression made by the symbols used and the precision of the argument makes this impossible. It takes time and eort to decipher the mathematics and understand the meaning.

It is a little like programming, it takes time to understand a lot of code and you never understand how to write code by just reading a manual - you have to do it! Mathematics is exactly the same, you need to do it.

Chapter 1 Numbers

Defendit numerus: There is safety in numbers

We begin by talking about numbers. This may seen rather elementary but is does set the scene and introduce a lot of notation. In addition much of what follows is important in computing.

1.0.1 Integers

We begin by assuming you are familiar with the integers
1,2,3,4,...,101,102, ...,n,...,2 32582657 1,...,

sometime called the whole numbers. These are just the numbers we use for counting. To these integers we add the zero, 0, dened as
0+ any integer n = 0+ n = n+ 0 = n

Once we have the integers and zero mathematicians create negative integers by dening (n) as:
the number which when added to n gives zero, so n+ (n)=(n)+ n = 0.

Eventually we get fed up with writing n+(n)= 0 and write this as nn = 0. We have now got the positive and negative integers {...,3,2,1, 0, 1, 2, 3, 4,...}
You are probably used to arithmetic with integers which follows simple rules. To be on the safe side we itemize them, so for integers a and b

1. a+ b = b+ a
2. a b = b a or ab = ba
3. a b =ab

7 4. (a)(b)= ab

5. To save space we write a k as a shorthand for a multiplied by itself k times. So
3
= 3 3 3 3 and 2 = 1024. Note a n a m = a n+m
6. Do note that n=1.
Factors and Primes

Many integers are products of smaller integers, for example 2 3 7 = 42. Here 2, 3 and 7 are called the factors of 42 and the splitting of 42 into the individual components is known as factorization. This can be a dicult exercise for large integers, indeed it is so dicult that it is the basis of some methods in cryptography.

Of course not all integers have factors and those that do not, such as 3, 5, 7, 11, 13,... , 2 216091 1,...
are known as primes. Primes have long fascinated mathematicians and others see

http://primes.utm.edu/,
and there is a considerable industry looking for primes and fast ways of factorizing integers.

To get much further we need to consider division, which for integers can be tricky since we may have a result which is not an integer. Division may give rise to a remainder, for example

9 = 2 4+ 1. and so if we try to divide 9 by 4 we have a remainder of 1 . In general for any integers a and b
b = k a+ r

where r is the remainder. If r is zero then we say a divides b written a | b.A single vertical bar is used to denote divisibility. For example 2 | 128, 7 | 49 but 3 does not divide 4, symbolically 3 4.

Aside

To find the factors of an integer we can just attempt division by primes i.e. 2, 3, 5, 7, 11, 19,.... If it is divisible by k then k is a factor and we try again. When we cannot divide by k we take the next prime and continue until we are left with a prime. So for example:

1. 2394/2=1197 cant divide by 2 again so try 3
9
2. 1197/3=399

3. 399/3 = 133 cant divide by 3 again so try 7 ( not divisible by 5) 3. 399/3 = 133 cant divide by 3 again so try 7 ( not divisible by 5) 4. 133/7 = 19 which is prime so 2394 =2 3 3 7 19
2 3 3 7 19
Modular arithmetic
The mod operator you meet in computer languages simply gives the remainder operator you meet in computer languages simply gives the remainderafter division. For example,
1. 25 mod 4= 1 because 25 4= 6 remainder 1.
4= 1 because 25
2. mod 5= 4 since 19 = 6 remainder 1. 19= 3 5+ 4 .
5= 4 since 19= 3 5 + 4 .
3. 24 mod 5= 4.
5= 4. 4. 99 mod 11= 0.

11 = 0. There are some complications when negative numbers are used, but we will ignore There are some complications when negative numbers are used, but we will ignorethem. We also point out that you will often see these results written in a slightly them. We also point out that you will often see these results written in a slightly 24= 4 mod 5 or 21= 0 mod 7. which just means 24 mod 5=

24
=
4
mod
4
27 0
and 21=mod 7 = 7. which just means 24 mod 5=
or mod

7 = 0 Modular arithmetic is sometimes called clock arithmetic. Suppose we take a Modular arithmetic is sometimes called clock arithmetic. Suppose we take a24 hour clock so 9 in the morning is 09.00 and 9 in the evening is 21.00. If I start 24 hour clock so 9 in the morning is 09.00 and 9 in the evening is 21.00. If I starta journey at 07.00 and it takes 25 hours then I will arrive at 08.00. We can think a journey at 07.00 and it takes 25 hours then I will arrive at 08.00. We can thinkof this as 7+25 = 32 and 32 mod 24 = 8. All we are doing is starting at 7 and of this as 7+25 = 32 and 32 mod 24 = 8. All we are doing is starting at 7 andgoing around the (25 hour) clock face until we get to 8. I have always thought this going around the (25 hour) clock face until we get to 8. I have always thought thisis a complex example so take a simpler version.
is a complex example so take a simpler version. Four people sit around a table and we label their positions 1 to 4. We have a Four people sit around a table and we label their positions 1 to 4. We have apointer point to position 1 which we spin. Suppose it spins 11 and three quarters pointer point to position 1 which we spin. Suppose it spins 11 and three quartersor 47 quarters. The it is pointing at 47 mod 4 or 3.

47 mod 4 or 3.
1
6
4 K 2 4 K 2
3 3
The Euclidean algorithm

Algorithms which are schemes for computing and we cannot resist putting one in at this point. The Euclidean algorithm for finding the gcd is one of the oldest algorithms known, it appeared in Euclids Elements around 300 BC. It gives a way of finding the greatest common divisor (gcd) of two numbers. That is the largest number which will divide them both.

Our aim is to find a a way of finding the greatest common divisor, gcd (a, b) of two integers a and b.
Suppose a is an integer smaller than b.

1. Then to find the greatest common factor between a and b, divide b by a. If the remainder is zero, then b is a multiple of a and we are done. 2. If not, divide the divisor a by the remainder.

Continue this process, dividing the last divisor by the last remainder, until the remainder is zero. The last non-zero remainder is then the greatest common factor of the integers a and b.
The algorithm is illustrated by the following example. Consider 72 and 246.

We have the following 4 steps:
1. 246= 3 72+ 30 or 246 mod 72= 30
2. 72= 2 30+ 12 or 72 mod 30= 12
3. 30= 2 12+ 6 or 30 mod 12= 6
4. 12= 2 6+ 0

so the gcd is 6.
There are several websites that oer Java applications using this algorithm, we give a Python function

def gcd(a,b):
""" the euclidean algorithm """
if b == 0:

return a
else:
return gcd(b, (a%b))