CSE191 Assignment 7 Answer Key Fall 2013
(1)(b) c = 8b mod 19, where b = 3 mod 19: c = 24 = 5 mod 19.
(c) c = a - b mod 19 where a = 11 mod 19 and b = 3 mod 19: c = 8 mod 19.
(d) c = 2a^2 + 3b^2 mod 19 with a,b as above. "Lazy": c = 2*11^2 + 3*3^2
= 242+27 = 269 mod 19, well 269 = 14*19 + 3 = 3 mod 19.
"Eager": Reduce a^2 = 121 = 6*19 + 7 = 7 mod 19 first, and 3*3^2 = 27
= 8 mod 19. Get 2*7 + 8 = 22 = 3 mod 19, as a useful check anyway.
So the problem could be done without eager modding, but actually eagerness is
implicit just in being able to use a=11 and b=3 to begin with, since the text
only told you those numbers were /congruent to/ 11 and 3 mod 19.
(2) (b) -9999 = -99*101 + 0, so div is -99 and mod is 0.
(c) 10299 = 10*999 + 309, so div is 10 and mod is 309.
(3) "Lazy": To prove that for every odd n, n^2 = 1 mod 8, let any odd n be given.
By definition of "odd", there is an integer k such that n = 2*k + 1. /Take/
that k. Then n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1. Since k(k+1) is
always even, 4k(k+1) is always a multiple of 8, so n^2 is 1 more than a
multiple of 8, which means n^2 = 1 mod 8. Nothing wrong with this, but...
By the equivalence of lazy and eager modding, n^2 mod 8 = (n mod 8)^2 mod 8.
For (n mod 8) there are only four possibilities: n = 1,3,5,7. Now 1^2 = 1,
3^2 = 8 = 1*8 + 1, 5^2 = 25 = 3*8 + 1, and 7^2 = 49 = 6*8 + 1. Done.
(4) BAD = (11)(10)(13) = 1011.1010.1101 in binary.
Binary 1.1000.0110.0011 = 1863 in hex. "Fourscore and seven years ago..."
(5) 20CBA + 00A01 = 216BB in hex, since A+C = 10+12 = 22 = 6 in base 16.
The product is 20CBA + shift Ax20CBA two places left. Multiplying by A, we have:
AxA = 100 = 6*16 + 4 = 64 = 4-carry-6 in base 16;
AxB = 100+10 == 14 base 16, so = 6E = E-carry-6.
AxC == 8 mod 16, so you get 8-carry-7. So going right-to-left, one has:
4 (6 + E) (6 + 8) (7 + 0) (0 + 4) (1)
= 4 (4) (1 + 6 + 8) (7) (4) (1)
= 4 4 F 7 4 1 = 147F44, shift two left to get 147F4400.
Add 20CBA to get 148150BA in base 16.
(6) Are there any pairs in these sets that are not relatively prime?
OK if you answered instead whether they were mutually relatively prime.
(a) 21,34,55 = 3*7,2*17,5*11. No common factors whatever, so no on both counts.
(b) 14,17,85 = 2*7, 17, 5*17. Pair 17,85 are not relatively prime, since they
share 17. (But they have no factor in common among all three.)
(c) 25,41,49,64 = 5^2,41,7^2,2^6. No common factor anywhere.
(d) 17,18,19,23 = 17,2*3^2,19,23. No common factor anywhere.
(7) LCM(x,y) = x*y/GCD(x,y) = 2^7 3^8 5^2 7^11 / 2^3 3^4 5 = 2^4 3^4 5 7^11.
So the LCM is 16*81*5*7^11 = 80*81*7^11 = 6480*7^11. I have no idea what
7^11 is---for an ultrafinitist like me it's "nan" (not a number), but
anyway that's the answer.
(8) (a) GCD(9,11) goes 11 = 9 + 2, 9 = 4*2 + 1, so it's 1, and 1 = 9 - 4*2;
substituting 2 = 11 - 9 gives 1 = 9 - 4*(11 - 9) = 5*9 - 4*11.
(b) GCD(33,44) goes 44 = 33 + 11, 33 = 3*11 + 0, so GCD is 11, and
11 = 44 - 33 already gives you the linear combination.
(e) GCD(203,101) goes straight to 1, so 1 = 203 - 2*101.