Use mathematical induction to prove that the algorithm you devised in Exercise 47 produces an optimal solution, that is, that it uses the fewest towers possible to provide cellular service to all buildings.

Lecture 13 Wednesday, October 26, 2016 10:34 AM Modular Inverse, exponentiation Recall: - Bezout's theorem:If a and b are positive integer, then there exist integers s and t such that gcd(a, b) = sa + tb. A. Multiplicative inverse mod m - Suppose GCD(a, m) = 1 - By Bezout's Theorem,there existsintegers s and t such that sa+tm=1. - S mod m is the multiplicative inverse of a: 1 = (sa + tm) mod m = sa mod m. - Gcd(a, m) = 1 if m is prime and 0 < a < m so can always solve these equations mod a prime. B. Fast Exponentiation a^k mod m for all k.