MAT 112 Integers and Modern Applications for the Uninitiated

We recall what the integers are and use them as examples when we introduce foundations of mathematical language (Chapter 1). We introduce instructions that we use in the formulation of algorithms throughout the course and apply them in the formulation of algorithms for integers (Chapter 2). As a particularly important algorithm for integers, the division algorithm and applications of its output are given (Chapter 3). These are the tools we need to formulate the Euclidean algorithm for computing greatest common divisors (Chapter 4).

Sets are one of the fundamental structures in mathematics. After introducing basic notation and definitions for working with sets in Chapter 5, we introduce subsets and Cartesian products (Chapter 6). Functions are used in mathematics to assign each element in one set to an element in another set. Often they are used to change the representation of objects. We start with definitions and properties of functions in Chapter 7. We apply functions in the encoding and encryption of texts (Chapter 8).

In Chapter 9 we define the cardinality of sets, talk about the cardinality of infinite sets. We introduce prime numbers and some of their applications (Chapter 10). We show that there are infinitely many prime numbers and present the Twin Prime Conjecture. The Twin Prime Conjecture is a mathematical statement that is believed to be true, but has not been proven yet. In Chapter 11 we discuss different representations of integers and apply those in the encoding of colors, images, and text in Chapter 12.

In the last chapter we introduce a new mathematical structure called a group. Although groups are very simple structures, they have many practical applications, some of which we present at the end of the chapter. We define binary operations, which are a specific kind of function, in Chapter 13. In Chapter 14 we introduce groups that consist of a set and a binary operation that fulfills certain properties. We give further applications of the operation \(\fmod\) from Chapter 3 and show that some finite sets of integers with operations based on addition, multiplication and \(\fmod\) form groups. We generalize exponentiation (introduced in Chapter 1), present an exponentiation algorithm that is more efficient than the algorithm for this purpose from Chapter 2, and demonstrate that, in groups, it is more difficult to compute logarithms (the inverse function of exponentiation) than powers (Chapter 15). In Chapter 16 we present a method for exchanging encryption keys and a public key crypto system whose security is based on the difficulty of computing discrete logarithms in groups. These two systems are widely used in everyday life.