142
Proofs, Induction, and Number Theory
d. ArraySumD (integers n, a[1], a[2], … , a[n])
Local variables:
integers i, j
i = 1
j = a[1]
while i ≤ n do
j = j + a[i + 1]
i = i + 1
end while
//j now has the value a[1] + a[2] + g+ a[n]
return j
end function ArraySumD
Exercises 23–28 concern a variation of the Euclidean algorithm more suited to computer implementation. The
original GCD algorithm relies on repeated integer divisions to compute remainders. The following variation,
called the binary GCD algorithm, also uses divisions, but only by 2, plus subtraction and testing for parity (oddness or evenness). Given that the numbers are stored in the computer in binary form, these operations are simple
and often done using built-in circuits. Testing for even/odd can be done using bitwise conjunction of N & 1,
which results in 1 if and only if N is odd. Given an even N, division by 2 is easily accomplished by a 1-bit right
shift operation, where all bits are shifted one place to the right (the rightmost bit disappears), and the leftmost
bit is set to 0. (Multiplication by 2 is a 1-bit left shift.) Subtraction involves the 2’s complement. As a result, the
binary gcd algorithm, which avoids regular division, runs faster than the Euclidean algorithm, even though it
does more (but simpler) steps. The binary GCD algorithm relies on three facts:
1. If both a and b are even, then gcd(a, b) = 2gcd(a/2, b/2).
2. If a is even and b is odd, then gcd(a, b) = gcd(a/2, b).
3. If a and b are both odd, and a ≥ b, then gcd(a, b) = gcd((a − b)/2, b).
23. To prove that if both a and b are even, then gcd(a, b) = 2gcd(a/2, b/2), let a and b be even integers. Then
2 is a common factor of both a and b, so 2 is a factor of gcd(a, b). Let 2c = gcd(a, b). Then
a = n(2c) and b = m(2c)
a/2 = nc and b/2 = mc
so c 0 a/2 and c 0 b/2. Finish this proof by showing that c = gcd(a/2, b/2).
24. To prove that if a is even and b is odd, then gcd(a, b) = gcd(a/2, b), note that because b is odd, 2 is not a
factor of b, hence not a factor of gcd(a, b). Therefore all contribution to gcd(a, b) comes from b and a/2,
and gcd(a, b) = gcd(a/2, b). Write an equation for gcd(a, b) when a is odd and b is even.
25. We want to prove that if a and b are both odd, and a ≥ b, then gcd(a, b) = gcd((a − b)/2, b). If a and
b are both odd and a ≥ b, then gcd(a, b) = gcd(a − b, b) because, from the regular Euclidean algorithm,
gcd(a, b) begins with a = qb + r, 0 ≤ r < b and gcd(a − b, b) begins with a – b = (q − 1)b + r, 0 ≤ r < b.
The next step in either case is to divide b by r, so the two final answers will be the same. Finish this proof
by showing that gcd(a − b, b) = gcd((a – b)/2, b).
Proofs, Induction, and Number Theory
d. ArraySumD (integers n, a[1], a[2], … , a[n])
Local variables:
integers i, j
i = 1
j = a[1]
while i ≤ n do
j = j + a[i + 1]
i = i + 1
end while
//j now has the value a[1] + a[2] + g+ a[n]
return j
end function ArraySumD
Exercises 23–28 concern a variation of the Euclidean algorithm more suited to computer implementation. The
original GCD algorithm relies on repeated integer divisions to compute remainders. The following variation,
called the binary GCD algorithm, also uses divisions, but only by 2, plus subtraction and testing for parity (oddness or evenness). Given that the numbers are stored in the computer in binary form, these operations are simple
and often done using built-in circuits. Testing for even/odd can be done using bitwise conjunction of N & 1,
which results in 1 if and only if N is odd. Given an even N, division by 2 is easily accomplished by a 1-bit right
shift operation, where all bits are shifted one place to the right (the rightmost bit disappears), and the leftmost
bit is set to 0. (Multiplication by 2 is a 1-bit left shift.) Subtraction involves the 2’s complement. As a result, the
binary gcd algorithm, which avoids regular division, runs faster than the Euclidean algorithm, even though it
does more (but simpler) steps. The binary GCD algorithm relies on three facts:
1. If both a and b are even, then gcd(a, b) = 2gcd(a/2, b/2).
2. If a is even and b is odd, then gcd(a, b) = gcd(a/2, b).
3. If a and b are both odd, and a ≥ b, then gcd(a, b) = gcd((a − b)/2, b).
23. To prove that if both a and b are even, then gcd(a, b) = 2gcd(a/2, b/2), let a and b be even integers. Then
2 is a common factor of both a and b, so 2 is a factor of gcd(a, b). Let 2c = gcd(a, b). Then
a = n(2c) and b = m(2c)
a/2 = nc and b/2 = mc
so c 0 a/2 and c 0 b/2. Finish this proof by showing that c = gcd(a/2, b/2).
24. To prove that if a is even and b is odd, then gcd(a, b) = gcd(a/2, b), note that because b is odd, 2 is not a
factor of b, hence not a factor of gcd(a, b). Therefore all contribution to gcd(a, b) comes from b and a/2,
and gcd(a, b) = gcd(a/2, b). Write an equation for gcd(a, b) when a is odd and b is even.
25. We want to prove that if a and b are both odd, and a ≥ b, then gcd(a, b) = gcd((a − b)/2, b). If a and
b are both odd and a ≥ b, then gcd(a, b) = gcd(a − b, b) because, from the regular Euclidean algorithm,
gcd(a, b) begins with a = qb + r, 0 ≤ r < b and gcd(a − b, b) begins with a – b = (q − 1)b + r, 0 ≤ r < b.
The next step in either case is to divide b by r, so the two final answers will be the same. Finish this proof
by showing that gcd(a − b, b) = gcd((a – b)/2, b).