Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

2.1 NUMBER THEORY

2.1.1 Basic Definitions

Definitions 2.1

1. The set of natural numbers¹ N = {0, 1, 2, 3, …}.
2. 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

1. x = −16, y = 3:

   

2. x = −15, y = 3:

   

Definitions 2.5

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