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

 1. (3^^{19}) % 4

 ( (3 % 4)^^{19} ) % 4
 ( (1)^^{19} ) % 4
 (1) % 4
 3
 2. ( (53 * 26 + 906)^^{24} ) % 5

 ( ((53 % 5) * (26 % 5) + (906 % 5))^^{24} % 5
 ( (3 * 1 + 1)^^{24} % 5
 ( 4^^{24} ) % 5
 ( (1)^^{24} ) % 5
 1
 3. ( 3^^{19} ) % 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^^{3} == 1 (mod 7)
 ( 3 * (3^^{3})^^{6} ) % 7
 ( (3 % 7) * ( (3^^{3}) % 7 )^^{6} ) % 7
 ( 3 * (1)^^{6} ) % 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 letterofthelaw 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.
