Clock Arithmetic and Prime Numbers
One of the greatest mathematicians of all
time was Carl Gauss. One of his earliest achievement was the invention
of clock arithmetic, writes Marcus du Sautoy in
Music of the Primes. It
is easy to understand.
It is 10 o’clock. If someone says they
will be back in 4 hours, we add 4 to 10 to get 14. But since the clock only has
12 hours, we don’t say the person will be back at 14 o’clock; instead we say 2
o’clock. Stop for a moment and think of how you knew 14 meant 2 o’clock.
Because it is the remainder when 14 (the answer) is divided by 12 (the number
of hours on the clock). That’s clock arithmetic.
Gauss found a different use for it. Say,
you want to find the remainder when 3 x 9 x 12 is divided
by 11. You start by calculating 3 x 9 = 27. Find the
remainder when 27 is divided by 11 – the answer is 5. Now multiply this
remainder (5) by the other number (12) to get 5 x 12 = 60. Again, find the
remainder when 60 is divided by 11 – the answer is 5. That’s your final answer:
when 3 x 9 x 12 is divided by 11, the remainder will be 5.
This works for any clock number – it was
11 in this example, but it can be any number (5, 13, 10293, anything). This may
seem like a nice trick, but useful? Its power comes into play when you deal
with the product of large numbers. Instead of first calculating a very large
product, then doing the division, this trick cuts down the time drastically.
Especially in Gauss’ time when even the calculator had not been invented.
Time saving aside, clock arithmetic
yielded other insights:
“Just as the telescope had allowed
astronomers to see new worlds, the development of the clock calculator helped
mathematicians to discover in the universe of numbers new patterns.”
And centuries later, even today in the
age of supercomputers:
“Gauss’ clocks are central to the
security of the Internet, which utilizes calculators whose clock faces bear
more hours than there are atoms in the universe.”
Let’s see how.
Internet security is based on prime numbers.
Which makes the following question critical - Is there any quick way to find
out if a number is prime? Brute force division checks aren’t practical if the
number in question is, say, 70 digits long. (Modern security algorithms need
primes that are that big and larger). But worry not, Fermat had found a way –
yes, he of the Fermat’s Last Theorem fame. It’s called Fermat’s Little Theorem.
And it is based on clock calculators. It says:
Let’s understand that equation/theorem with
an example.
- Assign ‘p’ to be any prime number. Say p = 5. This is the clock number.
- Now pick any value for ‘x’, say x = 4.
- Calculate the LHS (left side hand), using clock arithmetic.
5. You see that the LHS equals RHS (both 4).
Here is the key: LHS will equal RHS only
if p (the clock number) is a prime. In our example above, remember we
had chosen p = 5, a prime.
Let’s try the above steps, but this time
with ‘p’ as a composite.
- Say, p = 6 (composite). This is the clock number.
- Pick any value for ‘x’, say x = 5.
The LHS is the last number on the last
row, i.e., 1.
3. Calculate the RHS (right hand side): it’s
maths for “what is the remainder when x (i.e., 5) is divided by p (i.e., 6)?” Ã The
answer is 5.
4. You see that the LHS does not
equal RHS in this case. Because ‘p’ was composite.
How does this help in quickly checking if
a number is prime? Well, assign ‘p’ to be the number you want to check. Pick
any value for ‘x’ and repeat the above steps. If LHS equals RHS, then the
number ‘p’ is prime; if not, ‘p’ is composite. This is way faster than any
other way of checking if a number is prime, esp. when the number in question is
huge (70 or more digits long).
This theorem is weird – why/how would primes have a pattern with something as weird as a clock calculator? We know that it is true, and it’s the kind of stuff that “gets mathematician’s blood racing”, says du Sautoy.
Comments
Post a Comment