211L2Solutions
Exercises
1. Let n be an integer such that n != 0 and n != 1. Prove that the smallest positive factor m > 1 of n is a prime number.
In order to prove the theorem, we analyze the following algorithm. The analysis of the algorithm will give us a proof of the theorem. Input for the algorithm are integers n > 1, and s, m, k are integer variables.
1. Initialize s = n.
2. Find the smallest factor m > 1 of s and write s = m · k. Output m.
3. If s = m then stop. Otherwise, set s to be equal to k, and go to line 2 above.
Consider how the value of s changes each time when line 2 of the algorithm is executed. The first time, when line 2 is executed, the value of s is n. Any other time when line 2 is called for the current value of s is smaller than the previous of value of s. Therefore line 2 can’t be called more than n times. Therefore, after line 2 is called for the last time, the algorithm outputs the last value of m, and stops as instructed in line 3. Let t be the number of times line 2 of the algorithm is called. As we noted t � n. Every time when line 2 is called the algorithm outputs a positive integer. Thus, the algorithm outputs exactly t positive integers. Let us denote them by m1, m2, . . ., mt. After each call of line 2, the value of s changes in line 3 (unless s = m). So lets denote all these values s takes by k1, k2, . . ., kt−1. Thus, n = m1 · k1 in case n > m1 Now note that mi+1 is the smallest factor of ki. Therefore mi must be a prime number. Since ki = mi+1 · ki+1 for all i = 1, 2, . . . , t − 1, we have the following equalities:
n = m1 · k1, n = m1 · m2 · k2, . . . , n = m1 · m2 · . . . · mt−1 · mt.
Thus, we have written n as a product of prime numbers. This proves the theorem.
2. Consider FindFactors(n) algorithm.
(a) Run the algorithm on numbers 64, 120 and 1008.
- The factors of 64 are: itself and 1 2 4 8 16 32
- The factors of 120 are: itself and 1 2 3 4 5 6 8 10 12 15 20 24 30 40 60
- The factors of 1008 are: itself and 1 2 3 4 6 7 8 9 12 14 16 18 21 24 28 36 42 48 56 63 72 84 112 126 144 168 252 336 504
(b) For a positive integer n, its length is the number of digits needed to describe it. For example the lengths of numbers 1, 9, 26, 100 and 102312 are 1, 1, 2, 3, and 6, respectively. If it takes one unit of a time to execute each of lines 2 and 3 of the FindFactors algorithm, how much time (in terms of time units) is needed to run the algorithm on inputs of length t? Discuss if this algorithm is efficient in terms of time.
The time taken would be 2x10^t. This algorithm isn't efficient in terms of the time taken because the amount of wasted calculations (where i is greater than half the original value), increases exponentially.
3. Without references to the Euclidean algorithm prove that gcd(n,m) always exists.
Every number can be divided by one. Therefore, at the very least, there is always a g.c.d. of one.
4. Find gcd(n,m) for the following pairs of integers: 24 and 32; 44 and 56; 99 and 18; 299 and 247; and 242 and 44.
- The GCD of 24 & 32 is: 24
- The GCD of 44 & 56 is: 44
- The GCD of 99 & 18 is: 18
- The GCD of 299 & 247 is: 247
- The GCD of 242 & 44 is: 44
5. For each of the pairs n and m in the previous exercise find s and t such that gcd(n,m) = s · a1 + t · b1.
- 24 = 3*2 + 3*6
- 44 = 10*2 + 12*2
- 18 = 3*3 + 9*1
- 247 = 100*2 + 47*1
- 44 = 10*2 + 12*2
6. Consider the Euclidean algorithm. For inputs n and m the size of the input is the maximum of the sizes of n and m. If it takes one unit of a time to execute lines 3 and 4 of the algorithm, how much time (in terms of time units) is needed to run the algorithm on inputs of length t? Discuss if this algorithm is efficient in terms of time.
7. Prove that gcd(n,m) · lcm(n,m) = n · m for all positive integers n and m.
8. Let p0, . . ., pn be the first n + 1 prime numbers listed in increasing order. Prove that p0 · . . . · pn + 1 can not be written as a product of prime numbers p0, . . ., pn (Hint: Use the proof by contradiction method). Conclude that there is a prime number distinct from all the first n + 1 prime numbers p0, . . . , pn.
9. Write down all the congruences classes modulo 5 and modulo 7.
- 5 = ¯0, ¯1, ¯2, ¯3, ¯4
- 0 = {0,5,10,15...}
- 1 = {1,6,11,16...}
- 2 = {2,7,12,17...}
- 3 = {3,8,13,18...}
- 4 = {4,9,14,19...}
- 7 = ¯0, ¯1, ¯2, ¯3, ¯4, ¯5, ¯6
- 0 = {0,7,14,21...}
- 1 = {1,8,15,22...}
- 2 = {2,9,16,23...}
- 3 = {3,10,17,24...}
- 4 = {4,11,18,25...}
- 5 = {5,12,19,26...}
- 6 = {6,13,20,27...}
10. Consider a positive integer p. Prove each of the following:
(a) For all integers n, n is congruent to n modulo p.
n modulo p can be thought of as a remainder and will always be less than the value of n. As such n modulo p will always be a congruent of n.
(b) For all integers n and m, if n is congruent to m modulo p, then m is congruent to n modulo p.
If n is in the the remainder when m is divided by p, m will be in the same congruent class as n modulo p because m will be made up of a multiple of p plus n.
(c) For all integers n, m, and k, if n is congruent to m modulo p, and m is congruent to k modulo p, then n is congruent to k modulo p.
11. Write down the addition table for congruence classes ¯0, ¯1, ¯2, ¯3, ¯4, that is the addition rule modulo 5.
x 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3
12. Let n m and n0, m0 be integers such that n is congruent to n0 modulo p and m is congruent to m0 modulo p. Prove that n · m is congruent to n0 · m0 modulo p.
13. Write down the multiplication table for congruence classes ¯0, ¯1, ¯2, ¯3, ¯4, and ¯5, that is the multiplication rule modulo 6.
x 0 1 2 3 4 5 0 0 0 0 0 0 0 1 0 1 2 3 4 5 2 0 2 4 0 2 4 3 0 3 0 3 0 3 4 0 4 2 0 4 2 5 0 5 4 3 2 1
14. Consider the congruence classes ¯0, ¯1, ¯2, ¯3, ¯4 modulo 5. Solve the following equations:
- (a) ¯2 + ¯x =¯0 .
- 3
- (b) ¯3 + ¯x = ¯1.
- 3
- (c) ¯3 + ¯x = ¯4.
- 1
- (d) ¯2 · ¯x =¯0
- 0
- (e) ¯3 · ¯x = ¯1.
- 2
- (f) ¯3 · ¯x = ¯4.
- 3
Programming Exercises
1. Implement the FindFactors algorithm.
- Done
2. Implement the Euclidean algorithm.
- Done
3. Write a program that on input n, m, p, where n, m, p are integers and p > 0, outputs yes if n and m are congruent modulo p and outputs no otherwise.
- Done