Has to be done using Microsoft Equation 3.0 or Maple Software, where applicable. Randall Barnes did a great job on last week's assignment, would love to have him do this one. Need all type to be done...

SECTION 4.1
Sol: (2) (a) Yes, Since  7 1 15
(b) Yes, Since  7 0 42 .
(c) No
(d) No
(e) Yes, Since  7 9 5 . 
(f) Yes, Since  7 1 699 . 
Sol: (4)
Since the gcd is the smallest possible positive linear combination of and 2, we
must have that gcd( , 2) 2 since 2 1( 2) 1(a). If a is even, then so is 2,
thus 2 does dvide both and 2
a a
a a a a
a a

     
 so we must have that gcd( , 2) 2. But if is
odd then 2 cannot be a divisor of thus we must have that gcd( , 2) 1.
a a a
a a a
 
 
Sol: (6)
a. 22 9 (mod 13)
b. 100 9 (mod 13)
c. 1001 0 (mod 13)
d. 1 12 (mod 13)
e. 100 4 (mod 13)
f. 1000 1 (mod 13)



 
 
 

Sol: (12)
(mod ) for some integer . Since n|m we have that for
some integer . Thus we can make a substitution to get ( ) . This final
equaiton implies that (mod ).
a b m a b km m m tn
t a b kt n
a b n
    
 

Sol: (22)
Sol: (28)
 
   
 
   
2 22
33 3
22
2
From this problem,
1 1
1 2 ... 1
2 4
If 4 , then 4 for some integer k, so
1
1 0 mod n .
4
If is odd th
n n n n
n
n n k
n n
kn n
n
   
      
 


  
 
 
22
2 2
en -1 is even, so -1 2 for some integer m. Then
1
0 mod n .
4
If is even but not divisible by 4, then 2 for some odd integer l, and

n n m
n n
n m
n n l


 

 
   
 
22
22 2 2 2 2 2
2
1
1 2 mod ,
4
and since l is odd and is even, so 0 mod .
n n
l n l n l n l l n
n l n

     

Sol: (30)
1
For the base case, 4 1+3 (mod 9). For the induction hypothesis, assume that 4 1 3
(mod 9) for some positive integer . Then
4 4 4 4(1 3 ) 4 12 4 3 1 3( 1) (mod 9).
Th
n
n n
n
n
n n n n
  
          
erefore 4 1 3 (mod 9) for all positive integers .n n n 

SECTION 4.2
Sol: (2) (a)
Note that the solutions to 3 7 2 are given by ( , ) (3 7 ,-1, 3 ). Therefore
if 3 2 (mod 7) then 3 7 for some integer , that is 3 (mod7).
x y x y t t
x x t t x
   
   

(b)
Since (6, 9) = 3, there are 3 incongruent solutions. It's easy to see that 2 (mod 9)
is one solution. Then since 9/3 = 3, the other solutions are 2 3 5 (mod 9) and
2 6 8 (mod 9).
x
x
x

  
  

(c)
Since (17, 21) = 1, there is a unique solution modulo 21. Using the Euclidean Algorithm
we find that 17(5) - 21(4) 1, so multiplying by 14, we have 17(70) - 21(56) 14. Therefore
the unique solution is 70x
 
  7 (mod 21).

(d)
Note that 15 25 9 has no integer solution. Therefore 15 9(mod 25) has no
solution.
x y x  

(e)
We check that (128, 1001) 1 833, so that there is exactly one solution. Solving the
diophantine equation 128 1001 833 gives us 812 (mod 1001) :x y x

  
(f)
We check that (987, 1597) 1 610. Solving the diophantine equation 987 1597
610 gives us 1596 (mod 1597) :
x y
x
  

Sol: (4) (a)
1 1 1Since is the least positive residue of m modulo , we have -[ ] . Then
( -[ ] ) -[ ] -[ ] (mod ) as desired.
a a a m m a a a x
m m a a x m a ax m a b m

  
(b)
1
Given that a sequence of decreasing positive integers, must have a least element, .
Now we can reduce modulo and get an which is smaller than . But is
the least positive element of th
n
n n n n
a
m a a a a
 
     
1
1 1
1
e sequence, so = 0, which is to say .
However, since = , we have that a common divisor of and also
divides . Since , = 1, then we have , = 1,. By induction, , = 1,
but we pr
n n
n
a a m
a m m a a m a
a a m a m a m


oved , therefore, 1.n na m a 
(c)
   
   
 
1
2
3
We have =23 23 6 6 23 3 6 5. Then the new congruence is 5 7 3 2 mod 23
Then =23 23 5 5 23 4 5 3, and the next congruence is 3 2 4 15 mod 23 :
Then =23 23 3 3 23 7 3 2, and the next congruence is 2 15 7
a x
a x
a x
        
        
         
   4
10 mod 23 .
Then =23 23 2 2 23 11 2 1, and the final congruence is 10 11 5 mod 23 .a x

        
Sol: (8)
(a) Note 2·7 1 (mod 13), so inverse of 2 is 7.
(b) Note 3·4 -1 (mod 13), so -4 is the inverse of 3 modulo 13.
(c) Note that 5·5 -1 (mod 13), so -5 is the inverse of 5 modulo 13.
(d) Note that 11 -2 (mo



 d 13), and we already know that 7 is the inverse of -2. Therefore
-7 is the inverse of 11 modulo 13.
Sol: (10)
(a). As is shown in a later homework, the integers that have an inverse are precisely those
integers that are relatively prime to 14. They are {1, 3, 5, 9, 11, 13}.
(b). (i) 1 is its own inverse.
(ii) 3 and 5 are inverses.
(iii) 9 and 11 are inverses.
(iv) 13 is its own inverse

Sol: (14) (a)
we see that (2, 3, 7) = 1 and 1 1, so there are 1 7 solutions. We get them by letting
take on the values 0, 1, 2, 3, 4, 5, and 6, and solving the congruence for . We get,
respectively, = 5, 2, 6,
x y
y

3, 0, 4, and 1, modulo 7.
Sol: (14) (b)
We have (2, 4, 8) 2 and 2 6 so there are 2 8 = 16 incongruent solutions modulo 8.
If is even, the congruence reduces to 2 6 (mod 8) which has solutions 3 7
(mod 8). This gives us the 8 solu
y x x or
 
 
tions: (3, 0), (3, 2), (3, 4), (3, 6), (7, 0), (7, 2), (7, 4),
and (7, 6). If is odd, the congruence reduces to 2 2 (mod 8) which has...