Math 580
Exam #1

  1. (a). Using the Euclidean Algorithm, find the greatest common divisor of 391 and 323.

          391 = 323*1 + 68
          323 = 68*4 + 51
          68 = 51*1 + 17
          51 = 17*3 + 0

          So gcd(391, 323) = 17.


    (b). Using your answer to (a), express d = gcd(391, 323) as a integral linear
    combination of 391 and 323.

          Working backwards gives: 17 = -6*323 + 5*391


  2. (a).Find an expression for all the integral solutions to the equation 9x + 6y = 18.

          x = ___________________ y = _________________


    Since gcd(9, 6)=3, and one solution to the equation is x=2, y=0 it follows that all solutions are given by the equations:
    x=2 + 2t, y = -3t for any integer t.



    (b).The equation 10x + 25y = 22 does not have any integral solutions.
          How do you know this?

          gcd(10, 25) = 5 and 5 does not divide 22.


  3. Determine the remainder when is divided by 9. Show your work.

    and so . Now raising both sides to the 17 power gives . Hence, . But and so the reaminder is 7.

    Several people determined that . This is correct, but the remainder of any number divided by 9 must be and integer between 0 and 8 inclusive.

  4. Let and then

    (a). gcd(n, m) =       (b). lcm(n, m) =


    (c). The number of divisors of n is _______________
         


    (d). How many divisors of m are multiples of 20? ___________

         

  5. Prove by induction: If , then for any n >= 1,

    For n = 1 this just says that which is given to be true.
    Now suppose that for some integer k >= 1, we know that .
    But since we know that multiplying corresponding sides of two conguences yields another congruence, multiplying by gives or equivalently, . Thus the result holds for k+1 and the result follows by induction.

  6. Prove: If p is a prime larger than 3, then is of the form 6k + 1.
    Since p is a prime, it must be of the form 6k+1 ro 6k+5 (any other of the possible forms 6k, 6k+2, 6k+3 or 6k+4 are divisible by either 2 or 3).
    But if p = 6a+1, for some integer a, then which is of the form 6k+1.
    On the other hand if p = 6a + 5 for some intger a, then . Which is also of the form 6k+1.

  7. Show that for any integer n >= 2, is composite
    (Hint: Factor this expression. It does not have linear factors.).
    Explain where the condition n >= 2 is used.

    Proceeding along the lines of examples done in class, it is not too hard to arrive at the factorization . And if n >= 2, then each of these factors is an integer larger than 1.


  8. Prove: If a and b are relatively prime and a | bc, then a | c.

    Proof: Since a and b are relatively prime, there exist integers x and y such that .
    But then multiplying both sides of this equation by c gives, . However a certainly divides cax and since a divides bc it also divides cby. Thus a divides the sum of the sum of these two numbers i.e., a divides . But this sum equals c and so a divides c.