## 2.1 NUMBER THEORY

### 2.1.1 Basic Definitions

**Definitions 2.1**

- The set of natural numbers
^{1} *N* = {0, 1, 2, 3, …}.
- The set of integers
*Z* = {…, −3, −2, −1, 0, 1, 2, 3, … }.

**Definition 2.2** Given two integers *x* and *y*, *y divides x* (*y* is a *divisor* of *x*) if there exists an integer *z* such that *x* = *z.y*.

**Definition 2.3** Given two integers *x* and *y*, with *y* > 0, there exist two integers *q* (the *quotient*) and *r* (the *remainder*) such that

It can be proved that *q* and *r* are unique. Then (notation)

An alternative definition is the following.

**Definition 2.4 (Integer Division)** Given two integers *x* and *y*, with *y* > 0, there exist two integers *q* (the *quotient*) and *r* (the *remainder*) such that

It can be proved that *q* and *r* are unique. Then (notation)

**Examples 2.1**

*x* = −16, *y* = 3:
*x* = −15, *y* = 3:

**Definitions 2.5**

- Given two integers
*x* and *y*, *z* is the *greatest common divisor* of *x* and *y* if
*z* is a natural number (nonnegative ...