Math. 55 EXAM. Model Solutions Prof. W. Kahan Wed. 3 March. 1999 This 35 minute exam, to be administered in your discussion section, can be answered with the aid of any texts, notes and calculating instruments. Answers may be worked out on scratch paper but must be entered on this sheet in the spaces provided. Each correct answer earns one point; each incorrect answer loses one point; space left blank loses nothing, so DON’T JUST GUESS. And check your work. Finally hand this sheet and all your used scratch paper to the Teaching Assistant, who will return the scored sheet some time later. Your score will affect your final grade. You must not discuss this exam’s questions with anyone else until tomorrow. 1. “John hunts no birds or snakes.” _ ( ¬ b ) ∨ s , or b → s _.“John hunts no birds nor snakes.” _ ¬ (b ∨ s) , or ( ¬ b ) ^ ( ¬ s ) _.Assuming that these sentences have different meanings, explain them by filling in the blanks that follow them with expressions using logical operators like ¬ , ^ , ∨ , … and the two propositionsb := “John hunts birds.” s := “John hunts snakes.” 2. Wilson’s Theorem says “ If n is a prime then (n–1) ! ≡ –1 mod n .” State this theorem’sconverse: _ If (n–1) ! ≡ –1 mod n then n is a prime. _Is the converse of Wilson’s Theorem true? (YES or NO) _ YES _. ( Except if n ≤ 1 .)( If n > 1 is not prime, GCD(n, (n–1) ! ) is a product of prime factors of n , not 1 .) 3. Find the smallest (in magnitude) difference between different solutions x of all threecongruences { 3x ≡ 2 mod 5 , x ≡ 2 mod 6 , and 2x ≡ 3 mod 7 } : _ 210 , = 5·6·7 _. 4. The following algorithm is proposed to find factors of any given huge odd integer n :For k = , +1 , +2 , … in turn test whether m := √ ( k 2 – n ) is aninteger, in which case stop and exhibit n = ( k – m )·( k + m ) .Must this algorithm stop? ( YES or NO ) _ YES _.( This is Fermat’s algorithm; it has to stop for k ≤ (n+1)/2 .) 5. If a finite string of bits is the one’s complement representation of integer x andalso the two’s complement representation of integer y ≠ x , what is x – y ? _ +1 _. ( If x and y were positive they’d be equal; instead n-bit unsigned 2 n –1 + x = 2 n + y .) 6. Among all pairs (x, y) of integers that satisfy 93x + 20y = 1find the minimum of |x – y| : _ 17 _.( x = -3 and y = 14 .) 7. Solve mod 11 for x mod 11 = _ 4 _. ( And y mod 11 = 8 .)The maximum score on this test is 9 points.nn n3725xy24≡ This document was created with FrameMaker404Math. 55 EXAM. Model Solutions Prof. W. Kahan Wed. 3 March. 1999 This 35 minute exam, to be administered in your discussion section, can be answered with the aid of any texts, notes and calculating instruments. Answers may be worked out on scratch paper but must be entered on this sheet in the spaces provided. Each correct answer earns one point; each incorrect answer loses one point; space left blank loses nothing, so DON’T JUST GUESS. And check your work. Finally hand this sheet and all your used scratch paper to the Teaching Assistant, who will give back the scored sheet some time later. Your score will affect your final grade. You must not discuss this exam’s questions with anyone else until tomorrow. 1. Wilson’s Theorem says “ If n is a prime then (n–1) ! ≡ –1 mod n .” State this theorem’sconverse: _ If (n–1) ! ≡ –1 mod n then n is a prime. _Is the converse of Wilson’s Theorem true? (YES or NO) _ YES _. ( Except if n ≤ 1 .)( If n > 1 is not prime, GCD(n, (n–1) ! ) is a product of prime factors of n , not 1 .) 2. “John hunts no birds nor snakes.” _ ¬ (b ∨ s) , or ( ¬ b ) ^ ( ¬ s ) _.“John hunts no birds or snakes.” _ ( ¬ b ) ∨ s , or b → s _.Assuming that these sentences have different meanings, explain them by filling in the blanks that follow them with expressions using logical operators like ¬ , ^ , ∨ , … and the two propositionsb := “John hunts birds.” s := “John hunts snakes.” 3. If a finite string of bits is the one’s complement representation of integer x andalso the two’s complement representation of integer y ≠ x , what is y – x ? _ –1 _. ( If x and y were positive they’d be equal; instead n-bit unsigned 2 n –1 + x = 2 n + y .) 4. Among all pairs (x, y) of integers that satisfy 93x + 20y = 1find the minimum of |x + y| : _ 11 _.( x = -3 and y = 14 .) 5. Find the smallest (in magnitude) difference between different solutions x of all threecongruences { 4x ≡ 3 mod 5 , x ≡ 1 mod 6 , and 3x ≡ 5 mod 7 } : _ 210 , = 5·6·7 _.6. The following algorithm is proposed to find factors of any given huge odd integer n :For k = , +1 , +2 , … in turn test whether m := √(k2 – n) is aninteger, in which case stop and exhibit n = (k–m)·(k+m) .May this algorithm fail to stop? ( YES or NO ) _ NO _.( This is Fermat’s algorithm; it has to stop for k ≤ (n+1)/2 .)7. Solve mod 11 for y mod 11 = _ 8 _. ( And x mod 11 = 4 .)The maximum score on this test is 9 points.n n n3725xy24≡Math. 55 EXAM. Model SolutionsProf. W. Kahan Wed. 3 March. 1999Oops! I blundered in the problem about Wilson’s Theorem and its converse by taking for granted that the Universe of Discourse was obviously integers n > 1 . This should have been stated explicitly; the problem should have been worded “ For integers n > 1 Wilson’s Theorem says … .” In that Universe of Discourse, the converse of Wilson’s Theorem is true. In a larger Universe of Discourse