CS 2104 OOC 4 Summer 2014
-------------------------------------------------------------------------------

1.  Since 7 and 15 are relatively prime, we know there is a solution.  Applying
    the techniques from class:

       7x + 15y = 1 implies (7x + 15y) mod 15 = 1 mod 15
                         or  7x mod 15 = 1

    So, we are looking for a multiple of 7 (because of the 7x) that leaves a
    remainder of 1 when we divide by 15.  Listing multiples of 7, we find the
    smallest one that works is 91 (7 * 13).

    So, the smallest positive value of x that works is 13.

    Then subsituting in to the original equation gives us:  7*13 + 15y = 1.
    This implies that y must be -6.

    So, the desired solution is x = 13, y = -6.

2.  In this case, 56 and -21 are NOT relatively prime; their GCD is 7.  Dividing
    through the equation by 7 yields

                      8x - 3y = 7

    Since 8 and -3 ARE relatively prime, this has a solution.  Proceeding as
    before, 

             8x - 3y = 7 implies (8x - 3y) mod 3 = 7 mod 3
                              or  8x mod 3 = 1

    Therefore, we need a multiple of 8 that leaves a remainder of 1 when divided
    by 3.  The smallest positive such multiple is 16, so x must be 2.  Again,
    substituting into the equation, we see that y must be 3.

    So, the desired solution is x = 2, y = 3.

3.  We want an integer, A, that's a perfect square and perfect cube and perfect
    fifth power.  In other words, there must be (different) integers X, Y and Z
    such that
                 A = X^2 = Y^3 = Z^5

    Now, if Y^3 = Z^5, then Z = Y^(3/5) and the only way that Y^(3/5) can be an
    integer is if Y is a perfect fifth power.  So, Y = B^5 for some integer B.
    Therefore, Y^3 = B^15.

    Similarly, if X^2 = Y^3, then X^2 = B^15 and so X = B^(15/2).  But,
    B^(15/2) = B^7 * B^(1/2) and that can only be an integer if B is a perfect
    square.  So, there's some integer C such that B = C^2.

    Putting all that together, we have that

                  A = X^2 = B^15 = C^30

    So, A must be a thirtieth power of an integer and the smallest value that
    works (since A > 1) would be 2^30.

    So, A = 1,073,741,824.

4.  Let H be the number of half dollars, F be the number of $5 dollar bills, and
    T be the number of $10 bills.  Then we have two equations:

               H +    F +     T =   100
             50H + 500F + 1000T = 10000     (value in cents)

    Subtracting 50 times the first equation from the second equation eliminates
    the variabile H and gives us

                    450F + 950T = 5000

    Dividing through by 50 (the GCD of 450 and 950) yields the equation

                      9F + 19T = 100

    So, 9F mod 19 = 100 mod 19 = 5, and we want a multiple of 9 that leaves a
    remainder of 5 when divided by 19; the smallest that works is 81, so F must
    be 9.  Substituting into the last equation above gives us T = 1.  And then
    subsituting into the original first equation gives us that H = 90.

    So the bag must hold 90 half dollars (worth $45), 9 $5 bills (also worth
    $45), and 1 $10 bill, making a total of $100 in value and 100 pieces of
    currency.

5.  Suppose the statement is false.  In other words, suppose there are two
    integers K and L, such that 0 <= L < K <= N - 1 and

          (L^2 + L)/2 mod N = (K^2 + K)/2 mod N

    Now, this implies that (K^2 + K)/2 - (L^2 + L)/2 = Nq for some integer q.

    A little algebra shows that this implies

         (K^2 - L^2) + (K - L) = 2Nq
    or
         (K - L)(K + L + 1) = 2Nq

    No matter what K and L are, K - L and K + L are either both even or both odd,
    and therefore one of K - L and K + L + 1 must be even and one of them must
    be odd.

    Now, N = 2^r for some integer r, and 2 is prime.  Since we have that 

         (K - L)(K + L + 1) = 2Nq = 2q * 2^r = q * 2^(r + 1_

    2^(r + 1) must divide either K - L or K + L + 1, whichever is even.

    But from the bounds on L and K:

         K - L <= N - 1 = 2^r - 1
    and
         K + L + 1 <= N - 1 + N - 2 + 1 = 2N - 2 < 2^(r + 1).

    So, 2^(r + 1) cannot divide either of them.

    So, by contradiction, the statement must be true.