Scribd
Upload
11 views

Data Structure Lect11

Uploaded by

Hasnain Nisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views

Data Structure Lect11

Uploaded by

Hasnain Nisar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 13

Discrete Structure

Lecture 11
Topics
 Conversion between Binary Octal and Hexadecimal

 Decimal Expansion of Binary, Octal and Hexadecimal

 Principal of Mathematical Induction

 Fundamental Theorem of Arithmetic

 Fermat’s Little Theorem


Convert to Binary Number
Find the binary expansion of (241)10. Solution:
First divide 241 by 2 to obtain
241 = 2 · 120 + 1.
Successively dividing quotients by 2 gives
120 = 2 · 60 + 0,
60 = 2 · 30 + 0,
30 = 2 · 15 + 0,
15 = 2 · 7 + 1,
7 = 2 · 3 + 1,
3 = 2 · 1 + 1,
1=2·0+1
The successive remainders that we have found, 1, 0, 0, 0, 1, 1, 1, 1, are the digits
from the right to the left in the binary (base 2) expansion of (241) 10.
(241) 10 = (1111 0001) 2
Octal Conversion
Find the octal expansion of (12345) 10.
Solution: First, divide 12345 by 8 to obtain
12345 = 8 · 1543 + 1.
Successively dividing quotients by 8 gives
1543 = 8 · 192 + 7,
192 = 8 · 24 + 0,
24 = 8 · 3 + 0,
3 = 8 · 0 + 3.
The successive remainders that we have found, 1, 7, 0, 0, and 3, are the digits
from the right to the left of 12345 in base 8.
(12345) 10 = (30071) 8
Hexadecimal Conversion
Find the hexadecimal expansion of (177130)10.
Solution: First divide 177130 by 16 to obtain
177130 = 16 · 11070 + 10.
Successively dividing quotients by 16 gives
11070 = 16 · 691 + 14,
691 = 16 · 43 + 3,
43 = 16 · 2 + 11,
2 = 16 · 0 + 2.
The successive remainders that we have found, 10, 14, 3, 11, 2, give us the digits from the
right to the left of 177130 in the hexadecimal (base 16) expansion of (177130)10.
(177130)10 = (2B3EA)16.
Decimal Expansion of Base 16
What is the decimal expansion of the number with hexadecimal expansion
(2AE0B)16?
Solution: Using the definition of a base b expansion with b = 16 tells us that
(2AE0B) 16 = 2 · 164 + 10 · 163 + 14 · 162 + 0 · 161 + 11 = 175627.

Each hexadecimal digit can be represented using four bits.


For instance, we see that (1110 0101)2 = (E5)16 because (1110)2 = (E)16 and
(0101)2 = (5)16.
Bytes, which are bit strings of length eight, can be represented by two
hexadecimal digits.
Decimal Expansion of the Octal Number

What is the decimal expansion of the number with octal expansion (7016)8?

Solution:
Using the definition of a base b expansion with b = 8 tells us that
(7016)8 = 7 · 83 + 0 · 82 + 1 · 81 + 6 .80
= 3598.
Decimal Expansion of Binary Number
What is the decimal expansion of the integer that has (1 0101 1111) 2 as its binary
expansion?

Solution:

(10101 1111)2= 1 · 28 + 0 · 27 + 1 · 26 + 0 · 25 + 1 · 24 + 1 · 23 + 1 · 22 + 1 · 21 + 1 · 20
= 351.
Octal and Hexadecimal Expansion to Binary
OCTAL to Binary
To convert (765)8 into binary notation, we replace each octal digit by a block of three
binary digits.
7 = 111, 6 = 110, 5 = 101
These blocks are 111, 110, and 101.
Hence, (765) 8 = (1 1111 0101) 2.

Hexadecimal to Binary
To convert (A8D) 16 into binary notation, we replace each hexadecimal digit by a block
of four binary digits.
A = 10 =1010, 8 = 1000, D = 13 = 1101
These blocks are 1010, 1000, and 1101.
Hence, (A8D) 16 = (1010 1000 1101) 2
ALGORITHM 1 Constructing Base b Expansions

procedure base b expansion(n, b: positive integers with b > 1)


q := n
k := 0
while q ≠ 0
ak := q mod b
q := q div b
k := k + 1
return (ak−1, ...,a1,a0) {(ak−1 ...a1a0) b is the base b expansion of n }
THE FUNDAMENTAL THEOREM OF ARITHMETIC

Every integer greater than 1 can be written uniquely as a prime or as the product
of two or more primes where the prime factors are written in order of
nondecreasing size.

Example:
The prime factorizations of 100, 641, 999, and 1024 are given by
100 = 2 · 2 · 5 · 5 = 22 52,
641 = 641,
999 = 3 · 3 · 3 · 37 = 33 · 37,
1024 = 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 = 210.
Fermat’s Little Theorem
If p is prime and a is an integer not divisible by p,
then ap-1 ≡ 1 (mod p).
Furthermore, for every integer a we have
ap ≡ a (mod p)

Example: Find 7222 mod 11


We can use Fermat’s little theorem to evaluate 7222 mod 11 rather than using the fast
modular exponentiation algorithm.
By Fermat’s little theorem we know that 710 ≡ 1 (mod 11),
so (710) k ≡ 1 (mod 11) for every positive integer k. To take advantage of this last
congruence, we divide the exponent 222 by 10, finding that 222 = 22 · 10 + 2.
We now see that 7222 = 722.10+2 = (710) 22 72 ≡ (1) 22 · 49 ≡ 5 (mod 11).
It follows that 7222 mod 11 = 5.
Questions

Use Fermat’s little theorem to find 7121 mod 13.

Use Fermat’s little theorem to find 231002 mod 41.

Use Fermat’s little theorem to compute 3302 mod 5, 3302 mod 7, and 3302 mod 11.

You might also like