Yes, it is divisible. And you can answer similar questions within a matter of seconds to minutes after just going through the very basics of modular arithmetic.
Modular Arithmetic is informally known as "Clock Math" and fittingly so, because the logic follows as a 12-hour clock:
When dictating the time, we tend to speak in terms of "mod 12". What this means is that any number past 12 is reduced, like 17 becomes 5. As you may have noticed, the numbers we reduce the values to are the remainder when divided by 12. 17/12 = 1 rem 5, hence we say it is "5:00pm". In its simplest terms, that is how counting in mod 12 works : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 1, 2, 3, 4... and so on and so forth in a cycle (like a clock!)
Going past the familiar Clock
It is important to extend this metaphor of a "clock" to realise that Modular Arithmetic can deal with any size of "clock". The key is to find the remainders of the numbers we are working with and being careful with the kind of operations we use. It is critical to understand basic notation, so we minimise confusion. Let us try out some simple examples:
17 ≡ 5 mod 12
17 This is the original number that is being reduced. It can be positive or negative, but for now we will explore positive numbers only
≡ This is the congruence symbol. In modular arithmetic, this means the left number is congruent to the one on the right mod 12
5 This is the remainder. Dividing the green number by the blue number gives a remainder of this.
mod 12 This sets the divisor or the number being divided by. Choosing a good divisor can allow many equations to be solved in seconds.
Just like regular arithmetic, modular arithmetic can also work with multiple arithmetic operations. Let us try to understand why such operations can work. Let us work with mod 5 (a "5 wheel").
It is important to realise that in the world of "mod 5", all three segments : 1, 6, 11, are congruent and one and the same. This is because dividing all these numbers by "5" gives a remainder of one. Observe the wheel carefully and look at each of its segments to understand what it means to work in "mod 5".
Now, using the wheel, we will add two numbers.
Let us add the red and the green number to give the blue number
2 + 9 = 11
This is straightforward arithmetic, but since we are working on the "5 wheel", we can even write this as:
2 + 9 = 11 = 1 mod 5
This might look odd at first, but look at the wheel and realise that 11 = 1 in the world of mod 5. Expanding this concept into multiplication should now be easier. Recall that multiplication is repeated addition.
7 * 3 = 7 + 7 + 7 = 2 + 2 + 2 = 2 * 3 mod 5
As you see, the multiplication changes from 7*3 to 2*3. This may help you realise that multiplication in modular arithmetic allows you to "reduce" each of the multipliers separately. Hopefully reading through the above two examples one after another should help make it clear. Now, armed with our knowledge of performing multiplication and addition, we will move to the third level : exponentiation is repeated multiplication
7⁶ = 7 * 7 * 7 * 7 * 7 * 7 = 2 * 2 * 2 * 2 * 2 * 2 = 2⁶
As you see, the exponentiation changes from 7⁶ to 2⁶. This may help you realise that exponentiation in modular arithmetic allows you to "reduce" the base. Hopefully reading through the above three examples one after another should help make it clear. Note : Each example is dependant on the one before it.
Finally, we solve the problem we set out to solve. Is (27⁸⁶ - 1) divisible by 13?
For solving such a complex problem, we should first be smart about choosing which "mod world" we want to work in. Since the problem is asking about divisibility by 13, it will be best to work mod 13.
27⁸⁶ - 1 = (1)⁸⁶ - 1 mod 13
= 1 - 1 = 0 mod 13
Here, we "reduce" the base 27 to 1. This is because dividing 27 by 13 gives a remainder of 1. This allows us to do some simple calculations to realise the fact that the expression is equal to 0 mod 13. Recall that anything being equal to 0 mod 13 must be divisible by 13. Hence, we have shown the expression in the question is indeed divisible by 13. Notice how we do not even need to calculate the value of 27⁸⁶ for our calculation. That is the power of modular arithmetic!
Conclusion
Amusingly, the most prominent examples of modular arithmetic is cryptography and music. Cryptography exploits large prime numbers and uses their "mod worlds" to carry out calculations for encrypting/decrypting/error detection. At the same time, music, specifically digital music, uses smaller "mod worlds" to find perfect chords and chord progressions! The world of modular arithmetic is one of those small worlds of mathematics that is so straightforward yet tackles mammoth-like questions similar to the one we solved today. Spending just 30minutes to 1 hour learning the ins and outs of modular arithmetic may just make you that much better at solving previously impossible challenges.
Comments