This problem seems like a paradox but it isn’t. The so called “idiot savants” have been doing it without memorizing operation tables so why can’t the rest of the humans do it as well? I suspect that it is because the so called “idiot savants” are better equipped to recognize patterns in nature.
Let’s paraphrase the abstract problem for a concrete operation and start with the simplest operation there is: addition in Zn. It is trivial to verify that Zn is a group closed with respect to addition. In other words, for any a,b <= n-1 in Zn, the result of a+b is also in Zn. Namely, a + b = c where c is in Zn and c = n.q + r = r where r is the greatest common divisor of (a+b, n)
Problem: How can we compute the result of adding two integers in Zn without actually adding the 2 integers?
Solution: Find a pattern to generate all subsequent rows/columns in the table from the first trivial row/column.
First, let's compute the addition tables for the congruence classes of Zn for some n, namely 5, 6, and 7.
Below are the addition tables for Z sub 5, Z sub 6, and Z sub 7
The pattern should be easy to spot:
The first row simply lists all elements in Zn, and each subsequent row is simply a shift to the left by 1 integer from the previous row.
Here's the conjecture:
The proof is as trivial as the pattern itself: by definition.
This was the simplest of operations in Zn. I can't think of any real world applications for it, other than Abstract Algebra exams: you will never have to think what's 15+16 in Z sub 17 while writing out addition tables. Actually, navigation through different timezones is another real world application, duh.
However, there are other, much more powerful operations that are used in various aspects of our modern life and there is a method to the madness there as well.