Use the sieve of Eratosthenes to find all primes less than 200. Exercise # 8) (This exercise constructs another proof of the infinitude of primes.) Show that the integer Qn = n !+ 1, where n is a...

SECTION 3.1
Sol: (4) Find all the primes less than 200,
Sol: (8)
Fix an integer 1, and suppose that all primes satisfy . Let ! 1.
Then 1, so it has some prime divisor , and hence | !. But then
| ( !) 1, which is a contradiction. So there
n
n
n
n p p n Q n
Q q n q n
q Q n
   
 
  must be a prime larger than .
Since was arbitrary, there are infinitely many primes
n
n
Sol: (16) (a) Given that
5, 1a b 
for 1, 1 5 6( 2 divides 6 hence it is not a prime)
for 2, 1 2(5) 1 10 11( a prime)
Hence the smallest prime in the arithmetic progression
where 1 and 5 is 11.
n b an
n b an
b an b a
    
      
  

Sol: (3) (b) Given that
7, 2a b 
for 1, 2 7 12( 2 divides 12 hence it is not a prime)
for 2, 2 2(7) 2 14 16 ( 2 divides 16 hence it is not a prime)
for 3, 2 3(7) 2 21 23 ( it is a prime)
Hence the smallest prime in
n b an
n b an
n b an
    
      
      
the arithmetic progression
where 2 and 7 is 23.b an b a  

Sol: (3) (c) Given that
23, 13,a b 
for 1, 13 23 36( 2 divides 36 hence it is not a prime)
for 2, 13 2(23) 13 46 59( a prime)
Hence the smallest prime in the arithmetic progression
where 13 and 23 is 59.
n b an
n b an
b an b a
    
      
  

SECTION 3.2
Sol: (4) (5, 7, 11), (11, 13, 17), (17, 19, 23), and (41, 43, 47).
Sol: (6) (a) The smallest prime between and 2 for these values of 3 i.e.n n n 
between 3 and 6 is 5.
Sol: (6) (b) The smallest prime between and 2 for these values of 5 i.e.n n n 
between 5 and 10 is 7.
Sol: (6) (c) The smallest prime between and 2 for these values of 19 i.e.n n n 
between 19 and 38 is 23.
Sol: (6) (d)The smallest prime between and 2 for these values of 31 i.e.n n n 
between 31 and 62 is 37.
Sol: (12) (a) 50 3 47 7 43 13 37 19 31       
Sol: (12) (b) 98 19 79 31 67 37 61     
Sol: (12) (c)
102 5 97 13 89 19 83 23 79 29 73 31 71 41 61 43 59               
Sol: (12) (d)
144 5 139 7 137 13 131 17 127 31 113 37 107 41 103
43 101 47 97 61 83 71 73
              
      
Sol: (12) (e)
200 3 197 7 193 19 181 37 163 43 157 61 139 73 127
97 103
              

Sol: (12) (f)
222 11 211 23 199 29 193 31 191 41 181 43 179 59 163
71 151 73 149 83 139 109 113
              
      
SECTION 3.3
Sol: (2) (a) For 5; 15, we get the following list of Euclidean divisions:a b 
 15 5.3 0 3, 0q r   
The last non-zero remainder, 5, is the gcd of 5 and 15.
Sol: (2) (b)For 0; 100, we get the following list of Euclidean divisions:a b 
This is invalid numbers.
Sol: (2) (c)
For 27; 45, we get the following list of Euclidean divisions:a b   
 
 
 
 
45 27.1 18 1, 18
27 18.1 9 1, 9
18 9.1 9 1, 9
9 9.1 0 1, 0
q r
q r
q r
q r
      
      
      
     

The last non-zero remainder, 9, is the gcd of 27 and 45.  
Sol: (2) (d)
For 90; 100, we get the following list of Euclidean divisions:a b  

 
 
100 90.1 10 1, 10
90 10.9 0 9, 0
q r
q r
     
     

The last non-zero remainder, 10, is the gcd of 90 and 100. 
Sol: (2) (e)
For 100; 121, we get the following list of Euclidean divisions:a b 
 
 
 
 
 
121 100.1 21 1, 21
100 21.4 16 4, 16
21 16.1 5 1, 5
16 5.3 1 3, 1
1 1.1 0 1, 0
q r
q r
q r
q r
q r
   
   
   
   
   

The last non-zero remainder, 1 , is the gcd of 100 and 121.
Sol: (2) (f)
For 1001; 289, we get the following list of Euclidean divisions:a b 
 
 
 
 
 
 
 
 
1001 289.3 134 3, 134
289 134.2 21 2, 21
134 21.6 8 6, 8
21 8.2 5 2, 5
8 5.1 3 1, 3
5 3.1 2 1, 2
3 2.1 1 1, 1
2 1.2 0 2, 0
q r
q r
q r
q r
q r
q r
q r
q r
   
   
   
   
   
   
...