The (a,b,c)-product problem, I (& Fermat & the internet)

Directing research with undergrads in math...

As I enter a sabbatical semester concentrating on undergraduate research, I will both write on interesting undergraduate research problems and also offer some advice on directing research projects with undergrads.  More on the general plan later ....  but instead, as I do in my own classrooms, ... let's worry about the "syllabus" later and jump right into the mathematics!

... and the (a,b,c)-product problem 

Lay a sheet of paper on a table and place your index finger in the middle of the paper.  Rotate the paper around your fixed finger by 30 degrees (say, clockwise.)  How many times must you do that rotation before the paper returns to its original position?

Twelve.  It takes 12 copies of the 30-degree rotation to "return to start".  The positive integer 12 is the order of the rotation by 30 degrees.

Let's multiply integers modulo 13.  (So this is an exploration in modular arithmetic.) Begin with the number 2 and keep multiplying by 2 until you get the number 1.  Here is what happens when you multiply by 2 modulo 13:

2, 2^2=4, 2^3=8, 2^4=16=3, 2^5=2*3=6, 2*6=12=-1, 

2*12= 24=11, 2*11=22=9, 2*9=18=5, 2*5=10, 2*10=20=7, 2*7= 14=1.

It takes 12 multiplicative steps to return to the "identity" number, 1.

2^12=1 modulo 13

and so the order of 2 modulo 13 is 12.

The order of an element f (under a certain operation) is the smallest positive integer n such that

f^n=1.

Since 2^12=1 modulo 13, and 2^n is not 1 for any smaller positive integer n, then the order of 2 modulo 13 is 12.

What is the order of 4 modulo 13?  Since 4=2^2, a moment's thought might suggest that the order of 4 is 6.  We write ord(4)=6.

Although number theory is a typical college class for upper level math undergraduates, modular arithmetic can be taught to elementary school children (usually called "clock arithmetic" in that setting) and so we have not yet gotten into any serious mathematics....

A simple question

One step off the trodden mathematical path can often lead one into the mathematical wilderness.  We begin a mathematical exploration by asking a simple question.

What is the order of a product of two elements?

Suppose I have two elements x and y (and some underlying operation like multiplication modulo 13).  If I know the order of x and the order y, what can I say about the order of yx (or the order of xy?)

For example, if we are doing arithmetic modulo 13 then ord(8) = 4 and ord(3)=3.  Now 3*8=24=11, so can those the two orders (ord(8)=4, ord(3)=3) tell us the order of 11?  Yes.

Since

8^4=1

then

(8^4)^3=1^3=1 

so 

8^12=1.

Since

3^3=1 

then

(3^3)^4=1^4=1

so

3^12=1.

Since

8^12=1 

and

3^12=1 

then

(3*8)^12=(3^12)(8^12)=(1)(1)=1.

A little thought suggests that the order of yx should be the least common multiple of the orders of x and y.  But embedded in this calculation is an assumption.  The assumption is that xy=yx, that is, that x and y commute.

But in most numerical systems, commutativity does not hold!  In the composition of functions or the multiplication of matrices, the order of the operation is important.  Even in the symmetries of planar objects (such as the rotation of the sheet of paper in the first paragraph), the order of the operations can be important.  (Choose two different lines through the center of the sheet of paper and reflect across each of those lines, one after the other.  In this case the order of line choice effects the final answer.)

What if we are composing functions or multiplying matrices or arranging reflections in the plane?  Now what can we say about the order of a product?  Now it gets interesting!

Consider a Rubik's cube: turn the Right face 90 degrees and then turn the Upper face 90 degrees.  Each individual turn (R or U) has order 4 but their product (UR, for example) has order 105!

We can express this question precisely as follows:

Given ord(x)=a, ord(y)=b, what values of c can occur in the computation ord(xy)=c?  

The Rubik's cube gives an example where (a, b, c)=(4, 4, 105).

We will explore this problem in the next post of this blog.  That exploration leads into group theory, geometry and some interesting combinatorics.

Math is addictive (and useful!)

I do math (every day!) because it is fun.  The projects I propose in this blog are driven by the joy of creativity.  Mathematics is creative!

However, some will ask, "What good is this?" presumably seeking applications beyond just fun.  In this case, I must point out that our entire internet commerce, especially any secure exchange of data on the internet, relies on modular arithmetic!  Pierre de Fermat first observed that if p is a prime number (say, p=13) then the order of any nonzero number modulo p must divide p-1.  Precisely, if a is not divisible by p then

a^(p-1)=1 modulo p.

This is Fermat's "Little Theorem". A century after Fermat, Leonhard Euler then observed that if n=pq is the product of two primes, p and q, then the orders of numbers (that are not divisible by either p or q) must then be a divisor of (p-1)(q-1).  If we know n but do not know p and q, then the unsolved problem of factoring integers in polynomial time can be turned into a public key encryption scheme in modular arithmetic.  The RSA algorithm, based on Euler's observation, is the primary mathematical algorithm in SSL & TLS cryptographic protocols.  Anyone purchasing a song or application over iTunes is using these cryptographic protocols and is therefore applying (deep in the background) a version of Fermat's Little Theorem!   How is that for a mathematical application?!

Next time: Partial solutions to the (a,b,c)-product problem.

[Mathematical prerequisites: This article requires no mathematics beyond high school.]

Follow Ken W. Smith on Twitter @kenwsmith54