INTEGERS
OBJECTIVES
By the end of this unit, you should be able to:
explain the concept of integers and its operations
find the greatest common divisors between two numbers
describe how to use integers in cryptography
BASIC OPERATIONS
An integer is a set of numbers Z = {…., -2,-1, 0, 1, 2,….}
Normally, there are four usual types of operation for integers such
as:
ADDITION AND MULTIPLICATION
The following theorem describes some of the rules concerning the
addition and multiplication of integers:
Theorem 1.1a: For all a, b and c ∈Z
Law Rules
Commutative a + b = b + a and ab = ba
Associative (a + b) + c = a + (b + c)
Distributive a(b + c) = ab + ac
Additive and Multiplicative a + 0 = a and
Identity a.1 = 1.a = a
Additive Inverse a + (-a) = 0
THEOREM 1.1b
Definition: Let a and b be integers. We say a is less or equal to b,
written a ≤ b if the difference b - a is more or equal to zero.
Theorem 1.1b: The relation ≤ in Z has the following properties:
(i) a ≤ a, for all integers a
(ii)if a ≤ b and b ≤ a then a = b
(iii)if a ≤ b and b ≤c then a ≤c
THEOREM 1.1c & 1.1d
Theorem 1.1c (Law of Trichotomy): For any integer a and b,
exactly one of the following holds:
a < b, a = b or a > b.
Theorem 1.1d: Suppose a ≤ b and let c be any integers. Then
(i) a + c ≤ b + c
(ii)ac ≤ bc when c > 0, but bc ≤ ac when c<0
ABSOLUTE VALUE
Definition: The absolute value for an integer a, written as |a| is defined as
|a| = a, if a > 0
OR 0, if a = 0
OR -a, if a < 0
Example:
|5| = 5, |-5| = 5, |0| = 0
THEOREM 1.1e
Theorem 1.1e: Let a and b be any integers. Then
(i) |a| ≥ 0 and |a|= 0 iff a = 0
(ii)– |a| ≤ a ≤ |a|
(iii)|ab| = |a| |b|
(iv)|a + b| ≤ |a| + |b|
Exercise:
1. Evaluate
(i) |-6|
(ii) |1 -5| – | 2 -9|
(iii) |-4| + |3 - 2|
2. Show that for any integers x and y: 2xy ≤ x2+ y2
Mod OPERATION
Definition: If x is a non-negative integer and y is a positive integer, we define x
mod y to be the remainder when x is divided by y.
Example:
(a) 6 mod 2 = 0
(b) 5 mod 1 = 0
(c) 8 mod 12 = 8
(d) 199 673 mod 2 = 1
THEOREM 1.2a
Theorem 1.2a: Suppose a and b are integers. If a mod b = r then
there exists integers q and r such that a = bq + r and 0 ≤ r< |b|.
Theorem 7.2a: Suppose a and b are integers. If a mod b = r then
there exists integers q and r such that a = bq + r and 0 ≤ r< |b|.
EXERCISE
1. Find the mod for each pair of integers below
(b) 100, 45
(f) 4252, 50
2. Determine whether the mod operation below is true or false. If it is false, give
the correct answer.
(a) 18 mod 2 = 0
(c) 100 mod 8 = 4
(g) 8654 mod 69 = 31
Divisor and Greatest Common Divisor
Divisors
Definition 1.3a: Let a and b be integers with a ≠ 0. Suppose ac = b for some integer c. We
then say a divides b or b is divisible by a and written as a|b. We may also say b is multiples
of a and a is a factor or divisor of b.
Example:
The divisors of 10 are 1, 2, 5 and 10.
The characteristic of divisors can be summarised as the following theorem.
Theorem 1.3a: Suppose a, b and c are integers.
(i) if a| b and b| c then a| c
(ii) if a| b, then for any integer q, a| qb
(iii)if a | b and a| c, then a | (b + c) and a| (b -c)
(iv)if a| b and b ≠ 0, then |a| < |b|
if a| b and b| a then |a| = |b|
COMMON DIVISOR
Definition 1.3b: Let m and n be integers where m and n are not both zero. A
common divisor of m and n is an integer that divides both m and n.
Example:
The positive divisors of 30 are 1, 2, 3, 5, 6, 10, 15, 30 and the positive divisor of
105 are 1, 3, 5, 7, 15, 21, 35, 105 thus the positive common divisors of 30 and
105 are 1, 3, 5, 15
Let us suppose that c is a common divisor of m and n. Since c| m,
THEOREM 1.3b
Theorem 1.3b: Let m, n and c be integers.
(a) if c is a common divisor of m and n, then
c| (m + n)
(b) if c is a common divisor of m and n, then
c| (m - n)
(c) if c | m, then c| mn
GREATEST COMMON DIVISOR
Definition 1.3c: The greatest common divisor, written as gcd(m, n)
is the greatest common divisor of m and n.
Example:
The greatest common divisor of 30 and 105, gcd (30, 105) is 15.
EUCLIDEAN ALGORITHM
• The Euclidean algorithm is a way to find the greatest common
divisor of two positive integers, a and b.
Formal description of the Euclidean algorithm
Input Two positive integers, a and b.
Output The greatest common divisor, g, of a and b.
Internal computation
– If a<b, exchange a and b.
– Divide a by b and get the remainder, r. If r=0, report b as the
GCD of a and b.Else
– Replace a by b and replace b by r. Return to the previous step.
GENERAL DESCRIPTION
At each step, the remainder, r, decreases by at least 1. Therefore r
must eventually be 0
In the final stage, when r=0, we see that the "final b" must divide
the final a.
Therefore, the GCD also divides the "final b". So the "final b"
divides both a and b, and is itself a multiple of the GCD
Well, the GCD is the greatest such divisor, and therefore the "final
b" must be equal to the GCD of the initial values
ILLUSTRATIONS
This "greatest common divisor" must exist, since positive integer
divisors of integers can't be any larger than the integers: then gcd
(a,b)=gcd(b,r). Or (a,b) = (b,r1)
For example, gcd(356,96) = gcd(96,68) (because 68 = 356 - 3.96).
Continuing this process of dividing, then continuing with the
remainder and divisor, we have
gcd(356,96) = gcd(96,68) = gcd(68,28) = gcd(28,12) = gcd(12,4) =
gcd(4,0) = 4
ILLUSTRATIONS (Cont)
The computations for a=210 and b=45.
Divide 210 by 45, and get the result 4 with remainder 30, so
210=4·45+30.
Divide 45 by 30, and get the result 1 with remainder 15, so
45=1·30+15.
Divide 30 by 15, and get the result 2 with remainder 0, so
30=2·15+0.
The greatest common divisor of 210 and 45 is 15.
ILLUSTRATIONS (Cont)
This can be represented as:
Gcd(210,45):
(210,45) =4.45+30
(45,30) = 1.30+15
(30,15) = 2.15+0
Remainder is zero(0), therefore gcd(210,45) is 15
APPLICATION
Application - Solving equations of the form ax+by =c:
Diophantine equations
suppose that a = 408, b = 126, and c=6 gcd(408, 126) = 6. Are there
any solutions to the equation: 408x + 126y = 6?
To find a solution, we start by going through the steps of the
Euclidean Algorithm to show that gcd(408, 126) = 6:
Therefore, 408 = 3 ·126 + 30. Remember that gcd(408, 126) =
gcd(126, 30).
Therefore, (126,30) = 4 ·30 + 6.
Therefore, (30,6) = 5 ·6 + 0.
Now, what does this have to do with solutions to
408x + 126y = 6?
APPLICATION (CONT)
Let's take a look at the steps in the Euclidean Algorithm again:
(a) (408,126) = 3 ·126 + 30.
(b) (126,30) = 4 ·30 + 6.
(c) (30,6) = 5 ·6 + 0.
Reorganizing the equation in step (b), we have 6 = 126 – (4 ·30). (1)
From step (a), we see that 30 = 408 – (3 ·126).
Substituting into equation (1), we get
6 = 126 – (4 ·30)
= 126 – 4 ·(408 – 3 ·126)
= -4.408 +(12.126 +1.126)
= (– 4) ·408 + (1 + 12) ·126
= (– 4) ·408 + 13 ·126
Therefore, we see that x = – 4, y = 13 is a solution to 408x + 126y = 6.
APPLICATION (CONT)
Suppose that a = 1232 and b = 573, and we want to find a solution
to 1232x + 573y = d, where d = gcd(1232, 573)
First we compute d using the Euclidean Algorithm:
1. (1232,573) = 2 ·573 + 86.
2. (573,86) = 6 ·86 + 57.
3. (86,57) = 1 ·57 + 29.
4. (57,29) = 1 ·29 + 28.
5. (29,28) = 1 ·28 + 1.
6. (28,1) = 28 ·1 + 0.
APPLICATION (CONT)
We see that d = gcd(1232, 573) = 1, and so we are looking for a solution to1232x
+ 573y = 1.
Now we work our way back up the chain:
1 = 29 – 1 ·28
= 29 – 1 ·(57 – 1 ·29)
= –1 ·57 + 2 · 29
= –1 ·57 + 2 ·(86 – 1 ·57)
= 2 ·86 – 3 ·57
= 2 ·86 – 3 ·(573 – 6 ·86)
= –3 ·573 + 20 ·86
= –3 ·573 + 20 ·(1232 – 2 ·573)
= 20 ·1232 – 43 ·573.
APPLICATION (CONT)
So, x = 20 and y = –43 should be a solution to 1232x + 573y = 1.
Solving the linear equation ax + by = gcd(a, b) is useful in a variety of places in
number theory.
CONCLUSION
The algorithm can be written in pseudo-code as follows
Euclid(a,b) {
while (b not 0)
{ interchange(a,b) b := b mod a }
return(a)}
PRIME NUMBERS
Definition: A positive integer p is called a prime number if its only divisors are 1
and p. If n > 1 is not prime, then n is said to be composite.
Example:
The following numbers are prime numbers: 2, 3, 5, 7, 11, 13 and 17.
The following numbers are composite: 6, 9, 10, 15, 56 and 64
THEOREM 1.4a
Theorem 1.4a (Fundamental Theorem of Arithmetic):
Every integer n > 1 can be written as a product of primes.
This theorem states that any number n > 1 can be expressed uniquely in the form.
where mi are positive integers and p1< p2< ….. < pk
Example:
20 = 2.2.5, 120 = 2.2.2.3.5
A product may consists of a single factor, so a prime number 17 = 17
THEOREM 1.4a (Cont)
Theorem 1.4b: There is no largest prime number, that is, there exists an infinite
number of primes.
Definition 1.4b: Two integers a and b are said to be relatively prime if gcd(a,b) =
1.
Example 1.4c
9 = 3.3
25 = 5.5
So 9 and 25 are relatively prime since gcd(9,25) = 1.
CRYPTOGRAPHY
Cryptography is a technique for establishing secure communications.
The sender transforms the message before transmitting it so that, hopefully, only
authorised recipients can reconstruct the original message.
The sender is said to encrypt the message, and the recipient is said to be decrypt
the message.
If the encryption is done properly, unauthorised people will not be able to
understand the message.
PRIVATE KEY EXAMPLE 1.5A
If a key is defined as
Character: F P S
A B C D E G H I J K L M N O Q R T U V W X Y Z
Replaced P
by: E I J F U A X V H W G S R K O B T Q Y D M L Z N C
The S E N D M O R E M O N E Y
message:
Would be Q A R U S K T A S K R A N
encrypted
as:
By using the same key, the receiver will be able to decrypt the message.
PUBLIC KEY (RSA) ENCRYPTION TECHNIQUE
RSA is the initials of its inventors, Ronald L. Rivest, Adi Shamir, Leonard M.
Adleman. In the RSA system, each participant makes public an encryption key
and hides a decryption key.
To send a message, all one needs to do is look up the recipient’s encryption key in
a publicly distributed table. The recipient then decrypts the message using the
hidden decryption key.
Messages are represented as numbers. For example, each character might be
represented as numbers. If a blank space is represented as 1, A as 2, B as 3, and so
on, the message SEND MONEY would be represented as 20, 6, 15, 5, 1, 14, 16,
15, 6, 26. If desired, the integers could be combined into the single integer.
20061505011416150626
PUBLIC KEY (RSA) ENCRYPTION TECHNIQUE
(Cont)
RSA method can be summarised as follows:
1. Choose two large primes, p and q (typically more than 100
2. Compute n = pq and z = (p-1)(q-1)
3. Choose a number relatively prime to z and call it d.
4. Find e such that ed mod z = 1
To encrypt a message P, compute C = P d(mod n). C is called the cyphertext. To
decrypt a cyphertext C, compute P = Ce(mod n).
To perform the encryption, we need e and n. To perform the decryption, we need d
and n. Therefore, the public key consist of the pair (e,n) and the private key consists
of (d,n).
PUBLIC KEY (RSA) ENCRYPTION TECHNIQUE
(Cont)
Example:
Suppose that we choose p = 23, q = 31, d = 29
Then n = pq = 713 and z = (p-1)(q-1) = 660.
Exercise:
1. Now, e = 569 since e (29) mod 660 = 1 . The pair (e , n ) = ( 569, 713 ) is
made publicly available. The private key is (d,n) = (29,713). Encrypt the
message WEAREALIVE using the key as shown in Example
1.5a.
2. Decrypt the message UTWR ENKDTEKMIGYWRA using the
key as shown in Example 1.5a.
3. Decrypt 411 using e = 569 as in Example 1.5b.
REFERENCE
Kolman B and Robert C.Busby(2002). Discrete
Mathematical Structures For Computer Science
M A Lerma (2005).Discrete Mathematics
W W L Chen (2008). Discrete Mathematics
http://encyclopedia.thefreedictionary.com/Integer accessed
16.10.2016
