Modular Multiplicative Inverses Mystery Cache
Modular Multiplicative Inverses
-
Difficulty:
-
-
Terrain:
-
Size: 
(small)
Please note Use of geocaching.com services is subject to the terms and conditions
in our disclaimer.
Cache is NOT at the listed coordinates, but that's a good place to park. However, it is located
nearby, at N 44° 31.abc, W 092° 44.def, where abc and def are to be determined.
- If you got by the title you should be able to figure out the location of this cache! The
location is near the parking coordinates given above. Weatherwise, if you can get to the
parking lot you probably can get to the cache. The exact location has the same degrees and
minutes as those in the parking coordinates. However the decimal parts, in thousandths, are
the modular multiplicative inverses of those given, as explained below.
- Parking To find the parking location given above, go to either Welch Village or Vasa and
take County Road 7 towards the other. About halfway between the villages is a scenic
one-lane road, Belle Creek Way, heading west along the north bank of Belle Creek. At the
end of the road (about one mile) is a parking lot in the Richard J. Dorer Memorial State
Forest. The cache is about a quarter mile hike, mostly uphill along trails, from the
parking lot.
-
Inverses A multiplicative inverse is a fancy term for reciprocal. Thus 1/2 is the
multiplicative inverse of 2; and 1/45 is the multiplicative inverse of 45, etc. In general, if we
multiply an integer by its inverse we get 1.
-
Modular Arithmetic In modular arithmetic, we're just working with integers. All the
arithmetic is performed by taking the remainder after dividing by some number, called the
modulus. For all our work here we'll take the modulus to be 1,000. Thus for addition
782 + 453 = 235, the remainder after dividing 1,235 by 1,000; that is, we just throw
away the thousands. Similarly for multiplication: 782 X 453 = 246 (rather than 354,246).
-
Modular Multiplicative Inverses Let's put these two ideas together. The modular
multiplicative inverse of an integer is the integer you can multiply it by and just get 1
(after disregarding the thousands). For example, the modular multiplicative inverse of
453 is 117, because 453 X 117 = 001 (rather than 53,001). Similarly 259 X 139 = 001
(rather than 36,001).
-
The problem To find the location of the cache (N 44° 31.abc, W 092° 44.def) you will
need to find the inverses of 681 and 331, that is, numbers abc and def so that the products
681 X abc = 001 and 331 X def = 001 (after the 1,000's are ignored.)
- Hint on calculating the inverses:
One way to find the inverse is to develop its digits from right to left.
For example, to find the inverse, say pqr, of 423, try multiplying 423 times pqr:
4 2 3
times p q r
----------
.. .. 3r
in which 3r must end in 1. Aha! r must be 7, because 3 X 7 = 21.
So far we have:
2
4 2 3
p q 7
---------
2 9 6 1
in which the 2 has been carried. Continuing,
4 2 3
p q 7
------------
2 9 6 1
.. .. 3q
....
--------------
0 1
For the ten's digit to be 0 we need (3q+6) to end in 0.
Hence 3q must end in 4. Thus q = 8 (because 3 X 8 = 24. Let's try it with q = 8:
4 2 3
p 8 7
---------
2 9 6 1
3 3 8 4
3p
--------------------
sum 0 1
Now sum = 3p + 9 + 8 + 1 (the 1 is the carry from 6+4)
which will end in 0 if 3p ends in 2.
Therefore p = 4 (because 3 times 4 is 12).
Yes! 487 X 423 = 206,001.
So the modular multiplicative inverse of 423 is 487 (if the modulus is 1,000).
- Other applications Modular multiplicative inverses occur in many applications, in
particular, in encryption, such as the RSA public key encryption method. But that's a
subject for another cache! See GCQJ6Z
-
Container The cache is a green water bottle by an old birch tree stump and covered with birch bark so it can't be sighted from over the fence which is only a few feet away.
Additional Hints
(No hints available.)