math_class: Number Theory 101 (Answers for Class #2)

Answers

1. Calculate:

1. (3^¹⁹) % 4

• ( (3 % 4)^¹⁹ ) % 4
• ( (-1)^¹⁹ ) % 4
• (-1) % 4
• 3

2. ( (53 * 26 + 906)^²⁴ ) % 5

• ( ((53 % 5) * (26 % 5) + (906 % 5))^²⁴ % 5
• ( (3 * 1 + 1)^²⁴ % 5
• ( 4^²⁴ ) % 5
• ( (-1)^²⁴ ) % 5
• 1

3. ( 3^¹⁹ ) % 7

There are probably lots of ways that one could go about doing this. All of the ones that I can think of are a bit tricky. I'm going to hinge off of the observation that 3^³ == -1  (mod 7)

• ( 3 * (3^³)^⁶ ) % 7
• ( (3 % 7) * ( (3^³) % 7 )^⁶ ) % 7
• ( 3 * (-1)^⁶ ) % 7
• ( 3 * 1 ) % 7
• 3

2. Use the Euclidean Algorithm to determine:

1. gcd(1536,1152)

• 1536 = 1 * 1152 + 384
• 1152 = 3 * 384 + 0
• gcd(1536,1152) = 384

2. gcd(1152,1536)

• 1152 = 0 * 1536 + 1152
• 1536 = 1 * 1152 + 384
• 1152 = 3 * 384 + 0
• gcd(1152,1536) = 384

3. gcd(256,55)

• 256 = 4 * 55 + 36
• 55 = 1 * 36 + 19
• 36 = 1 * 19 + 17
• 19 = 1 * 17 + 2
• 17 = 8 * 2 + 1
• 2 = 2 * 1 + 0
• gcd(256,55) = 1

Think about how the Euclidean Algorithm would work for:

1. gcd(360,72)

2. gcd(360,-72)

3. gcd(-360,-72)

Because the division algorithm always expresses the remainder r as a number which is greater than or equal to zero and less than or equal to the absolute value of b when trying to express a = q * b + r, there are some subtle differences in the value of q at various stages in in the algorithm. However, a q from one stage never gets fed onto the next stage. So, the remainders are unaffected.

Of course, following the letter-of-the-law for the algorithm as I presented it, you should get answers of 72, -72, and -72 respectively. However, it is common practice to always make a and b both positive at the start of the algorithm since it is obvious that if -72 divides both numbers, then 72 divides both numbers. Furthermore, one cannot really call -72 the greatest common divisor when 72 (a much greater number) is also a common divisor.