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, f ₁ = 1,
   and for n ≥ 2, f_n = f_{n - 1} + f_{n - 2}. 
   (These are the Fibonacci numbers.) 
   Prove that for all n ≥ 0, f ₀ + f ₁  + ... + f_n  = f_{n + 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) = (n² + n + 2)/2.  
   Prove that the sum of the pizza numbers P(0) + P(1) + ... + P(k) is (n³ + 3n² + 8n + 6)/6.
   
   
5. Use algorithm 5 to find 4⁷⁷⁷ (mod 25)
   
   
6. Prove that there do not exist integers x and y such that 3x² - 2y² = 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 x² - y²,
    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.