Search Free eBooks

Mathematics for Computer Scientists

     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 math- ematics 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 effort 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.

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.

Integers

We begin by assuming you are familiar with the integers

1,2,3,4,. . .,101,102, . . . , n, . . . , 232582657 − 1, . . .,

sometime called the whole numbers. These are just the numbers we use for count- ing. To these integers we add the zero, 0, defined as

0 + any integer n = 0 + n = n + 0 = n

Once we have the integers and zero mathematicians create negative integers by defining (−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 n−n = 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
          4. (−a) × (−b) = ab
          5. To save space we write ak as a shorthand for a multiplied by itself k times. So 34 = 3 × 3 × 3 × 3 and 210 = 1024. Note an × am = an+m
          6. Do note that n0=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 difficult exercise for large integers, indeed it is so difficult 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, . . . , 2216091 − 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.

Read book online on Google Docs Mathematics for Computer Scientists

No comments:

Post a Comment