O'Reilly logo

Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems by Gustavo D. Sutter, Gery J.A. Bioul, Jean-Pierre Deschamps

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

2.1 NUMBER THEORY

2.1.1 Basic Definitions

Definitions 2.1

  1. The set of natural numbers1 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

image

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

image

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

image

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

image

Examples 2.1

  1. x = −16, y = 3:

    image

  2. x = −15, y = 3:

    image

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required