January 2005

January 2005:

January 2005:
Let a, b and c be integers. The expression a º b (mod c) represents that b is the remainder when a is divided by c. For example, 21 º 1 (mod 10) because 1 is the remainder of dividing 21 by 10. Prove that for all a, b and c, if a º b (mod c), then a^k º b^k (mod c) where k is a positive integer. Now use this theorem to find the remainder when 4^999,999 is divided by 7.
Since a º b (mod c), a = qc + b for some integer q. Thus, a^k = (qc + b)^k The binomial expansion formula shows that all the terms in the expansion of (qc + b)^k have a factor of c in them except for b^k. This means (qc + b)^k = c(some integer) + b^k. Hence, by definition a^k º b^k (mod c). Now we can apply this important result to solve a problem. We need to find the remainder of dividing 4^999,999 by 7. This can be done very quickly if we observe that 4³ º 1 (mod 7) because 64 = 9(7) + 1. By the theorem that we proved, 4^3(333,333) º 1^333,333 = 1. Therefore, the remainder is simply 1. There are other ways to find this remainder, but this method is advantageous because it is quick. Topic: Number Theory

Previous Month	Archive	Next Month