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:
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!
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.
If \(a\equiv b\text{ (mod }n)\), then \(a^m\equiv b^m\text{ (mod }n)\) no matter how huge \(m\) is.
Now I do my first congruence computation: \begin{equation*}2\equiv -1\text{ (mod }3)\text{ and }(-1)^{1000000000}=1\; ,\end{equation*} 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.
We can use print to output multiple things per line of code, though it only prints them. Of course, writing this a lot can get annoying. So instead we can assign our ‘modulo integer’ a name, like b, and then just do as normal. This makes it easy to do lots of interesting tests.
The last command is what prints out.
In this case, we put commas between things so that all of the stuff in the last row prints out. It's in parentheses because the commas create a tuple (a special Python way of making a list with certain nice properties).
What was computed above is not a trick; I definitely couldn't do \(2000^{1000}\), or even \(16^{1000}\), 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 print out b and then to print out its type, which is definitely not an ordinary integer, and can be manipulated much more efficiently.
This was a lot of computer business. The point is that if the computer thinks it's a good idea to just think of the remainder before you do any arithmetic, maybe we should too.
