# Using your Head is Permitted

## June 2013 solution

Let *A* be some large constant. For example, it may be 10^{40}.
Let *B* be another constant, computed as
*B* = 1 - *A* + *A*^{2} + *A*^{4}.
One program that would solve the question is

1. *a* = *x* mod 2233393

2. *b* = *a* + *A*

3. *c* = *B* mod *b*

4. *d* = *c* mod 2233393

This solves the problem in only four operations.

The reason this solution works is that if *X* ≡ *Y* in some
ring (for example, modulo some number), then for any polynomial, *P*, we
also have *P*(*X*) ≡ *P*(*Y*) in the same ring.

Here, our ring is the integers taken modulo (*a* + *A*). Under this
modulus, the number -*a* and the number *A* are equivalent. Now,
we calculate *B* in this ring. The value of *B* was defined as a
polynomial over *A*. In the ring, it is therefore equivalent to the same
polynomial at the value -*a*. This value is
1 - (-*a*) + (-*a*)^{2} + (-*a*)^{4} =
1 + *a* + *a*^{2} + *a*^{4}, which is our target
polynomial. We can now think of this as our target polynomial calculated at
*a*.

Our next observation is that the true value of this polynomial
(at *a*) must be nonnegative and less than *a*+*A*. It is
nonnegative because all its coefficients are nonnegative. It is less than
*a*+*A* because in our first step (*a*=*x* mod 2233393) we
bounded *a*, and therefore also the value of the polynomial. The choice of
*A* as a "large" constant was merely meant to have it larger than this
bound. Because the true value to be computed is between 0 and the modulus, we
know that the result of the modulo operation at step 3 is the actual value of
the polynomial at *a*, and not some folded value.

Next, consider everything in the ring of the integers modulo 2233393. By
construction, *x* and *a* are equivalent in this ring. Therefore, so
must *c* and the target value be. For the target value, specifically, we
know that by definition it must be between 0 and 2233393 (the value of the
modulus), so we take *c* modulo this value at step 4, giving us the final
result.

We note that this is a general technique, and neither special properties of the
target polynomial nor special properties of the modulus value were used in the
process.

I have recently presented a paper in TAMC 2013 (an extended abstract of which
can be found here) showcasing the
general fact that
the simple availability of a "large enough" number is a huge boon to
computational power, far beyond what is apparent in the present solution. The
same paper also shows the great computational powers of the modulo operation.
By comparison, the paper shows that in many cases multiplication does not
bring any added computational power.

Back to riddle

Back to main page