Math 3110 Spring 2010 -- Homework Problem Set #3

Due: Friday, February 19th
  1. Let \( a,b \in \mathbb{Z} \). Prove that if \( \quad a \Big| b \quad \) and \( \quad b \Big| a \quad \) (that is \( a \) divides \( b \) and \( b \) divides \( a \)), then \( a = \pm b \).

  2. Suppose that \( a,b,x,y \in \mathbb{Z} \)
    1. Suppose \( ax+by=4 \). What are the possible value(s) of \( (a,b) \)?
    2. Now suppose \( ax+by=5 \) and \( (a,b)=5 \). What are the possible value(s) of \( (x,y) \)?

  3. Let \( d = (a,b) \) and suppose that \( a \Big| c \) and \( b \Big| c \). Show that \( ab \Big| cd \).

  4. Use the Euclidean algorithm to find the GCD of each of the following pairs of integers. Then run the algorithm "backwards" to express the GCD as a linear combination of the pair of integers.
    1. 482 and 74
    2. 147 and 64

  5. Equations mod \( n \).
    1. Does \( 3x \equiv 1 \; \mbox{mod} \; 80 \) have a solution? If not, explain why no solution exists. If so, find a solution between 0 and 80.
    2. Does \( [3]x = [1] \) have a solution if we are working in \( \mathbb{Z}_{99} \)? If not, explain why no solution exists. If so, find a solution.