Math questions:
1. Wilson's Theorem says " If n is a prime then (n-1)! =-1 mod n ." State this theorem's converse: 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 s 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." -(bvs), or (-b )(-s ) _ "John hunts no birds or snakes." (-b) vs, 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 -, A , v, ... and the two propositions b:= "John hunts birds." s := "John hunts snakes." 3. If a finite string of bits is the one's complement representation of integer x and also 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"-1 + x = 2" + y .) 4. Among all pairs (x, y) of integers that satisfy 93x + 20y = 1 find the minimum of (x + yl : 11 ( x = -3 and y = 14 .) 5. Find the smallest (in magnitude) difference between different solutions x of all three congruences { 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= [vn] , [wal+1, [wm1+2 . ... in turn test whether m := V(k- -n) is an integer, 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 ks (n+1)/2 .) 7. Solve or y mod 11 ( And x mod 11 = 4 .)1. "John hunts no birds or snakes." - (-b)vs, or b-> s "John hunts no birds nor snakes." -(b vs), 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 -, A, v . ... and the two propositions b:= "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's converse: 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 s 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 three congruences { 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= [vn] . [ml+1 , [/m /+2 . ... in turn test whether m := V(k- -n) is an integer, 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 S (n+1)/2.) 5. If a finite string of bits is the one's complement representation of integer x and also 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"-1 + x = 2" + y .) 6. Among all pairs (x, y) of integers that satisfy 93x + 20y = 1 find the minimum of (x - yl : 17 ( x = -3 and y = 14.) 7. Solve :3 - mod Il for xmod ll =_ 4 - ( And y mod 11 = 8 .)
