Section 4.2 Going Modulo First
Okay, that's all fun. But we need power, too. Here's an example of such power. Even though I'm not physically present, I can do amazing computations! Let me compute \(2^{1000000000}\) (mod \(3\))! I'll do it instantaneously.
Ready for the answer? It's 1!
Perhaps you don't believe an absent author. We can check it with Sage:
Sage note 4.2.1. Timing your work.
In a Sage worksheet, putting %time before a command tells you how long it took. Putting %timeit instead runs the command many times and gives a ‘best of’ timing. (This does not universally work in the embedded cells in the web version of this book.)
Hmm, but that took more than a few milliseconds – strange that I could do it so fast!
Sage note 4.2.2. Numbers too big for a computer.
If I add one more zero, it will throw a very nasty error, like MemoryError: failed to allocate 1250000024 bytes, because things are too big. We can quickly go beyond the bounds of what our computers can do in number theory!
Now consider that I did this huge computation instantaneously in my head. Surely I must be full of brains, like the Scarecrow in L. Frank Baum's Oz books?
Of course, the reason is not that I am clever, but that congruence can be turned into arithmetic! Unlike the Wizard, I will give away my secret. I just used the following useful property.
Fact 4.2.3.
If \(a\equiv b\text{ (mod }n)\text{,}\) then \(a^m\equiv b^m\text{ (mod }n)\) no matter how huge \(m\) is.
Proof.
Now I do my first congruence computation:
the latter like all even powers of negative one. Ta-dah!
What I've done is first think of the original number as in the congruence, and then taken its power.
Sage can verify this approach is much faster, and even for much bigger powers. Here we will need to use the mod(x,m) syntax:
Even the presumptively very, very big latter computation should be as fast as your internet connection.
Sage note 4.2.4. Give things names.
We can use the print function as above with print( mod(2,3)^1000000000 ) to show multiple computations in a cell. Then again, it only prints them to the output, does not save them, and typing print() a lot can get annoying.
So instead, we can assign our ‘modulo integer’ a name, like b, and then use it to compute. This makes it easy to do lots of interesting tests.
The command in the last line is what prints out in any Sage cell.
Sage note 4.2.5. Making tuples.
In this case, we put commas between things so that all of the stuff in the last row prints out. The output is in parentheses because the commas create a tuple (a special Python way of making a list with certain nice properties).
Sage note 4.2.6. Types matter.
What was computed above is not a trick; I definitely couldn't do \(2000^{1000}\text{,}\) or even \(16^{1000}\text{,}\) in my head. How does Sage do it? The answer lies in the kind of thing b really is, which confirms that Sage is using modular numbers, not normal integers.
In Python, we can ask for the type of anything.In this case, we asked to output b and then its type, which is definitely not an ordinary integer, and can be manipulated much more efficiently.
The preceding notes were a lot of computer business, and especially the last one may have seemed too technical. But if you just skipped it, consider the main point; if the computer thinks it's a good idea to just think of the remainder before you do any arithmetic, maybe we should too.