Due:   By class time, Thursday, September 28.

Book Problems:

Section 4.2:  Problems: 2a-c, 4a-d, 26, 46. Section 4.3:  Problems 33c-d.
Section 4.4:  Problems 2, 4, 9, 12, 37.    Section 4.6:  24.
Section 5.1:  Problems 6, 7, 11, 16, 18, 32, 49, 51.

My Problems:

1. Prove by induction that  2ⁿ > n² for all integers n larger than 4.
   


2. Take any integer n > 1 and partition it in two parts each greater than zero.  For example 16 might be partitioned into 3 and 13.  Calculate the product of the two numbers, in this case 39.  Repeat this process with each of the two numbers, until you are down to 1, keeping track of the sum of all the products.  For example, if you start with 7, then you could get 3 and 4.  Three becomes 1 and 2.  Four becomes 2 and 2.  The two's all become 1 and 1.  This gives:  12 + 2 + 4 + 1 + 1 + 1 = 21.  Make a conjecture about the relationship of this sum to n.  Prove your conjecture by induction.
   


3. Prove that the square root of 3 is irrational using Aristotle/Hipassus’ techniques. Make sure to prove the appropriate lemma.


4. Compute by hand, the smallest positive integers x, y, u, v such that ax-by = bu-av = gcd(a,b) for each pair a, b below. Use the Euclidean algorithm and back tracking.  (i) 99, 101  (ii). 36, 42


5. Prime Numbers:  How many distinct divisors are there for p^a, where p is a prime? Prove your conjecture by induction on a.  How many distinct divisors are there for an arbitrary number m?   Hint: Factor m  into its prime factors so that m = p₁^a1p₂^a2…p_n^an ,  and prove your answer by induction on n, the number of distinct prime factors. Use the first part of this question as your base case.


6. Guess the number of different ways for n people to arrange themselves in a straight line, and prove your guess is correct by induction.


7. Euclid proved that there is an infinite number of primes by showing that if n is the highest prime, there is a number larger than n (one plus the product of all the primes through n)  that is either prime itself or has a prime factor greater than n. Find the smallest n for which Euclid’s proof does not provide an actual prime number. (You can write a program to find it if you like).

8. Guess a formula (or just look around the internet) for the sum below, and prove you are right by induction.

 1(2) + 2(3) + 3(4) + … + n(n+1)


9. In Stonehill-ball, you can score 11 points for a goal, and 7 for a near miss. Prove by induction that you can achieve any score greater than or equal to 60.  Hint: Try to add one point to your score by adding/subtracting multiples of a and b. We did this in class with 2 cent and 3 cent coins.     Extra Credit:  Prove that in general that if a and b are relatively prime, you can get any score greater than or equal to (a-1)(b-1) where a and b are the two point values (in our example a = 7 and b =11).

10. RSA encryption. Let p=13 and q=11. Calculate an appropriate public code, and private code for doing RSA encrypting.   Assuming that each character in a message is represented by its ASCII value (an assigned table of integers from 0 to 127, can be found in many texts), encode the message “Too much work!” by encoding each ASCII value one at a time.

11. If I want to send you something securely so that you know it came from me and I know that only you received it,  I can put it in a box and lock the box keeping the only key in my pocket.  When you receive the box, you add your own lock to it and send it back to me.  I then remove my lock and return the box once again to you, at which point you open your own lock to get at the contents.  Explain how to get this effect electronically using RSA. Recall that RSA can be used for encryption or authentication.  Also, note that locking a box is something anyone can do (public), and unlocking is something only someone with the key can do.
    

shai@stonehill.edu

http://www.stonehill.edu/compsci/shai.htm