Math 3110 Fall 2011 -- Homework Problem Set #2

Due: Wednesday, September 21^st

Computing Modulo \( n \)

1. For each of the following pairs of integers: \(a,b \in \mathbb{Z}\), use the Euclidean algorithm to find \(\mathrm{gcd}(a,b)=d\) and then "running the algorithm backwards" find \( x,y \in \mathbb{Z}\) such that \(ax+by=d\).
   
   
   • \( a=45 \) and \( b=888 \)
     
     
   • \( a=25 \) and \( b=222 \)
     
     
   • \( a=23 \) and \( b=123 \)
     
     
   • \( a=112 \) and \( b=12345 \)
     
     
2. Explain why \( 45^{-1} \) does not exist when working mod 888. Then for all of the following elements \( a \in \mathbb{Z}_b \), find \( a^{-1} \).
   
   
   • Find \( 25^{-1} \) in \( \mathbb{Z}_{222} \).
     
     
   • Find \( 23^{-1} \) in \( \mathbb{Z}_{123} \).
     
     
   • Find \( 112^{-1} \) in \( \mathbb{Z}_{12345} \).
     
     
3. Write addition and multiplication tables for \( \mathbb{Z}_8 \). Find the additive inverse of each element (i.e. for each \( x \in \mathbb{Z}_8 \), find \( -x \)). Also, which elements have multiplicative inverses? If \( x^{-1} \) exists, find it.
   
   
4. List the elements of \( U(9) \) and then write down its Cayley table. Then list each of the elements paired with their inverses (i.e. \(1^{-1}=1 \), etc.)
   
   
5. Consider the matrix \( A=\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \). Why does \( A^{-1} \) fail to exist in \( \mathrm{GL}_2(\mathbb{Z}) \)? Also, find \( A^{-1} \) in \( \mathrm{GL}_2(S) \) when \( S= \mathbb{R}, \mathbb{Z}_5, \mathbb{Z}_9, \) and \(\mathbb{Z}_{25} \).