Set of Integers

The set of integers, denoted by $Z$, contains all integral numbers (with no fraction) from negative infinity to positive infinity. The set of integers $$ \mathbf{Z}={\ldots,-2,-1,0,1,2, \ldots} $$

Binary Operations

In cryptography, we are interested in three binary operations applied to the set of integers. A binary operation takes two inputs and creates one output. Figure $2.2$ Three binary operations for the set of integersThe following shows the results of the three binary operations on two integers. Because each input can be either positive or negative, we can have four cases for each operation.

$\begin{array}{lllll}\text { Add: } & 5+9=14 & (-5)+9=4 & 5+(-9)=-4 & (-5)+(-9)=-14 \\ \text { Subtract: } & 5-9=-4 & (-5)-9=-14 & 5-(-9)=14 & (-5)-(-9)=+4 \\ \text { Multiply: } & 5 \times 9=45 & (-5) \times 9=-45 & 5 \times(-9)=-45 & (-5) \times(-9)=45\end{array}$

Integer Division

In integer arithmetic, if we divide a by $n$, we can get $q$ And $r$. The relationship between these four integers can be shown as $a=q \times n+r

Example

Assume that $a=255$ and $n=11$. We can find $q=23$ and $R=2$ using the division algorithm.

Divisbility

If $a$ is not zero and we let $r=0$ in the division relation, we get $a=q \times n$ If the remainder is zero, $a \mid n$ If the remainder is not zero, $a \nmid n$a. The integer 4 divides the integer 32 because $32=8 \times 4$. We show this as 4132 b. The number 8 does not divide the number 42 because $42=5 \times 8+2$. There is a remainder, the number 2 , in the equation. We show this as $8 \times 42$ $$ \begin{array}{l} \text { Property 1: if } a \mid 1, \text { then } a=\pm 1 . \ \text { Property 2: if } a \mid b \text { and } b \mid a \text {, then } a=\pm b . \ \text { Property 3: if } a \mid b \text { and } b \mid c \text {, then } a \mid c . \ \text { Property 4: if } a \mid b \text { and } a \mid c, \text { then } \ a \mid(m \times b+n \times c), \text { where } m \ a \text { and } n \text { are arbitrary integers } \end{array} $$

Note Fact 1: The integer 1 has only one divisor, itself. Fact 2: Any positive integer has at least two divisors, 1 and itself (but it can have more).

$$ \begin{array}{l} \text { Note } \text { Greatest Common Divisor } \\ \hline \begin{array}{l} \text { The greatest common divisor of two } \\ \text { positive integers is the largest integer } \\ \text { that can divide both integers. } \end{array} \\ \begin{array}{|l|} \hline \text { Note } & \text { Euclidean Algorithm } \\ \hline \hline \text { Fact 1: gcd }(a, 0)=a & \\ \text { Fact 2: gcd }(a, b)=g c d(b, r), \text { where } r \text { is } \\ & \text { the remainder of dividing a by } b \\ \hline \end{array} \end{array} $$