Patrick (patrickwonders) wrote in math_class,
Patrick
patrickwonders
math_class

  • Mood:

NumberTheory101 (#2a): Answers to problems with Euclidean Algorithm

First, let me apologize. Somehow, in my head, I thought I had already posted these answers. Oi.

I am running behind on this week's lesson as well. It will be out by early next week.

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 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.

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

  • 0 comments