Problem 4. [15 points] Fill in the boxes below. All variables denote integers. No exp nations are required, but we can only award partial credit for an incorrect answer if you show your reasoning (a) Suppose c is a multiple of 17. Write the smallest nonnegative integers that make this statement true 6x2+4x10-4x+6=0x+6(mod17) Solution. If r is a multiple of 17, then =0(mod 17). Therefore, all terms involving r on the left are congruent to zero (b)Now suppose a is not a multiple of 17. Write the smallest nonnegative integers that make this statement true 6.x 17+4x 4x+6三15·x+12(mod17 Solution. By Fermat's Theorem, Io= 1 (mod 17). Thus, we can reason as follows 6x2+4x0-4x+6≡2(x)2-6r(x)+416-4x+6(mod17) 2-6x+4-4x+6(mod17) -2x+12(mod17 (c) In the box, write the smallest positive integer that makes this statement true There exist integers s and t such that 117+t·153=x and only if x≡0(mod9 Solution. Recall that an integer r is expressible as a linear combination of a and b if and only if a is a multiple of ged(a, b), i.e. a =0(mod ged(a, b)). In this case, Euclids algorithm gives gcd(153,117)=gcd(117,36)=gcd(36,9)=9Quiz 1 7 Problem 4. [15 points] Fill in the boxes below. All variables denote integers. No expla￾nations are required, but we can only award partial credit for an incorrect answer if you show your reasoning. (a) Suppose x is a multiple of 17. Write the smallest nonnegative integers that make this statement true. 2x 32 − 6x 17 + 4x 16 − 4x + 6 ≡ 0 · x + 6 (mod 17) Solution. If x is a multiple of 17, then x ≡ 0 (mod 17). Therefore, all terms involving x on the left are congruent to zero. (b) Now suppose x is not a multiple of 17. Write the smallest nonnegative integers that make this statement true. 2x 32 − 6x 17 + 4x 16 − 4x + 6 ≡ 15 · x + 12 (mod 17) Solution. By Fermat’s Theorem, x 16 ≡ 1 (mod 17). Thus, we can reason as follows: 2x 32 − 6x 17 + 4x 16 − 4x + 6 ≡ 2 ￾ x 16
2 − 6x ￾ x 16
+ 4x 16 − 4x + 6 (mod 17) ≡ 2 − 6x + 4 − 4x + 6 (mod 17) ≡ −2x + 12 (mod 17) ≡ 15x + 12 (mod 17) (c) In the box, write the smallest positive integer that makes this statement true: There exist integers s and t such that s · 117 + t · 153 = x if and only if x ≡ 0 (mod 9 ) Solution. Recall that an integer x is expressible as a linear combination of a and b if and only if x is a multiple of gcd(a, b), i.e. x ≡ 0 (mod gcd(a, b)). In this case, Euclid’s algorithm gives: gcd(153, 117) = gcd(117, 36) = gcd(36, 9) = 9