This page has content which requires Javascript to be displayed correctly, such as LaTeX formulae or code snippets. Your browser doesn't seem to support Javascript. Sorry if this causes any problems.
Finding the remainder left behind when dividing a large number
It is easy to compute the remainder left behind upon dividing, for example, 2100 by 3 using modular arithmetic.
Modular arithmetic is a system of arithmetic where numbers wrap around, or get 'reset' once they reach a certain value. If you like to think visually, you can think of it as a number circle as opposed to the number line.
Consider this circle of circumference 2 units:
If you start at the point marked 0 and cover a distance of 2 units, you would end up at 0 once again. Also note that, starting at 0, moving along the circle by either 3 units or 1 unit will take you to the same point. We represent this fact by saying 3 \equiv 1 \pmod 2, read as "3 is congruent to 1 modulo 2".
When we say x \equiv y \pmod a, it is implied that x - y is an integral multiple of a, or that x and y both leave the same remainder upon division by a.
Some properties of these congruence relations make them very useful. If a_1 \equiv b_1 \pmod n and a_2 \equiv b_2 \pmod n, then the following hold true.
- (a_1 + a_2) \equiv (b_1 + b_2) \pmod n
- (a_1 - a_2) \equiv (b_1 - b_2) \pmod n
- (a_1 a_2) \equiv (b_1 b_2) \pmod n
To compute the remainder left on dividing 2100 by 3, we note that 2 \equiv -1 \pmod 3.
As a result, 2^{100} \equiv (-1)^{100} \pmod 3. This is, of course, a direct consequence of the third property.
Now, since (-1)^{100} = 1, the remainder left behind will be 1. You can verify this using Wolfram Alpha, or by using the mod (or %) function found in most programming languages.
Examples
1. What is the remainder when the number 72010 is divided by 25?
First, we note that 7^{2010} = 49^{1005}.
Now, 49 \equiv -1 \pmod {25}
\Rightarrow 49^{1005} \equiv (-1)^{1005} \pmod {25}
\Rightarrow 49^{1005} \equiv -1 \pmod {25}
\Rightarrow 49^{1005} \equiv 24 \pmod {25}
Hence, the remainder is 24.
Note: 49^{1005} \equiv -1 \pmod {25} \Rightarrow 49^{1005} \equiv 24 \pmod {25} because we can freely add and subtract multiples of 25.
We can verify this using Wolfram Alpha.
2. What is the remainder when 22006 + 2007 is divided by 17?
2^{2006} = 2^{4 \times 501 + 2} = 2^{2} \cdot 2^{4^501} = 4 \cdot 16^{501}
16 \equiv -1 \pmod {17}
\Rightarrow 16^{501} \equiv (-1)^{501} \pmod {17}
\Rightarrow 2^{4 \times 501} \equiv -1 \pmod {17}
\Rightarrow 4 \cdot 2^{4 \times 501} \equiv -4 \pmod {17}
\Rightarrow 2^{2006} \equiv -4 \pmod {17}
\Rightarrow 2^{2006} + 2007 \equiv -4 + 2007 \pmod {17}
\Rightarrow 2^{2006} + 2007 \equiv 2003 \pmod {17}
Hence, the remainder is 2003 mod 17, which is 14. This can be verified, once again, using Wolfram Alpha.
This work by Vikhyat Korrapati is licensed under a Creative Commons Attribution 3.0 Unported License.