Divisible or Not
(a) Prove that for any number n, the number formed by the last two digits of n are divisible by 4 if and only if n is divisible by 4. (For example, ‘23xx’ is divisible by 4 if and only if the number ‘xx’ is divisible by 4.)
(b) Prove that for any number n, the sum of the digits of n are divisible by 3 if and only if n is divisible by 3.
2 Extended Euclid
In this problem we will consider the extended Euclid’s algorithm. The bolded numbers below keep track of which numbers appeared as inputs to the gcd call. Remember that we are interested in writing the GCD as a linear combination of the original inputs, so we don’t want to accidentally simplify the expressions and eliminate the inputs.
(a) Note that x mod y, by definition, is always x minus a multiple of y. So, in the execution of Euclid’s algorithm, each newly introduced value can always be expressed as a "combination" of the previous two, like so:
gcd(2328,440) = gcd(440,128) [
= gcd(128,56) [
= gcd(56,16) [
= gcd(16,8) [ = gcd(8,0) [
= 8.
(Fill in the blanks)
(b) Now working back up from the bottom, we will express the final gcd above as a combination of the two arguments on each of the previous lines:
[Hint: Remember, 8 = 1⇥56+( 3)⇥16. Substitute this into the above line.]
[Hint: Remember,
(c) In the same way as just illustrated in the previous two parts, calculate the gcd of 17 and 38, and determine how to express this as a "combination" of 17 and 38.
(d) What does this imply, in this case, about the multiplicative inverse of 17, in arithmetic mod 38?
3 Modular Arithmetic Equations
Solve the following equations for x and y modulo the indicated modulus, or show that no solution exists. Show your work.
(a) 9x ⌘ 1 (mod 11).
(b) 10x+23 ⌘ 3 (mod 31).
(c) 3x+15 ⌘ 4 (mod 21).
(d) The system of simultaneous equations 3x+2y ⌘ 0 (mod 7) and 2x+y ⌘ 4 (mod 7).
