Homework 3

CS 280 - Spring 2002

Due: Friday, February 15

Part A

  1. You must explain your answer to get full credit.
    1. What is the last digit (i.e., the units digit) of 77777777?
    2. What is 77777777 mod 6?
       
  2. You must explain your answer to get full credit.
    1. What is 666666 mod 5?
    2. What is 765765 mod 8?

Part B

  1. Put the following functions in order of growth rate.  In other words, place f(n) before g(n) if f(n) is O(g(n)).
    log(log n))      n3+n      (log n)2      1+sin(n)      n log n      log n      2n      n
     
  2. You must explain your answer to get full credit.
    1. Find the gcd(11...11, 11...11) where the first number has 75 digits and the second has 165.
    2. Find the gcd(n3 - n2 + n -1, n3 - 1).

Part C

  1.  
    1. Show that 5 | (14499 + 21699).
    2. Show that 5 | (n5 + 4n) for any n.
       
  2. Show that 90 | 1711 + 16315.