Old algorithms and new

I’m taking a number theory class this summer, so my mind is full of residuals and mods.  In that mindset it’s easy to forget all the other math I’ve learned in my life.  Here’s an example.  I was asked to find a divisor between 2000 and 3000 of this expression:

85^9 -21^9 + 6^9

Because 85, 21, and 6 all have prime factors in common, it’s easy to find some primes that evenly divide this expression.  But that alone isn’t enough to find a single number between 2000 and 3000.

I considered all the divisibility formulas I had learned in the previous lecture:  Fermat’s Little Theorem, Euler’s Theorem, and Wilson’s Theorem, but nothing seemed to work.

It turns out, solving the problem is made easier by seeing that the first 2 terms in the expression:  85^9 - 21^9 can be expressed as a difference of cubes.  Twice actually!

85^9 - 21^9 = (85^3)^3-(21^3)^3

A difference of cubes can be factored as:

a^3-b^3 = (a-b)(a^2 +ab + b^2)

Substituting, we find:

85^9 - 21^9 = (85^3)^3-(21^3)^3 = (85^3-21^3)((85^3)^2+85^321^3+(21^3)^2)

But now we can do it again with the first factor:

85^3-21^3=(85-21)(85^2+85 \cdot 21+21^2)

Setting N equal to all those yucky square and cubes to the right, we now we have

85^9 - 21^9 = (85-21)N=64N=2^6N.

And so we have:

85^9-21^9+6^9 = 2^6N + 2^62^33^9 = 2^6(N+2^33^9)

And voila, we have found another factor, 2^6, that divides this expression.

Good math problems force the student to use not only skills they have just learned, but also draw on older skills and older theorems that have been sitting around unused in your brain.

This is another reason I think math contests are so valuable to our students.  Students continue to use all the algorithms they learned earlier, keeping it fresh in their minds.   Is it unfair to test students on factoring polynomials in a number theory class?  Strong students welcome the opportunity to be reminded of old almost-forgotten formulas because hopefully they’ll recognize those differences of cubes again in the future.

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s