Bith212 Unit 1 Integers

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.
45=1·30+15.
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
(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).
(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

Bith212 Unit 1 Integers

Uploaded by

Copyright:

Available Formats

Bith212 Unit 1 Integers

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Bith212 Unit 1 Integers

Uploaded by

Copyright:

Available Formats

INTEGERS

 By the end of this unit, you should be able to:

 An integer is a set of numbers Z = {…., -2,-1, 0, 1, 2,….}

 The following theorem describes some of the rules concerning the

Additive Inverse a + (-a) = 0

 Definition: Let a and b be integers. We say a is less or equal to b,

 Theorem 1.1b: The relation ≤ in Z has the following properties:

(i) a ≤ a, for all integers a

 Theorem 1.1c (Law of Trichotomy): For any integer a and b,

 Theorem 1.1d: Suppose a ≤ b and let c be any integers. Then

 Definition: The absolute value for an integer a, written as |a| is defined as

 |5| = 5, |-5| = 5, |0| = 0

 Theorem 1.1e: Let a and b be any integers. Then

(i) |a| ≥ 0 and |a|= 0 iff a = 0

 (ii) |1 -5| – | 2 -9|

 2. Show that for any integers x and y: 2xy ≤ x2+ y2

 Definition: If x is a non-negative integer and y is a positive integer, we define x

 (d) 199 673 mod 2 = 1

 Theorem 1.2a: Suppose a and b are integers. If a mod b = r then

 Theorem 7.2a: Suppose a and b are integers. If a mod b = r then

 1. Find the mod for each pair of integers below

 (c) 100 mod 8 = 4

 (g) 8654 mod 69 = 31

 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

 if a| b and b| a then |a| = |b|

 Let us suppose that c is a common divisor of m and n. Since c| m,

 Theorem 1.3b: Let m, n and c be integers.

 (a) if c is a common divisor of m and n, then

 (b) if c is a common divisor of m and n, then

 Definition 1.3c: The greatest common divisor, written as gcd(m, n)

• The Euclidean algorithm is a way to find the greatest common

 At each step, the remainder, r, decreases by at least 1. Therefore r

 This "greatest common divisor" must exist, since positive integer

 The computations for a=210 and b=45.

 This can be represented as:

 Suppose that a = 1232 and b = 573, and we want to find a solution

 So, x = 20 and y = –43 should be a solution to 1232x + 573y = 1.

 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 (Fundamental Theorem of Arithmetic):

 Every integer n > 1 can be written as a product of primes.

 where mi are positive integers and p1< p2< ….. < pk

 20 = 2.2.5, 120 = 2.2.2.3.5

 A product may consists of a single factor, so a prime number 17 = 17

 So 9 and 25 are relatively prime since gcd(9,25) = 1.

 Cryptography is a technique for establishing secure communications.

 Messages are represented as numbers. For example, each character might be

 RSA method can be summarised as follows:

1. Choose two large primes, p and q (typically more than 100

 To encrypt a message P, compute C = P d(mod n). C is called the cyphertext. To

 To perform the encryption, we need e and n. To perform the decryption, we need d

 Suppose that we choose p = 23, q = 31, d = 29

 Then n = pq = 713 and z = (p-1)(q-1) = 660.

Kolman B and Robert C.Busby(2002). Discrete

You might also like