Numerical Algorithms

x 0 1 2 3 4 5 6 7 8 9
x−1 1 7 3 9

4/12/2006 Numerical Algorithms 1

Outline
Divisibility and primes
Modular arithmetic
Euclid’s GCD algorithm
Multiplicative inverses
Powers
Fermat’s little theorem
Euler’s theorem
4/12/2006 Numerical Algorithms 2
Facts About Numbers
Prime number p:
„ p is an integer
„ p≥2
„ The only divisors of p are 1 and p
Examples
„ 2, 7, 19 are primes
„ −3, 0, 1, 6 are not primes
Prime decomposition of a positive integer n:
n = p1e1 × … × pkek
Example:
„ 200 = 23 × 52
Fundamental Theorem of Arithmetic
The prime decomposition of a positive integer is unique
4/12/2006 Numerical Algorithms 3
Greatest Common Divisor
The greatest common divisor (GCD) of two positive
integers a and b, denoted gcd(a, b), is the largest
positive integer that divides both a and b
The above definition is extended to arbitrary integers
Examples:
gcd(18, 30) = 6 gcd(0, 20) = 20
gcd(−21, 49) = 7
Two integers a and b are said to be relatively prime if
gcd(a, b) = 1
Example:
„ Integers 15 and 28 are relatively prime

4/12/2006 Numerical Algorithms 4

Modular Arithmetic
Modulo operator for a positive integer n
r = a mod n
equivalent to
a = r + kn
and
r = a − ⎣a/n⎦ n
Example:
29 mod 13 = 3 13 mod 13 = 0 −1 mod 13 = 12
29 = 3 + 2×13 13 = 0 + 1×13 12 = −1 + 1×13
Modulo and GCD:
gcd(a, b) = gcd(b, a mod b)
Example:
gcd(21, 12) = 3 gcd(12, 21 mod 12) = gcd(12, 9) = 3

4/12/2006 Numerical Algorithms 5

Euclid’s GCD Algorithm
Euclid’s algorithm for Algorithm EuclidGCD(a, b)
computing the GCD Input integers a and b
repeatedly applies the Output gcd(a, b)
formula
if b = 0
gcd(a, b) = gcd(b, a mod b) return a
Example else
„ gcd(412, 260) = 4 return EuclidGCD(b, a mod b)

a 412 260 152 108 44 20 4

b 260 152 108 44 20 4 0

4/12/2006 Numerical Algorithms 6

Analysis
Let ai and bi be the arguments of the i-th recursive call of
algorithm EuclidGCD
We have
ai + 2 = bi + 1 = ai mod ai + 1 < ai + 1
Sequence a1, a2, …, an decreases exponentially, namely
ai + 2 ≤ ½ ai for i > 1
Case 1 ai + 1 ≤ ½ ai ai + 2 < ai + 1 ≤ ½ ai
Case 2 ai + 1 > ½ ai ai + 2 = ai mod ai + 1 = ai − ai + 1 ≤ ½ ai
Thus, the maximum number of recursive calls of algorithm
EuclidGCD(a. b) is
1 + 2 log max(a. b)
Algorithm EuclidGCD(a, b) executes O(log max(a, b)) arithmetic
operations
The running time can also be expressed as O(log min(a, b))

4/12/2006 Numerical Algorithms 7

Multiplicative Inverses (1)
The residues modulo a positive integer n are the set
Zn = {0, 1, 2, …, (n − 1)}
Let x and y be two elements of Zn such that
xy mod n = 1
We say that y is the multiplicative inverse of x in Zn
and we write y = x−1
Example:
„ Multiplicative inverses of the residues modulo 11

x 0 1 2 3 4 5 6 7 8 9 10
x−1 1 6 4 3 9 2 8 7 5 10

4/12/2006 Numerical Algorithms 8

Multiplicative Inverses (2)
Theorem
An element x of Zn has a multiplicative inverse if and only if x and
n are relatively prime
Example
„ The elements of Z10 with a multiplicative inverse are 1, 3, 5, 7
Corollary
If is p is prime, every nonzero residue in Zp has a multiplicative
inverse
Theorem
A variation of Euclid’s GCD algorithm computes the multiplicative
inverse of an element x of Zn or determines that it does not exist

x 0 1 2 3 4 5 6 7 8 9
x−1 1 7 3 9
4/12/2006 Numerical Algorithms 9
Example: Measuring Lengths
Consider a stick of length a and a stick of length b such that a and
b are relatively prime
Given two integers i and j, we can measure length
n = ia + jb
We show that any integer n can be written as n = ia + jb for some
integers i and j
„ Let s be the inverse of a in Zb We have sa mod b = 1
„ There exists integer t such that sa + tb = 1
„ Pick i = ns and j = nt
Thus, given two sticks of relatively prime integer lengths, we can
measure any integer length
Example, measure length 2 with sticks of length 3 and 7

3 3 3 3
7 7

4/12/2006 Numerical Algorithms 10

Example: Double Hashing
Consider a hash table whose size n is a prime
In open addressing with double hashing, an operation
on key x probes the following locations modulo n
i, i + d, i + 2d, i + 3d, …, i + (n – 1)d
where i = h1(x) and d = h2(x)
We show that each table location is probed by this
sequence once
„ Suppose (i + jd) mod n = (i + kd) mod n for some integers j and
k in the range [0, n – 1]
„ We have (j − k)d mod n = 0
„ Since n is prime, we have that n and d are relatively prime
„ Thus, d has an inverse d− 1 in Zn
„ Multiplying each side by d− 1, we obtain (j − k) mod n = 0
„ We conclude that j = k
4/12/2006 Numerical Algorithms 11
Powers
Let p be a prime
The sequences of successive powers of the elements of Zp
exhibit repeating subsequences
The sizes of the repeating subsequences and the number of
their repetitions are the divisors of p − 1
Example (p = 7)
x x2 x3 x4 x5 x6
1 1 1 1 1 1
2 4 1 2 4 1
3 2 6 4 5 1
4 2 1 4 2 1
5 4 6 2 3 1
6 1 6 1 6 1
4/12/2006 Numerical Algorithms 12
Fermat’s Little Theorem
Theorem
Let p be a prime. For each nonzero residue x of Zp,
we have xp − 1 mod p = 1
Example (p = 5):
14 mod 5 = 1 24 mod 1 = 16 mod 5 = 1
34 mod 1 = 81 mod 5 = 1 44 mod 1 = 256 mod 5 = 1
Corollary
Let p be a prime. For each nonzero residue x of Zp,
the multiplicative inverse of x is xp − 2 mod p
Proof
x(xp − 2 mod p) mod p = xxp − 2 mod p = xp − 1 mod p = 1

4/12/2006 Numerical Algorithms 13

Euler’s Theorem
The multiplicative group for Zn, denoted with Z*n, is the subset of
elements of Zn relatively prime with n
The totient function of n, denoted with φ(n), is the size of Z*n
Example
Z*10 = { 1, 3, 7, 9 } φ(10) = 4
If p is prime, we have
Z*p = {1, 2, …, (p − 1)} φ(p) = p − 1
Theorem
For each element x of Z*n, we have xφ(n) mod n = 1
Example (n = 10)
3φ(10) mod 10 = 34 mod 10 = 81 mod 10 = 1
7φ(10) mod 10 = 74 mod 10 = 2401 mod 10 = 1
9φ(10) mod 10 = 94 mod 10 = 6561 mod 10 = 1

4/12/2006 Numerical Algorithms 14