Number Theory concepts to undertsnd cryptography
nitinsaxena777
5 views
37 slides
Sep 16, 2025
Slide 1 of 37
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
About This Presentation
Number Theory concepts to understand cryptography
Slide Content
Fall 2002 CMSC 203 - Discrete Structures 1
Let us get into…Let us get into…
Number TheoryNumber Theory
Let us get into…Let us get into…
Number TheoryNumber Theory
Fall 2002 CMSC 203 - Discrete Structures 2
Introduction to Number TheoryIntroduction to Number Theory
Number theory is about Number theory is about integersintegers and their and their
properties.properties.
We will start with the basic principles ofWe will start with the basic principles of
• divisibility,divisibility,
• greatest common divisors,greatest common divisors,
• least common multiples, andleast common multiples, and
• modular arithmeticmodular arithmetic
and look at some relevant algorithms. and look at some relevant algorithms.
Introduction to Number TheoryIntroduction to Number Theory
Number theory is about Number theory is about integersintegers and their and their
properties.properties.
We will start with the basic principles ofWe will start with the basic principles of
• divisibility,divisibility,
• greatest common divisors,greatest common divisors,
• least common multiples, andleast common multiples, and
• modular arithmeticmodular arithmetic
and look at some relevant algorithms. and look at some relevant algorithms.
Fall 2002 CMSC 203 - Discrete Structures 3
DivisionDivision
If a and b are integers with a If a and b are integers with a 0, we say that 0, we say that
a a dividesdivides b if there is an integer c so that b = ac. b if there is an integer c so that b = ac.
When a divides b we say that a is a When a divides b we say that a is a factorfactor of b of b
and that b is a and that b is a multiplemultiple of a. of a.
The notation The notation a | ba | b means that a divides b. means that a divides b.
We write We write a X ba X b when a does not divide b when a does not divide b
(see book for correct symbol).(see book for correct symbol).
DivisionDivision
If a and b are integers with a If a and b are integers with a 0, we say that 0, we say that
a a dividesdivides b if there is an integer c so that b = ac. b if there is an integer c so that b = ac.
When a divides b we say that a is a When a divides b we say that a is a factorfactor of b of b
and that b is a and that b is a multiplemultiple of a. of a.
The notation The notation a | ba | b means that a divides b. means that a divides b.
We write We write a X ba X b when a does not divide b when a does not divide b
(see book for correct symbol).(see book for correct symbol).
Fall 2002 CMSC 203 - Discrete Structures 4
Divisibility TheoremsDivisibility Theorems
For integers a, b, and c it is true thatFor integers a, b, and c it is true that
• if a | b and a | c, then a | (b + c)if a | b and a | c, then a | (b + c)
Example:Example: 3 | 6 and 3 | 9, so 3 | 15. 3 | 6 and 3 | 9, so 3 | 15.
• if a | b, then a | bc for all integers cif a | b, then a | bc for all integers c
Example:Example: 5 | 10, so 5 | 20, 5 | 30, 5 | 40, … 5 | 10, so 5 | 20, 5 | 30, 5 | 40, …
• if a | b and b | c, then a | cif a | b and b | c, then a | c
Example:Example: 4 | 8 and 8 | 24, so 4 | 24. 4 | 8 and 8 | 24, so 4 | 24.
Divisibility TheoremsDivisibility Theorems
For integers a, b, and c it is true thatFor integers a, b, and c it is true that
• if a | b and a | c, then a | (b + c)if a | b and a | c, then a | (b + c)
Example:Example: 3 | 6 and 3 | 9, so 3 | 15. 3 | 6 and 3 | 9, so 3 | 15.
• if a | b, then a | bc for all integers cif a | b, then a | bc for all integers c
Example:Example: 5 | 10, so 5 | 20, 5 | 30, 5 | 40, … 5 | 10, so 5 | 20, 5 | 30, 5 | 40, …
• if a | b and b | c, then a | cif a | b and b | c, then a | c
Example:Example: 4 | 8 and 8 | 24, so 4 | 24. 4 | 8 and 8 | 24, so 4 | 24.
Fall 2002 CMSC 203 - Discrete Structures 5
PrimesPrimes
A positive integer p greater than 1 is called prime A positive integer p greater than 1 is called prime
if the only positive factors of p are 1 and p.if the only positive factors of p are 1 and p.
A positive integer that is greater than 1 and is not A positive integer that is greater than 1 and is not
prime is called composite.prime is called composite.
The fundamental theorem of arithmetic:The fundamental theorem of arithmetic:
Every positive integer can be written Every positive integer can be written uniquelyuniquely as as
the the product of primesproduct of primes, where the prime factors , where the prime factors
are written in order of increasing size.are written in order of increasing size.
PrimesPrimes
A positive integer p greater than 1 is called prime A positive integer p greater than 1 is called prime
if the only positive factors of p are 1 and p.if the only positive factors of p are 1 and p.
A positive integer that is greater than 1 and is not A positive integer that is greater than 1 and is not
prime is called composite.prime is called composite.
The fundamental theorem of arithmetic:The fundamental theorem of arithmetic:
Every positive integer can be written Every positive integer can be written uniquelyuniquely as as
the the product of primesproduct of primes, where the prime factors , where the prime factors
are written in order of increasing size.are written in order of increasing size.
Fall 2002 CMSC 203 - Discrete Structures 6
PrimesPrimes
Examples:Examples:
3·53·5
48 =48 =
17 =17 =
100 =100 =
512 =512 =
515 =515 =
28 =28 =
15 =15 =
2·2·2·2·3 = 22·2·2·2·3 = 2
44
·3·3
1717
2·2·5·5 = 22·2·5·5 = 2
22
·5·5
22
2·2·2·2·2·2·2·2·2 = 22·2·2·2·2·2·2·2·2 = 2
99
5·1035·103
2·2·72·2·7
PrimesPrimes
Examples:Examples:
3·53·5
48 =48 =
17 =17 =
100 =100 =
512 =512 =
515 =515 =
28 =28 =
15 =15 =
2·2·2·2·3 = 22·2·2·2·3 = 2
44
·3·3
1717
2·2·5·5 = 22·2·5·5 = 2
22
·5·5
22
2·2·2·2·2·2·2·2·2 = 22·2·2·2·2·2·2·2·2 = 2
99
5·1035·103
2·2·72·2·7
Fall 2002 CMSC 203 - Discrete Structures 7
PrimesPrimes
If n is a composite integer, then n has a prime If n is a composite integer, then n has a prime
divisor less than or equal .divisor less than or equal .
This is easy to see: if n is a composite integer, it This is easy to see: if n is a composite integer, it
must have two prime divisors pmust have two prime divisors p
11 and p and p
22 such that such that
pp
11pp
22 = n. = n.
pp
11 and p and p
22 cannot both be greater than cannot both be greater than
, because then p, because then p
11pp
22 > n. > n.
n
n
PrimesPrimes
If n is a composite integer, then n has a prime If n is a composite integer, then n has a prime
divisor less than or equal .divisor less than or equal .
This is easy to see: if n is a composite integer, it This is easy to see: if n is a composite integer, it
must have two prime divisors pmust have two prime divisors p
11 and p and p
22 such that such that
pp
11pp
22 = n. = n.
pp
11 and p and p
22 cannot both be greater than cannot both be greater than
, because then p, because then p
11pp
22 > n. > n.
n
n
Fall 2002 CMSC 203 - Discrete Structures 8
The Division AlgorithmThe Division Algorithm
Let Let aa be an integer and be an integer and dd a positive integer. a positive integer.
Then there are unique integers Then there are unique integers qq and and rr, with , with
0 0 r < d r < d, such that , such that a = dq + ra = dq + r..
In the above equation, In the above equation,
• dd is called the divisor, is called the divisor,
• aa is called the dividend, is called the dividend,
• qq is called the quotient, and is called the quotient, and
• rr is called the remainder. is called the remainder.
The Division AlgorithmThe Division Algorithm
Let Let aa be an integer and be an integer and dd a positive integer. a positive integer.
Then there are unique integers Then there are unique integers qq and and rr, with , with
0 0 r < d r < d, such that , such that a = dq + ra = dq + r..
In the above equation, In the above equation,
• dd is called the divisor, is called the divisor,
• aa is called the dividend, is called the dividend,
• qq is called the quotient, and is called the quotient, and
• rr is called the remainder. is called the remainder.
Fall 2002 CMSC 203 - Discrete Structures 9
The Division AlgorithmThe Division Algorithm
Example:Example:
When we divide 17 by 5, we haveWhen we divide 17 by 5, we have
17 = 517 = 53 + 2.3 + 2.
• 17 is the dividend,17 is the dividend,
• 5 is the divisor,5 is the divisor,
• 3 is called the quotient, and3 is called the quotient, and
• 2 is called the remainder.2 is called the remainder.
The Division AlgorithmThe Division Algorithm
Example:Example:
When we divide 17 by 5, we haveWhen we divide 17 by 5, we have
17 = 517 = 53 + 2.3 + 2.
• 17 is the dividend,17 is the dividend,
• 5 is the divisor,5 is the divisor,
• 3 is called the quotient, and3 is called the quotient, and
• 2 is called the remainder.2 is called the remainder.
Fall 2002 CMSC 203 - Discrete Structures 10
The Division AlgorithmThe Division Algorithm
Another example:Another example:
What happens when we divide -11 by 3 ?What happens when we divide -11 by 3 ?
Note that the remainder cannot be negative.Note that the remainder cannot be negative.
-11 = 3-11 = 3(-4) + 1.(-4) + 1.
• -11 is the dividend,-11 is the dividend,
• 3 is the divisor,3 is the divisor,
• -4 is called the quotient, and-4 is called the quotient, and
• 1 is called the remainder.1 is called the remainder.
The Division AlgorithmThe Division Algorithm
Another example:Another example:
What happens when we divide -11 by 3 ?What happens when we divide -11 by 3 ?
Note that the remainder cannot be negative.Note that the remainder cannot be negative.
-11 = 3-11 = 3(-4) + 1.(-4) + 1.
• -11 is the dividend,-11 is the dividend,
• 3 is the divisor,3 is the divisor,
• -4 is called the quotient, and-4 is called the quotient, and
• 1 is called the remainder.1 is called the remainder.
Fall 2002 CMSC 203 - Discrete Structures 11
Greatest Common DivisorsGreatest Common Divisors
Let a and b be integers, not both zero.Let a and b be integers, not both zero.
The largest integer d such that d | a and d | b is The largest integer d such that d | a and d | b is
called the called the greatest common divisorgreatest common divisor of a and b. of a and b.
The greatest common divisor of a and b is denoted The greatest common divisor of a and b is denoted
by gcd(a, b).by gcd(a, b).
Example 1:Example 1: What is gcd(48, 72) ? What is gcd(48, 72) ?
The positive common divisors of 48 and 72 are The positive common divisors of 48 and 72 are
1, 2, 3, 4, 6, 8, 12, 16, and 24, so gcd(48, 72) = 24. 1, 2, 3, 4, 6, 8, 12, 16, and 24, so gcd(48, 72) = 24.
Example 2:Example 2: What is gcd(19, 72) ? What is gcd(19, 72) ?
The only positive common divisor of 19 and 72 isThe only positive common divisor of 19 and 72 is
1, so gcd(19, 72) = 1. 1, so gcd(19, 72) = 1.
Greatest Common DivisorsGreatest Common Divisors
Let a and b be integers, not both zero.Let a and b be integers, not both zero.
The largest integer d such that d | a and d | b is The largest integer d such that d | a and d | b is
called the called the greatest common divisorgreatest common divisor of a and b. of a and b.
The greatest common divisor of a and b is denoted The greatest common divisor of a and b is denoted
by gcd(a, b).by gcd(a, b).
Example 1:Example 1: What is gcd(48, 72) ? What is gcd(48, 72) ?
The positive common divisors of 48 and 72 are The positive common divisors of 48 and 72 are
1, 2, 3, 4, 6, 8, 12, 16, and 24, so gcd(48, 72) = 24. 1, 2, 3, 4, 6, 8, 12, 16, and 24, so gcd(48, 72) = 24.
Example 2:Example 2: What is gcd(19, 72) ? What is gcd(19, 72) ?
The only positive common divisor of 19 and 72 isThe only positive common divisor of 19 and 72 is
1, so gcd(19, 72) = 1. 1, so gcd(19, 72) = 1.
Fall 2002 CMSC 203 - Discrete Structures 12
Greatest Common DivisorsGreatest Common Divisors
Using prime factorizations:Using prime factorizations:
a = pa = p
11
aa
1 1 p p
22
aa
2 2 … p… p
nn
aa
n n , b = p, b = p
11
bb
1 1 p p
22
bb
2 2 … p… p
nn
bb
n n ,,
where pwhere p
11 < p < p
22 < … < p < … < p
nn and a and a
ii, b, b
ii NN for 1 for 1 i i n n
gcd(a, b) = pgcd(a, b) = p
11
min(amin(a
11
, b, b
1 1
))
p p
22
min(amin(a
22
, b, b
2 2
))
… p… p
nn
min(amin(a
nn
, b, b
n n
))
Example:Example:
a = 60 = a = 60 = 22
22
3 3
11
5 5
11
b = 54 = b = 54 = 22
11
3 3
33
5 5
00
gcd(a, b) = gcd(a, b) = 22
11
3 3
11
5 5
0 0
= 6 = 6
Greatest Common DivisorsGreatest Common Divisors
Using prime factorizations:Using prime factorizations:
a = pa = p
11
aa
1 1 p p
22
aa
2 2 … p… p
nn
aa
n n , b = p, b = p
11
bb
1 1 p p
22
bb
2 2 … p… p
nn
bb
n n ,,
where pwhere p
11 < p < p
22 < … < p < … < p
nn and a and a
ii, b, b
ii NN for 1 for 1 i i n n
gcd(a, b) = pgcd(a, b) = p
11
min(amin(a
11
, b, b
1 1
))
p p
22
min(amin(a
22
, b, b
2 2
))
… p… p
nn
min(amin(a
nn
, b, b
n n
))
Example:Example:
a = 60 = a = 60 = 22
22
3 3
11
5 5
11
b = 54 = b = 54 = 22
11
3 3
33
5 5
00
gcd(a, b) = gcd(a, b) = 22
11
3 3
11
5 5
0 0
= 6 = 6
Fall 2002 CMSC 203 - Discrete Structures 13
Relatively Prime IntegersRelatively Prime Integers
Definition:Definition:
Two integers a and b are Two integers a and b are relatively primerelatively prime if if
gcd(a, b) = 1.gcd(a, b) = 1.
Examples:Examples:
Are 15 and 28 relatively prime?Are 15 and 28 relatively prime?
Yes, gcd(15, 28) = 1.Yes, gcd(15, 28) = 1.
Are 55 and 28 relatively prime?Are 55 and 28 relatively prime?
Yes, gcd(55, 28) = 1.Yes, gcd(55, 28) = 1.
Are 35 and 28 relatively prime?Are 35 and 28 relatively prime?
No, gcd(35, 28) = 7.No, gcd(35, 28) = 7.
Relatively Prime IntegersRelatively Prime Integers
Definition:Definition:
Two integers a and b are Two integers a and b are relatively primerelatively prime if if
gcd(a, b) = 1.gcd(a, b) = 1.
Examples:Examples:
Are 15 and 28 relatively prime?Are 15 and 28 relatively prime?
Yes, gcd(15, 28) = 1.Yes, gcd(15, 28) = 1.
Are 55 and 28 relatively prime?Are 55 and 28 relatively prime?
Yes, gcd(55, 28) = 1.Yes, gcd(55, 28) = 1.
Are 35 and 28 relatively prime?Are 35 and 28 relatively prime?
No, gcd(35, 28) = 7.No, gcd(35, 28) = 7.
Fall 2002 CMSC 203 - Discrete Structures 14
Relatively Prime IntegersRelatively Prime Integers
Definition:Definition:
The integers aThe integers a
11, a, a
22, …, a, …, a
nn are are pairwise relatively pairwise relatively
primeprime if gcd(a if gcd(a
ii, a, a
jj) = 1 whenever 1 ) = 1 whenever 1 i < j i < j n. n.
Examples:Examples:
Are 15, 17, and 27 pairwise relatively prime?Are 15, 17, and 27 pairwise relatively prime?
No, because gcd(15, 27) = 3.No, because gcd(15, 27) = 3.
Are 15, 17, and 28 pairwise relatively prime?Are 15, 17, and 28 pairwise relatively prime?
Yes, because gcd(15, 17) = 1, gcd(15, 28) = 1 and Yes, because gcd(15, 17) = 1, gcd(15, 28) = 1 and
gcd(17, 28) = 1.gcd(17, 28) = 1.
Relatively Prime IntegersRelatively Prime Integers
Definition:Definition:
The integers aThe integers a
11, a, a
22, …, a, …, a
nn are are pairwise relatively pairwise relatively
primeprime if gcd(a if gcd(a
ii, a, a
jj) = 1 whenever 1 ) = 1 whenever 1 i < j i < j n. n.
Examples:Examples:
Are 15, 17, and 27 pairwise relatively prime?Are 15, 17, and 27 pairwise relatively prime?
No, because gcd(15, 27) = 3.No, because gcd(15, 27) = 3.
Are 15, 17, and 28 pairwise relatively prime?Are 15, 17, and 28 pairwise relatively prime?
Yes, because gcd(15, 17) = 1, gcd(15, 28) = 1 and Yes, because gcd(15, 17) = 1, gcd(15, 28) = 1 and
gcd(17, 28) = 1.gcd(17, 28) = 1.
Fall 2002 CMSC 203 - Discrete Structures 15
Least Common MultiplesLeast Common Multiples
Definition:Definition:
The The least common multipleleast common multiple of the positive of the positive
integers a and b is the smallest positive integer integers a and b is the smallest positive integer
that is divisible by both a and b.that is divisible by both a and b.
We denote the least common multiple of a and b We denote the least common multiple of a and b
by lcm(a, b).by lcm(a, b).
Examples:Examples:
lcm(3, 7) =lcm(3, 7) =2121
lcm(4, 6) =lcm(4, 6) =1212
lcm(5, 10) =lcm(5, 10) =1010
Least Common MultiplesLeast Common Multiples
Definition:Definition:
The The least common multipleleast common multiple of the positive of the positive
integers a and b is the smallest positive integer integers a and b is the smallest positive integer
that is divisible by both a and b.that is divisible by both a and b.
We denote the least common multiple of a and b We denote the least common multiple of a and b
by lcm(a, b).by lcm(a, b).
Examples:Examples:
lcm(3, 7) =lcm(3, 7) =2121
lcm(4, 6) =lcm(4, 6) =1212
lcm(5, 10) =lcm(5, 10) =1010
Fall 2002 CMSC 203 - Discrete Structures 16
Least Common MultiplesLeast Common Multiples
Using prime factorizations:Using prime factorizations:
a = pa = p
11
aa
1 1 p p
22
aa
2 2 … p… p
nn
aa
n n , b = p, b = p
11
bb
1 1 p p
22
bb
2 2 … p… p
nn
bb
n n ,,
where pwhere p
11 < p < p
22 < … < p < … < p
nn and a and a
ii, b, b
ii NN for 1 for 1 i i n n
lcm(a, b) = plcm(a, b) = p
11
max(amax(a
11
, b, b
1 1
))
p p
22
max(amax(a
22
, b, b
2 2
))
… p… p
nn
max(amax(a
nn
, b, b
n n
))
Example:Example:
a = 60 = a = 60 = 22
22
3 3
11
5 5
11
b = 54 = b = 54 = 22
11
3 3
33
5 5
00
lcm(a, b) = lcm(a, b) = 22
22
3 3
33
5 5
1 1
= 4 = 427275 = 5405 = 540
Least Common MultiplesLeast Common Multiples
Using prime factorizations:Using prime factorizations:
a = pa = p
11
aa
1 1 p p
22
aa
2 2 … p… p
nn
aa
n n , b = p, b = p
11
bb
1 1 p p
22
bb
2 2 … p… p
nn
bb
n n ,,
where pwhere p
11 < p < p
22 < … < p < … < p
nn and a and a
ii, b, b
ii NN for 1 for 1 i i n n
lcm(a, b) = plcm(a, b) = p
11
max(amax(a
11
, b, b
1 1
))
p p
22
max(amax(a
22
, b, b
2 2
))
… p… p
nn
max(amax(a
nn
, b, b
n n
))
Example:Example:
a = 60 = a = 60 = 22
22
3 3
11
5 5
11
b = 54 = b = 54 = 22
11
3 3
33
5 5
00
lcm(a, b) = lcm(a, b) = 22
22
3 3
33
5 5
1 1
= 4 = 427275 = 5405 = 540
Fall 2002 CMSC 203 - Discrete Structures 17
GCD and LCMGCD and LCM
a = 60 = a = 60 = 22
22
3 3
11
5 5
11
b = 54 = b = 54 = 22
11
3 3
33
5 5
00
lcm(a, b) = lcm(a, b) = 22
22
3 3
33
5 5
1 1
= 540 = 540
gcd(a, b) = gcd(a, b) = 22
11
3 3
11
5 5
0 0
= 6 = 6
Theorem: aTheorem: ab =b =gcd(a,b)gcd(a,b)lcm(a,b)lcm(a,b)
GCD and LCMGCD and LCM
a = 60 = a = 60 = 22
22
3 3
11
5 5
11
b = 54 = b = 54 = 22
11
3 3
33
5 5
00
lcm(a, b) = lcm(a, b) = 22
22
3 3
33
5 5
1 1
= 540 = 540
gcd(a, b) = gcd(a, b) = 22
11
3 3
11
5 5
0 0
= 6 = 6
Theorem: aTheorem: ab =b =gcd(a,b)gcd(a,b)lcm(a,b)lcm(a,b)
Fall 2002 CMSC 203 - Discrete Structures 18
Modular ArithmeticModular Arithmetic
Let a be an integer and m be a positive integer.Let a be an integer and m be a positive integer.
We denote by We denote by a mod ma mod m the remainder when a is the remainder when a is
divided by m.divided by m.
Examples:Examples:
9 mod 4 =9 mod 4 =11
9 mod 3 =9 mod 3 =00
9 mod 10 =9 mod 10 =99
-13 mod 4 =-13 mod 4 =33
Modular ArithmeticModular Arithmetic
Let a be an integer and m be a positive integer.Let a be an integer and m be a positive integer.
We denote by We denote by a mod ma mod m the remainder when a is the remainder when a is
divided by m.divided by m.
Examples:Examples:
9 mod 4 =9 mod 4 =11
9 mod 3 =9 mod 3 =00
9 mod 10 =9 mod 10 =99
-13 mod 4 =-13 mod 4 =33
Fall 2002 CMSC 203 - Discrete Structures 19
CongruencesCongruences
Let a and b be integers and m be a positive integer. Let a and b be integers and m be a positive integer.
We say that We say that a is congruent to b modulo ma is congruent to b modulo m if if
m divides a – b.m divides a – b.
We use the notation We use the notation a a b (mod m) b (mod m) to indicate to indicate
that a is congruent to b modulo m.that a is congruent to b modulo m.
In other words:In other words:
a a b (mod m) if and only if b (mod m) if and only if a mod m = b mod ma mod m = b mod m. .
CongruencesCongruences
Let a and b be integers and m be a positive integer. Let a and b be integers and m be a positive integer.
We say that We say that a is congruent to b modulo ma is congruent to b modulo m if if
m divides a – b.m divides a – b.
We use the notation We use the notation a a b (mod m) b (mod m) to indicate to indicate
that a is congruent to b modulo m.that a is congruent to b modulo m.
In other words:In other words:
a a b (mod m) if and only if b (mod m) if and only if a mod m = b mod ma mod m = b mod m. .
Fall 2002 CMSC 203 - Discrete Structures 20
CongruencesCongruences
Examples:Examples:
Is it true that 46 Is it true that 46 68 (mod 11) ? 68 (mod 11) ?
Yes, because 11 | (46 – 68).Yes, because 11 | (46 – 68).
Is it true that 46 Is it true that 46 68 (mod 22)? 68 (mod 22)?
Yes, because 22 | (46 – 68).Yes, because 22 | (46 – 68).
For which integers z is it true that z For which integers z is it true that z 12 (mod 10)? 12 (mod 10)?
It is true for any zIt is true for any z{…,-28, -18, -8, 2, 12, 22, 32, …}{…,-28, -18, -8, 2, 12, 22, 32, …}
Theorem:Theorem: Let m be a positive integer. The integers Let m be a positive integer. The integers
a and b are congruent modulo m if and only if there a and b are congruent modulo m if and only if there
is an integer k such that a = b + km.is an integer k such that a = b + km.
CongruencesCongruences
Examples:Examples:
Is it true that 46 Is it true that 46 68 (mod 11) ? 68 (mod 11) ?
Yes, because 11 | (46 – 68).Yes, because 11 | (46 – 68).
Is it true that 46 Is it true that 46 68 (mod 22)? 68 (mod 22)?
Yes, because 22 | (46 – 68).Yes, because 22 | (46 – 68).
For which integers z is it true that z For which integers z is it true that z 12 (mod 10)? 12 (mod 10)?
It is true for any zIt is true for any z{…,-28, -18, -8, 2, 12, 22, 32, …}{…,-28, -18, -8, 2, 12, 22, 32, …}
Theorem:Theorem: Let m be a positive integer. The integers Let m be a positive integer. The integers
a and b are congruent modulo m if and only if there a and b are congruent modulo m if and only if there
is an integer k such that a = b + km.is an integer k such that a = b + km.
Fall 2002 CMSC 203 - Discrete Structures 21
CongruencesCongruences
Theorem:Theorem: Let m be a positive integer. Let m be a positive integer.
If a If a b (mod m) and c b (mod m) and c d (mod m), then d (mod m), then
a + c a + c b + d (mod m) and ac b + d (mod m) and ac bd (mod m). bd (mod m).
Proof:Proof:
We know that a We know that a b (mod m) and c b (mod m) and c d (mod m) d (mod m)
implies that there are integers s and t with implies that there are integers s and t with
b = a + sm and d = c + tm. b = a + sm and d = c + tm.
Therefore,Therefore,
b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) andb + d = (a + sm) + (c + tm) = (a + c) + m(s + t) and
bd = (a + sm)(c + tm) = ac + m(at + cs + stm).bd = (a + sm)(c + tm) = ac + m(at + cs + stm).
Hence, a + c Hence, a + c b + d (mod m) and ac b + d (mod m) and ac bd (mod m). bd (mod m).
CongruencesCongruences
Theorem:Theorem: Let m be a positive integer. Let m be a positive integer.
If a If a b (mod m) and c b (mod m) and c d (mod m), then d (mod m), then
a + c a + c b + d (mod m) and ac b + d (mod m) and ac bd (mod m). bd (mod m).
Proof:Proof:
We know that a We know that a b (mod m) and c b (mod m) and c d (mod m) d (mod m)
implies that there are integers s and t with implies that there are integers s and t with
b = a + sm and d = c + tm. b = a + sm and d = c + tm.
Therefore,Therefore,
b + d = (a + sm) + (c + tm) = (a + c) + m(s + t) andb + d = (a + sm) + (c + tm) = (a + c) + m(s + t) and
bd = (a + sm)(c + tm) = ac + m(at + cs + stm).bd = (a + sm)(c + tm) = ac + m(at + cs + stm).
Hence, a + c Hence, a + c b + d (mod m) and ac b + d (mod m) and ac bd (mod m). bd (mod m).
Fall 2002 CMSC 203 - Discrete Structures 22
The Euclidean Algorithm The Euclidean Algorithm
The The Euclidean AlgorithmEuclidean Algorithm finds the finds the greatest greatest
common divisorcommon divisor of two integers a and b. of two integers a and b.
For example, if we want to find gcd(287, 91), we For example, if we want to find gcd(287, 91), we
dividedivide 287 by 91: 287 by 91:
287 = 91287 = 913 + 143 + 14
We know that for integers a, b and c,We know that for integers a, b and c,
if a | b and a | c, then a | (b + c).if a | b and a | c, then a | (b + c).
Therefore, any divisor of 287 and 91 must also be Therefore, any divisor of 287 and 91 must also be
a divisor of 287 - 91a divisor of 287 - 913 = 14.3 = 14.
Consequently, gcd(287, 91) = gcd(14, 91).Consequently, gcd(287, 91) = gcd(14, 91).
The Euclidean Algorithm The Euclidean Algorithm
The The Euclidean AlgorithmEuclidean Algorithm finds the finds the greatest greatest
common divisorcommon divisor of two integers a and b. of two integers a and b.
For example, if we want to find gcd(287, 91), we For example, if we want to find gcd(287, 91), we
dividedivide 287 by 91: 287 by 91:
287 = 91287 = 913 + 143 + 14
We know that for integers a, b and c,We know that for integers a, b and c,
if a | b and a | c, then a | (b + c).if a | b and a | c, then a | (b + c).
Therefore, any divisor of 287 and 91 must also be Therefore, any divisor of 287 and 91 must also be
a divisor of 287 - 91a divisor of 287 - 913 = 14.3 = 14.
Consequently, gcd(287, 91) = gcd(14, 91).Consequently, gcd(287, 91) = gcd(14, 91).
Fall 2002 CMSC 203 - Discrete Structures 23
The Euclidean Algorithm The Euclidean Algorithm
In the next step, we divide 91 by 14:In the next step, we divide 91 by 14:
91 = 1491 = 146 + 76 + 7
This means that gcd(14, 91) = gcd(14, 7).This means that gcd(14, 91) = gcd(14, 7).
So we divide 14 by 7:So we divide 14 by 7:
14 = 714 = 72 + 02 + 0
We find that 7 | 14, and thus gcd(14, 7) = 7.We find that 7 | 14, and thus gcd(14, 7) = 7.
Therefore, gcd(287, 91) = 7.Therefore, gcd(287, 91) = 7.
The Euclidean Algorithm The Euclidean Algorithm
In the next step, we divide 91 by 14:In the next step, we divide 91 by 14:
91 = 1491 = 146 + 76 + 7
This means that gcd(14, 91) = gcd(14, 7).This means that gcd(14, 91) = gcd(14, 7).
So we divide 14 by 7:So we divide 14 by 7:
14 = 714 = 72 + 02 + 0
We find that 7 | 14, and thus gcd(14, 7) = 7.We find that 7 | 14, and thus gcd(14, 7) = 7.
Therefore, gcd(287, 91) = 7.Therefore, gcd(287, 91) = 7.
Fall 2002 CMSC 203 - Discrete Structures 24
The Euclidean Algorithm The Euclidean Algorithm
In In pseudocodepseudocode, the algorithm can be implemented , the algorithm can be implemented
as follows: as follows:
procedureprocedure gcd(a, b: positive integers) gcd(a, b: positive integers)
x := ax := a
y := by := b
whilewhile y y 0 0
beginbegin
r := x r := x modmod y y
x := yx := y
y := ry := r
endend {x is gcd(a, b)}{x is gcd(a, b)}
The Euclidean Algorithm The Euclidean Algorithm
In In pseudocodepseudocode, the algorithm can be implemented , the algorithm can be implemented
as follows: as follows:
procedureprocedure gcd(a, b: positive integers) gcd(a, b: positive integers)
x := ax := a
y := by := b
whilewhile y y 0 0
beginbegin
r := x r := x modmod y y
x := yx := y
y := ry := r
endend {x is gcd(a, b)}{x is gcd(a, b)}
Fall 2002 CMSC 203 - Discrete Structures 25
Representations of IntegersRepresentations of Integers
Let b be a positive integer greater than 1.Let b be a positive integer greater than 1.
Then if n is a positive integer, it can be expressed Then if n is a positive integer, it can be expressed
uniquelyuniquely in the form: in the form:
n = an = a
kkbb
kk
+ a + a
k-1k-1bb
k-1k-1
+ … + a + … + a
11b + ab + a
00,,
where k is a nonnegative integer,where k is a nonnegative integer,
aa
00, a, a
11, …, a, …, a
kk are nonnegative integers less than b, are nonnegative integers less than b,
and aand a
kk 0. 0.
Example for b=10:Example for b=10:
859 = 8859 = 81010
22
+ 5 + 51010
11
+ 9 + 91010
00
Representations of IntegersRepresentations of Integers
Let b be a positive integer greater than 1.Let b be a positive integer greater than 1.
Then if n is a positive integer, it can be expressed Then if n is a positive integer, it can be expressed
uniquelyuniquely in the form: in the form:
n = an = a
kkbb
kk
+ a + a
k-1k-1bb
k-1k-1
+ … + a + … + a
11b + ab + a
00,,
where k is a nonnegative integer,where k is a nonnegative integer,
aa
00, a, a
11, …, a, …, a
kk are nonnegative integers less than b, are nonnegative integers less than b,
and aand a
kk 0. 0.
Example for b=10:Example for b=10:
859 = 8859 = 81010
22
+ 5 + 51010
11
+ 9 + 91010
00
Fall 2002 CMSC 203 - Discrete Structures 26
Representations of IntegersRepresentations of Integers
Example for b=2 (binary expansion):Example for b=2 (binary expansion):
(10110)(10110)
22 = 1 = 122
44
+ 1 + 122
22
+ 1 + 122
11
= (22) = (22)
1010
Example for b=16 (hexadecimal expansion):Example for b=16 (hexadecimal expansion):
(we use letters A to F to indicate numbers 10 to 15)(we use letters A to F to indicate numbers 10 to 15)
(3A0F)(3A0F)
1616 = 3 = 31616
33
+ 10 + 101616
22
+ 15 + 151616
00
= (14863) = (14863)
1010
Representations of IntegersRepresentations of Integers
Example for b=2 (binary expansion):Example for b=2 (binary expansion):
(10110)(10110)
22 = 1 = 122
44
+ 1 + 122
22
+ 1 + 122
11
= (22) = (22)
1010
Example for b=16 (hexadecimal expansion):Example for b=16 (hexadecimal expansion):
(we use letters A to F to indicate numbers 10 to 15)(we use letters A to F to indicate numbers 10 to 15)
(3A0F)(3A0F)
1616 = 3 = 31616
33
+ 10 + 101616
22
+ 15 + 151616
00
= (14863) = (14863)
1010
Fall 2002 CMSC 203 - Discrete Structures 27
Representations of IntegersRepresentations of Integers
How can we construct the base b expansion of an How can we construct the base b expansion of an
integer n?integer n?
First, divide n by b to obtain a quotient qFirst, divide n by b to obtain a quotient q
00 and and
remainder aremainder a
00, that is,, that is,
n = bqn = bq
00 + a + a
00, where 0 , where 0 a a
00 < b. < b.
The remainder aThe remainder a
00 is the rightmost digit in the base b is the rightmost digit in the base b
expansion of n.expansion of n.
Next, divide qNext, divide q
00 by b to obtain: by b to obtain:
qq
00 = bq = bq
11 + a + a
11, where 0 , where 0 a a
11 < b. < b.
aa
11 is the second digit from the right in the base b is the second digit from the right in the base b
expansion of n. Continue this process until you obtain a expansion of n. Continue this process until you obtain a
quotient equal to zero.quotient equal to zero.
Representations of IntegersRepresentations of Integers
How can we construct the base b expansion of an How can we construct the base b expansion of an
integer n?integer n?
First, divide n by b to obtain a quotient qFirst, divide n by b to obtain a quotient q
00 and and
remainder aremainder a
00, that is,, that is,
n = bqn = bq
00 + a + a
00, where 0 , where 0 a a
00 < b. < b.
The remainder aThe remainder a
00 is the rightmost digit in the base b is the rightmost digit in the base b
expansion of n.expansion of n.
Next, divide qNext, divide q
00 by b to obtain: by b to obtain:
00 = bq = bq
11 + a + a
11, where 0 , where 0 a a
11 < b. < b.
aa
11 is the second digit from the right in the base b is the second digit from the right in the base b
expansion of n. Continue this process until you obtain a expansion of n. Continue this process until you obtain a
quotient equal to zero.quotient equal to zero.
Fall 2002 CMSC 203 - Discrete Structures 28
Representations of IntegersRepresentations of Integers
Example:Example:
What is the base 8 expansion of (12345)What is the base 8 expansion of (12345)
10 10 ??
First, divide 12345 by 8:First, divide 12345 by 8:
12345 = 812345 = 81543 + 11543 + 1
1543 = 81543 = 8192 + 7192 + 7
192 = 8192 = 824 + 024 + 0
24 = 824 = 83 + 03 + 0
3 = 83 = 80 + 30 + 3
The result is: (12345)The result is: (12345)
1010 = (30071) = (30071)
88..
Representations of IntegersRepresentations of Integers
Example:Example:
What is the base 8 expansion of (12345)What is the base 8 expansion of (12345)
10 10 ??
First, divide 12345 by 8:First, divide 12345 by 8:
12345 = 812345 = 81543 + 11543 + 1
1543 = 81543 = 8192 + 7192 + 7
192 = 8192 = 824 + 024 + 0
24 = 824 = 83 + 03 + 0
3 = 83 = 80 + 30 + 3
The result is: (12345)The result is: (12345)
1010 = (30071) = (30071)
88..
Fall 2002 CMSC 203 - Discrete Structures 29
Representations of IntegersRepresentations of Integers
procedure procedure base_b_expansion(n, b: positive integers)base_b_expansion(n, b: positive integers)
q := nq := n
k := 0k := 0
whilewhile q q 0 0
beginbegin
aa
kk := q mod b := q mod b
q := q := q/bq/b
k := k + 1k := k + 1
endend
{the base b expansion of n is (a{the base b expansion of n is (a
k-1k-1 … a … a
11aa
00))
b b }}
Representations of IntegersRepresentations of Integers
procedure procedure base_b_expansion(n, b: positive integers)base_b_expansion(n, b: positive integers)
q := nq := n
k := 0k := 0
whilewhile q q 0 0
beginbegin
aa
kk := q mod b := q mod b
q := q := q/bq/b
k := k + 1k := k + 1
endend
{the base b expansion of n is (a{the base b expansion of n is (a
k-1k-1 … a … a
11aa
00))
b b }}
Fall 2002 CMSC 203 - Discrete Structures 30
Addition of IntegersAddition of Integers
Let a = (aLet a = (a
n-1n-1aa
n-2n-2…a…a
11aa
00))
22, b = (b, b = (b
n-1n-1bb
n-2n-2…b…b
11bb
00))
2.2.
How can we add these two binary numbers?How can we add these two binary numbers?
First, add their rightmost bits:First, add their rightmost bits:
aa
00 + b + b
00 = c = c
002 + s2 + s
00,,
where swhere s
00 is the is the rightmost bitrightmost bit in the binary in the binary
expansion of a + b, and cexpansion of a + b, and c
00 is the is the carrycarry..
Then, add the next pair of bits and the carry:Then, add the next pair of bits and the carry:
aa
11 + b + b
1 1 + c+ c
00 = c = c
112 + s2 + s
11,,
where swhere s
11 is the is the next bitnext bit in the binary expansion of in the binary expansion of
a + b, and ca + b, and c
11 is the carry. is the carry.
Addition of IntegersAddition of Integers
Let a = (aLet a = (a
n-1n-1aa
n-2n-2…a…a
11aa
00))
22, b = (b, b = (b
n-1n-1bb
n-2n-2…b…b
11bb
00))
2.2.
How can we add these two binary numbers?How can we add these two binary numbers?
First, add their rightmost bits:First, add their rightmost bits:
aa
00 + b + b
00 = c = c
002 + s2 + s
00,,
where swhere s
00 is the is the rightmost bitrightmost bit in the binary in the binary
expansion of a + b, and cexpansion of a + b, and c
00 is the is the carrycarry..
Then, add the next pair of bits and the carry:Then, add the next pair of bits and the carry:
aa
11 + b + b
1 1 + c+ c
00 = c = c
112 + s2 + s
11,,
where swhere s
11 is the is the next bitnext bit in the binary expansion of in the binary expansion of
a + b, and ca + b, and c
11 is the carry. is the carry.
Fall 2002 CMSC 203 - Discrete Structures 31
Addition of IntegersAddition of Integers
Continue this process until you obtain cContinue this process until you obtain c
n-1n-1..
The leading bit of the sum is sThe leading bit of the sum is s
nn = c = c
n-1n-1..
The result is:The result is:
a + b = (sa + b = (s
nnss
n-1n-1…s…s
11ss
00))
22
Addition of IntegersAddition of Integers
Continue this process until you obtain cContinue this process until you obtain c
n-1n-1..
The leading bit of the sum is sThe leading bit of the sum is s
nn = c = c
n-1n-1..
The result is:The result is:
a + b = (sa + b = (s
nnss
n-1n-1…s…s
11ss
00))
22
Fall 2002 CMSC 203 - Discrete Structures 32
Addition of IntegersAddition of Integers
Example:Example:
Add a = (1110)Add a = (1110)
22 and b = (1011) and b = (1011)
22..
aa
00 + b + b
00 = 0 + 1 = 0 = 0 + 1 = 02 + 1, so that c2 + 1, so that c
00 = 0 and s = 0 and s
00 = 1. = 1.
aa
11 + b + b
1 1 + c+ c
00 = 1 + 1 + 0 = 1 = 1 + 1 + 0 = 12 + 0, so c2 + 0, so c
11 = 1 and s = 1 and s
11 = 0. = 0.
aa
22 + b + b
2 2 + c+ c
11 = 1 + 0 + 1 = 1 = 1 + 0 + 1 = 12 + 0, so c2 + 0, so c
22 = 1 and s = 1 and s
22 = 0. = 0.
aa
33 + b + b
3 3 + c+ c
22 = 1 + 1 + 1 = 1 = 1 + 1 + 1 = 12 + 1, so c2 + 1, so c
33 = 1 and s = 1 and s
33 = 1. = 1.
ss
44 = c = c
33 = 1. = 1.
Therefore, s = a + b = (11001)Therefore, s = a + b = (11001)
22..
Addition of IntegersAddition of Integers
Example:Example:
Add a = (1110)Add a = (1110)
22 and b = (1011) and b = (1011)
22..
aa
00 + b + b
00 = 0 + 1 = 0 = 0 + 1 = 02 + 1, so that c2 + 1, so that c
00 = 0 and s = 0 and s
00 = 1. = 1.
aa
11 + b + b
1 1 + c+ c
00 = 1 + 1 + 0 = 1 = 1 + 1 + 0 = 12 + 0, so c2 + 0, so c
11 = 1 and s = 1 and s
11 = 0. = 0.
aa
22 + b + b
2 2 + c+ c
11 = 1 + 0 + 1 = 1 = 1 + 0 + 1 = 12 + 0, so c2 + 0, so c
22 = 1 and s = 1 and s
22 = 0. = 0.
aa
33 + b + b
3 3 + c+ c
22 = 1 + 1 + 1 = 1 = 1 + 1 + 1 = 12 + 1, so c2 + 1, so c
33 = 1 and s = 1 and s
33 = 1. = 1.
ss
44 = c = c
33 = 1. = 1.
Therefore, s = a + b = (11001)Therefore, s = a + b = (11001)
22..
Fall 2002 CMSC 203 - Discrete Structures 33
Addition of IntegersAddition of Integers
How do we (humans) add two integers?How do we (humans) add two integers?
Example: Example: 75837583
+ +49324932
5511552211
111111 carrycarry
Binary expansions: Binary expansions: (1011)(1011)
22
+ + (1010)(1010)
22
1100
carrycarry11
1100
11
11(( ))
22
Addition of IntegersAddition of Integers
How do we (humans) add two integers?How do we (humans) add two integers?
Example: Example: 75837583
+ +49324932
5511552211
111111 carrycarry
Binary expansions: Binary expansions: (1011)(1011)
22
+ + (1010)(1010)
22
1100
carrycarry11
1100
11
11(( ))
22
Fall 2002 CMSC 203 - Discrete Structures 34
Addition of IntegersAddition of Integers
Let a = (aLet a = (a
n-1n-1aa
n-2n-2…a…a
11aa
00))
22, b = (b, b = (b
n-1n-1bb
n-2n-2…b…b
11bb
00))
2.2.
How can we How can we algorithmically algorithmically add these two binary add these two binary
numbers?numbers?
First, add their rightmost bits:First, add their rightmost bits:
aa
00 + b + b
00 = c = c
002 + s2 + s
00,,
where swhere s
00 is the is the rightmost bitrightmost bit in the binary expansion in the binary expansion
of a + b, and cof a + b, and c
00 is the is the carrycarry..
Then, add the next pair of bits and the carry:Then, add the next pair of bits and the carry:
aa
11 + b + b
1 1 + c+ c
00 = c = c
112 + s2 + s
11,,
where swhere s
11 is the is the next bitnext bit in the binary expansion of a + in the binary expansion of a +
b, and cb, and c
11 is the carry. is the carry.
Addition of IntegersAddition of Integers
Let a = (aLet a = (a
n-1n-1aa
n-2n-2…a…a
11aa
00))
22, b = (b, b = (b
n-1n-1bb
n-2n-2…b…b
11bb
00))
2.2.
How can we How can we algorithmically algorithmically add these two binary add these two binary
numbers?numbers?
First, add their rightmost bits:First, add their rightmost bits:
aa
00 + b + b
00 = c = c
002 + s2 + s
00,,
where swhere s
00 is the is the rightmost bitrightmost bit in the binary expansion in the binary expansion
of a + b, and cof a + b, and c
00 is the is the carrycarry..
Then, add the next pair of bits and the carry:Then, add the next pair of bits and the carry:
aa
11 + b + b
1 1 + c+ c
00 = c = c
112 + s2 + s
11,,
where swhere s
11 is the is the next bitnext bit in the binary expansion of a + in the binary expansion of a +
b, and cb, and c
11 is the carry. is the carry.
Fall 2002 CMSC 203 - Discrete Structures 35
Addition of IntegersAddition of Integers
Continue this process until you obtain cContinue this process until you obtain c
n-1n-1..
The leading bit of the sum is sThe leading bit of the sum is s
nn = c = c
n-1n-1..
The result is:The result is:
a + b = (sa + b = (s
nnss
n-1n-1…s…s
11ss
00))
22
Addition of IntegersAddition of Integers
Continue this process until you obtain cContinue this process until you obtain c
n-1n-1..
The leading bit of the sum is sThe leading bit of the sum is s
nn = c = c
n-1n-1..
The result is:The result is:
a + b = (sa + b = (s
nnss
n-1n-1…s…s
11ss
00))
22
Fall 2002 CMSC 203 - Discrete Structures 36
Addition of IntegersAddition of Integers
Example:Example:
Add a = (1110)Add a = (1110)
22 and b = (1011) and b = (1011)
22..
aa
00 + b + b
00 = 0 + 1 = 0 = 0 + 1 = 02 + 1, so that c2 + 1, so that c
00 = 0 and s = 0 and s
00 = 1. = 1.
aa
11 + b + b
1 1 + c+ c
00 = 1 + 1 + 0 = 1 = 1 + 1 + 0 = 12 + 0, so c2 + 0, so c
11 = 1 and s = 1 and s
11 = 0. = 0.
aa
22 + b + b
2 2 + c+ c
11 = 1 + 0 + 1 = 1 = 1 + 0 + 1 = 12 + 0, so c2 + 0, so c
22 = 1 and s = 1 and s
22 = 0. = 0.
aa
33 + b + b
3 3 + c+ c
22 = 1 + 1 + 1 = 1 = 1 + 1 + 1 = 12 + 1, so c2 + 1, so c
33 = 1 and s = 1 and s
33 = 1. = 1.
ss
44 = c = c
33 = 1. = 1.
Therefore, s = a + b = (11001)Therefore, s = a + b = (11001)
22..
Addition of IntegersAddition of Integers
Example:Example:
Add a = (1110)Add a = (1110)
22 and b = (1011) and b = (1011)
22..
aa
00 + b + b
00 = 0 + 1 = 0 = 0 + 1 = 02 + 1, so that c2 + 1, so that c
00 = 0 and s = 0 and s
00 = 1. = 1.
aa
11 + b + b
1 1 + c+ c
00 = 1 + 1 + 0 = 1 = 1 + 1 + 0 = 12 + 0, so c2 + 0, so c
11 = 1 and s = 1 and s
11 = 0. = 0.
aa
22 + b + b
2 2 + c+ c
11 = 1 + 0 + 1 = 1 = 1 + 0 + 1 = 12 + 0, so c2 + 0, so c
22 = 1 and s = 1 and s
22 = 0. = 0.
aa
33 + b + b
3 3 + c+ c
22 = 1 + 1 + 1 = 1 = 1 + 1 + 1 = 12 + 1, so c2 + 1, so c
33 = 1 and s = 1 and s
33 = 1. = 1.
ss
44 = c = c
33 = 1. = 1.
Therefore, s = a + b = (11001)Therefore, s = a + b = (11001)
22..
Fall 2002 CMSC 203 - Discrete Structures 37
Addition of IntegersAddition of Integers
procedure procedure add(a, b: positive integers)add(a, b: positive integers)
c := 0c := 0
for j := 0 to n-1for j := 0 to n-1
beginbegin
d := d := (a(a
jj + b + b
jj + c)/2 + c)/2
ss
jj := a := a
jj + b + b
jj + c – 2d + c – 2d
c := dc := d
endend
ss
nn := c := c
{the binary expansion of the sum is (s{the binary expansion of the sum is (s
nnss
n-1n-1…s…s
11ss
00))
22}}
Addition of IntegersAddition of Integers
procedure procedure add(a, b: positive integers)add(a, b: positive integers)
c := 0c := 0
for j := 0 to n-1for j := 0 to n-1
beginbegin
d := d := (a(a
jj + b + b
jj + c)/2 + c)/2
ss
jj := a := a
jj + b + b
jj + c – 2d + c – 2d
c := dc := d
endend
ss
nn := c := c
{the binary expansion of the sum is (s{the binary expansion of the sum is (s
nnss
n-1n-1…s…s
11ss
00))
22}}
Tags
Categories
EducationDownload
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 5
- Slides 37
- Age 77 days
Related Slideshows
11
TLE-9-Prepare-Salad-and-Dressing.pptxkkk
MaAngelicaCanceran
32 views
12
LESSON 1 ABOUT MEDIA AND INFORMATION.pptx
JojitGueta
26 views
60
GRADE-8-AQUACULTURE-WEEKQ1.pdfdfawgwyrsewru
MaAngelicaCanceran
41 views
26
Feelings PP Game FOR CHILDREN IN ELEMENTARY SCHOOL.pptx
KaistaGlow
40 views
![Jeopardy_Figures_of_Speech_Template.pptx [Autosaved].pptx](https://slidepub.com/thumb/5828/284015828.jpg)
54
Jeopardy_Figures_of_Speech_Template.pptx [Autosaved].pptx
acecamero20
25 views
7
Jeopardy_Figures_of_Speech.pptxvdsvdsvsdvsd
acecamero20
25 views