|
Division Algorithm
Division is
not an easy matter as multiplication. In our childhood we were instructed to execute
the “Long Division” mechanically without paying to much attention to its
inherent complexity.
Given any two integers a,
b where b>0, there exists a unique pair of integers [q, r] such that a = b.q + r , where q is called the quotient of a and b, and r is the
remainder.
Warning: The
division algorithm is not an algorithm at all but a theorem.
Its name derives from the fact that it was first used empirically as an
algorithm to compute the quotient of two integers.
Multiple
and Divisor: Given a and b pertaining to the set of integers Z a is called a multiple of b if a = b.q for
some integer q. We may also say that b is a divisor of
a using the notation b | a. We may also say that b is a factor
of a, or that a is divisible by b.
Division in Z could be
formally stated as: For any integers a and b, with
b>0, there exist a unique integer q (the quotient) and r (the remainder)
such that
a = b.q + r, with 0  r<b.
The Euclidean Algorithm
gcd
The greatest common divisor or gcd of two numbers a and b can be
computed by using a procedure known as the Euclidean
algorithm. First, note that if a  0 and b | a,
then gcd(a,
b) = |b|. The next observation provides the basis for the Euclidean algorithm.
If a = b.q + r, then (a, b) = (b, r). Thus given
integers a>b>0, the Euclidean algorithm uses the division algorithm
repeatedly to obtain
a = b.q1 + r1,
with 0 r1<
b
b = r1.q2 + r2, with 0 r2<
r1,
……………………………….
Since r1 > r2 > . . . , the
remainders get smaller and smaller, and after a finite number of steps we
obtain a remainder rn+1 = 0. Thus gcd(a, b) = gcd(b, r1) = . . . = rn.
To see how
the algorithm works stepwise let’s tabulate how Dividend (D), divisor (d), quotient
(q) and remainder (r) transform along
iterations for these examples: (1525, 125), (137, 9), (1908, 900)
|
Iter
|
D
|
d
|
q
|
r
|
|
1
|
1525
|
125
|
12
|
25
|
|
2
|
25
|
25
|
1
|
0
|
|
|
|
|
|
|
|
1
|
137
|
9
|
15
|
2
|
|
2
|
9
|
2
|
4
|
1
|
|
3
|
2
|
1
|
2
|
0
|
|
|
|
|
|
|
|
1
|
1908
|
900
|
2
|
108
|
|
2
|
900
|
108
|
8
|
36
|
|
3
|
108
|
36
|
3
|
0
|
Where in
red we depict the corresponding gcd’s.
Turning back to our childhood let’s remember the “factorization” procedure for
the (1908, 900) example:
|
1908
|
3
|
|
900
|
2
|
|
636
|
3
|
450
|
5
|
|
212
|
2
|
90
|
5
|
|
106
|
2
|
18
|
3
|
|
53
|
53
|
6
|
3
|
|
1
|
1
|
2
|
2
|
|
|
|
1
|
|
|
1908 = 32 .22 .53.1
|
900 = 22 .32.52
|
Where we
depict the gcd obtained as the product of two common
factors: 4 and 9.
The
iteration logic is very simple, namely:
d becomes D
r becomes d
at each
iteration and stops when the r=0 condition is attained.
Primes:
Nonzero integers a and
b are said to be relatively primes if (a, b) = 1. Formally this
assertion could be stated as: Let a, b be nonzero integers. Then (a, b)=1 if and only if there exist integers m, n such that
ma + nb
= 1 .
With the following properties: for a, b, c integers
(i) If b |
ac, then b | (a, b)c.
(ii) If b | ac and (a, b)=1, then b | c.
(iii) If b | a, c | a and (b, c)=1, then bc | a.
(iv) (a,
bc)=1 if and only if (a, b)=1 and (a, c)=1.
Prime Numbers: An integer p>1 is called a prime
number if its only divisors are ± 1 and ± p. An integer a > 1 is called composite if it is not prime, and an integer p>1 is
prime if and only if it satisfies the following property: If p | ab for integers a and b, then
either p | a or p | b.
Factorization: Any integer a>1 can be factored
uniquely as a product of prime numbers, in the form
a = p1m1
p2m2 · · · pnmn
Where p1 < p2
< · · · < pn and exponents m1, m2 , . . . , mn
are all positive. There exist infinite prime numbers.
lcd
The Least common multiple or
the lcm of any two nonzero integers a and b is a number m subject
to the following restrictions:
(i) m
is a multiple of both a and b, and
(ii) any
multiple of both a and b is also a multiple of m.
And we may
use the notation lcm [a,b]
for the least common multiple of a and b.
Properties:
Let a and b be
positive integers with prime factorizations
a = p1a1 p2a2
· · · pnan and
b = p1b1 p2b2
· · · pnbn ,
with ai  0 and bi 0 for all i
(allowing use of the same prime factors.)
For each i let di
=min { ai, bi
} and let mi =max { ai, bi
}. Then we have the following factorization scheme:
(i) gcd(a,b)
= p1d1 p2d2 ·
· · pndn
(ii) lcm[a,b] = p1m1 p2m2
· · · pnmn
Congruence
Integers a and b are said to be congruent modulo n, being n a
positive integer if they have the same remainder when divided by n. This is
denoted by writing a  b (mod n).
When working with congruence modulo n, the integer n is called the modulus. By the preceding proposition, a b (mod n) if and only if (a – b) = n.q for some integer q. We can write this in the form a = b
+ n.q, for some integer q. This observation gives a
very useful method of replacing congruence with an equation (over Z). On
the other hand any equation can be converted to a congruence modulo n by simply
changing the = sign to . In doing
so, any term congruent to 0 can simply be omitted. Thus the equation a = b + n q
would be converted back to a b (mod n).
Some properties and theorems: Let n>0 be an integer. Then the
following conditions hold for all integers a, b, c, d:
(i) If a c (mod n) and b d (mod n), then a  b c d (mod n),
and ab c.d (mod n).
(ii) If a + c a + d (mod n), then c d (mod n)
(iii) If ac a.d (mod n)
and (a, n)=1, then c d (mod n).
Let a and n>1 be integers. There exists an integer b such
that a.b 1 (mod n) if and only if (a, n)=1.
The congruence a.x b (mod n) has a solution if and only if b is
divisible by d, where d = (a, n).
If d | b, then there are d distinct solutions modulo n, and these solutions are
congruent modulo n / d.
The Chinese
Remainder Theorem:
Let n and m be positive integers, with (n, m) = 1. Then the system of
congruence
x a (mod n) x b (mod m)
has a
solution. Moreover, any two solutions are congruent modulo m. n.
Congruence Classes: Let a and n>0 be integers. The
set of all integers which have the same remainder when divided by n is called
the congruence class of a modulo n, and is denoted by [a]n,
where
[a]n
= { x  Z | x a (mod n) }.
All
congruence classes modulo n set is called the module n set of integers, denoted by Zn.
Some properties and
Theorems: Let n be
a positive integer, and let a, b be any integers. Then the addition and
multiplication of congruence classes given below are well-defined by:
[a]n + [b]n
= [a+b]n , [a]n[b]n
= [ab]n.
If [a]n belongs to Zn, and [a]n[b]n
= [0]n for some nonzero congruence class [b]n, then [a]n
is called a divisor of zero, modulo n.
If [a]n belongs
to Zn, and [a]n[b]n = [1]n,
for some congruence class [b]n, then [b]n is called a multiplicative
inverse of [a]n and is denoted by [a]n-1.
In this case, we say that [a]n and [b]n are invertible
elements of Zn, or units of Zn.
Let n be a positive
integer. It follows:
(i) The congruence class [a]n
has a multiplicative inverse in Zn if and only if (a, n)=1.
(ii) A nonzero element of Zn either has
a multiplicative inverse or is a divisor of zero.
The following
conditions on the modulus n > 0 are equivalent:
(i) The number n is prime.
(ii) Zn has no divisors of zero, except
[0]n.
(iii) Every nonzero element of Zn
has a multiplicative inverse.
Totient
Let n be a
positive integer. The number of positive integers less than or equal to n which
are relatively prime to n will be denoted by  (n). This
function is called Euler's phi-function, or the Totient
function.
If the prime factorization
of n is n = p1m1 p2m2
· · · pnmn , then
(n) = n(1-1/p1)(1-1/p2) · · · (1-1/pk).
The set of
units of Zn, the congruence classes [a]n, such
that (a, n)=1, will be denoted by
Zn×.
Another Euler Theorem: If (a, n) = 1, then a (n) 1 (mod n).
Fermat
Corollary: If p is prime, then ap a (mod p), for any integer a.
Some discussion and
properties
In Z and R realms
Suppose p and q
are relatively prime integers, and 0 < p < q. If q has any prime factors
besides 2 and 5, then a decimal expansion of p/q will eventually start to
repeat. How long will the repeating part be?
Looking at the
sequence of digits is actually a very difficult way to approach this problem.
It's much simpler to look at the sequence of remainders. Remember
how long division works. At every step, we have a remainder r, bounded by 0
<= r < q. To get the next digit in the expansion, we figure out how many
times q goes into 10*r; this gives us a digit and a new remainder. In C++ code,
we may write the long division algorithm this way:
/* Compute n digits of p/q */ r = p; for (i = 0; i < ndigits; ++i) { d[i] = (10*r) / q; r = (10*r) % q; }
The operator % is the mod operator that computes the
remainder in a division. If two results are equivalent modulo m, it means that
they pertain to the same equivalence class. For example the bit sequence [0 1 2
3] in base 4 represent the infinite sequences [0 1 2 3], [4 5 6 7], [8 9 10 11],……., sequences of numbers that differ by a multiple of the
base 4 used as module.
The C code above
computes then a sequence of remainders, which look like
r[k] = (p*10^k) % q
If q has prime
factors other than 2 and 5, we are going to find a remainder which is prime relative to q; at that point. From this point onwards
the remainders are all units of the ring of integers modulo q (Z_q). For instance,
4 and 7 are relatively prime, so 4 is a unit in Z_7;
the inverse is 2, since 4*2 = 7+1 = 1 modulo 7.
Euler Phi Function: The set of units in Z_q is an important object in number theory: the number of
natural numbers less than q which are prime relative to q is written phi(q) and is called Euler's
phi function or Euler's totient function.
Division Algorithm script From Ian Kaplan /* Copyright stuff Use of this program, for any purpose, is granted the author, Ian Kaplan, as long as this copyright notice is included in the source code or any source code derived from this program. The user assumes all responsibility for using this code. Ian Kaplan, October 1996 */ void unsigned_divide(unsigned int dividend, unsigned int divisor, unsigned int "ient, unsigned int &remainder ) { unsigned int t, num_bits; unsigned int q, bit, d; int i; remainder = 0; quotient = 0; if (divisor == 0) return; if (divisor > dividend) { remainder = dividend; return; } if (divisor == dividend) { quotient = 1; return; } num_bits = 32; while (remainder < divisor) { bit = (dividend & 0x80000000) >> 31; remainder = (remainder << 1) | bit; d = dividend; dividend = dividend << 1; num_bits--; } /* The loop, above, always goes one iteration too far. To avoid inserting an "if" statement inside the loop the last iteration is simply reversed. */ dividend = d; remainder = remainder >> 1; num_bits++; for (i = 0; i < num_bits; i++) { bit = (dividend & 0x80000000) >> 31; remainder = (remainder << 1) | bit; t = remainder - divisor; q = !((t & 0x80000000) >> 31); dividend = dividend << 1; quotient = (quotient << 1) | q; if (q) { remainder = t; } } } /* unsigned_divide */ #define ABS(x) ((x) < 0 ? -(x) : (x)) void signed_divide(int dividend, int divisor, int "ient, int &remainder ) { unsigned int dend, dor; unsigned int q, r; dend = ABS(dividend); dor = ABS(divisor); unsigned_divide( dend, dor, q, r ); /* the sign of the remainder is the same as the sign of the dividend and the quotient is negated if the signs of the operands are opposite */ quotient = q; if (dividend < 0) { remainder = -r; if (divisor > 0) quotient = -q; } else { /* positive dividend */ remainder = r; if (divisor < 0) quotient = -q; } } /* signed_divide */
|
