Homework #7 - Due 11/16/05

1. Prove that if 3|n and 4|n, then 12|n

2. Prove that for all natural numbers n, n(n + 1) is an even number.

3. Let the sequence {fn} be defined for all n  ≥ 0 by
f 0 = 0, f 1 = 1,
and for n ≥ 2, fn = fn - 1 + fn - 2
(These are the Fibonacci numbers.)
Prove that for all n ≥ 0, f 0 + f 1  + ... + fn  = fn + 2 - 1.
Hint:  The Principle of Mathematical Induction gives an easy way to do this.

4. Recall that the nth pizza number P(n) is given by P(n) = (n2 + n + 2)/2.
Prove that the sum of the pizza numbers P(0) + P(1) + ... + P(k) is (n3 + 3n2 + 8n + 6)/6.

5. Use algorithm 5 to find 4777 (mod 25)

6. Prove that there do not exist integers x and y such that 3x2 - 2y2 = 2.
Hint:  There is a good modulus m, so that if you consider this equation
mod m, the proof just falls right out.

7. Find an inverse of 24, mod 55.  Then use this inverse to solve the
equation 24x ≡ 13 (mod 55).

8. Prove or disprove:  If a and b are relatively prime, and b and c are relatively prime,
then a and c are relatively prime.

9. Prove or disprove:  If a and b are relatively prime, and c and d are relatively prime,
then ac and bd are relatively prime.

10. Prove or disprove:  If a and b are relatively prime, and c and d are relatively prime,
then (b + ac) and (a + bd + acd) are relatively prime.

11. (Extra credit + 7):  Which positive integers are not expressible in the form x2 - y2,
for integers x and y?
You should show (a bunch of) work and a conjecture.  You do not need to prove
your conjecture.  But a proof would get you even more extra credit.  It's not beyond
your abilities at this point, but it may take a while to discover.