Section5.2Going Modulo First

Okay, that's all fun. But we need power, too. And that power is what makes calculating \(2^{1000000000}\) mod (3) instantaneous for me - it's 1!

I can check it with Sage:

Remark5.2.1

Sage note:
Note that wasn't immediate. 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!

Now consider that I did this huge computation instantaneously in my head. Of course, the reason is not that I am clever, but that congruence can be turned into arithmetic! I used the following useful property.

Now I can reveal my secret: \(2\equiv -1\) mod (\(3\)), and \((-1)^{1000000000}=1\), 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.

Subsection5.2.1Computer diversion

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:

Remark5.2.3

Sage note:
We can use print to output multiple things per line of code, though it only prints them.

Remark5.2.4

Sage note:
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.

Remark5.2.5

Sage note:
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.

Remark5.2.6

Sage note:
The next cell tells you what kind of thing b really is, which confirms that Sage is using modular numbers, not normal integers.

Remark5.2.7

Sage note:
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.

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.