Due: Monday, October 2.

Book Problems:

Section 4.2: Problems: 2a-c,
4a-d, 26, 40. 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:

- Prove by induction that
^{n}>n^{2}for all integers n larger than 4.

- Take any integer n,
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.

- Prove that the square root of 3 is irrational using Aristotle/Hipassus’ techniques. Make sure to prove the appropriate lemma.
- 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 - Prime Numbers: How many distinct divisors are there for
*p*, where^{a}*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*, and prove your answer by induction on_{1}^{a1}p_{2}^{a2}…p_{n}^{an }*n*, the number of distinct prime factors. Use the first part of this question as your base case. - 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. - 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 authorization.

- Guess the number of different ways for
*n*people to arrange themselves in a straight line, and prove your guess is correct by induction. - Euclid proved that there is an infinite number of primes, by
assuming that
*n*is the highest prime, and exhibiting a number that he proved must either be prime itself, or else have 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). - 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.
**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).

- 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)