Saturday, December 18, 2010

My Math Alphabet: F is for Factoring

My Math Alphabet: F is for Factoring 



Factoring Numbers
Factoring numbers is usually pretty straightforward.  If we're trying to find the factors of a number n, we check each prime up to the square root of n*. There are easy ways to check whether 2, 3, and 5 are factors, and about 73% of randomly picked numbers will have at least one of these factors. (I just now figured that out. Challenge #1: How?)  But once we've pulled out those factors, or purposely chosen a number that doesn't have any of those factors, it gets just a bit harder; with the help of a calculator, we just check whether n/p is a whole number. Here's a cute bit of math trivia: The first three numbers I'd check with a calculator - 7, 11, and 13 - multiply to make 1001, so for example, 137,137 factors to 7 . 11 . 13 . 137. (137 does not have 2, 3, 5, 7, 11, or 13 as factors, so I know it's prime.)

Although this search is relatively simple, it depends on knowing the list of primes to check (2, 3, 5, 7, 11, 13, 17, 19, ...), and that gets lots harder to produce for really big numbers. I remember reading the Scientific American article in 1978 about the mathematics behind a new form of cryptography, that involved multiplying two very big prime numbers to get a  number that would be too big to factor (in a reasonable amount of time). This scheme, now dubbed RSA after the 3 mathematicians who worked it out, is part of what helps keep online information private. Of course, what qualifies as a big enough number changes over time as computers become more powerful. Here's a list of the first ten thousand primes.

Factoring numbers is good practice for improving your number sense, and mathematicians sometimes find that a meditative exercise. If you have a calculator handy, it's pretty quick to check out the factoring of the number in this xkcd comic (the square root of 1453 is 38.118..., so you only have to check the primes up to 37). That's challenge #2.

Some mathematicians are good at arithmetic and would check out possible factors in their heads. I'd rather not myself, but G.H. Hardy and Ramanujan, perhaps like most number theorists, would have liked that sort of thing. A much-quoted story has Hardy saying his taxi  number, 1729, was dull, and Ramanujan responding that it was a very interesting number because it's the smallest number expressible as the sum of two cubes in two different ways. Hmm, I just factored 1729 (challenge #3), and I think it's interesting in another way - its prime factors are in an arithmetic sequence.



Factoring Polynomials
We spend a lot of our time in beginning algebra courses on factoring polynomials, and some teachers question whether that's a good topic to spend the time on. One reason for factoring polynomials is to find solutions to equations. But computers and calculators can answer those questions so easily, perhaps this topic become has become archaic. (And besides, most polynomials can't be factored. I remember a lovely post about that, and cannot find it. Can someone point me to it?) Here's a cool picture by Dan Christensen, of all the complex roots of polynomials with integers coefficients of degree 5 or less. (More here.)

In the comments to dy/dan's post Grocery Shrink Ray, one person wrote:   (comment #13)
Is teaching factoring the best use of time in the classroom? Is it the best topic we can teach students, at this point in their mathematical learning? WCYDWT can’t answer those questions, but it can raise them and get us thinking. In the case of factoring, I think these questions are fair ones. It’s true that I’m asking some pretty leading questions here; as you might be able to guess, my answer would probably be “no”. In my view, factoring is not terribly critical in real life, and this happens to be correlated to the fact that it’s hard to come up with WCYDWT problems (or real-world problems) to motivate learning factoring.
I replied:
Factoring may not have real-life applications, but it leads into cool deeper math topics. I see it as very important in algebra.
 So, what are those cool deeper math topics? 

One is Pythagorean triples, which I've posted about before. But here's a mathematical use for factoring I'd never seen before: George Sicherman wanted to find a way to create a pair of dice that would have the same sums as regular dice, with the same probabilities (7 comes up most often, for instance).  He used polynomials (and their factors) to find his unusual dice. (Found at Plus Magazine.)

What are some of the other cool mathematical uses of factoring?

_____
*If f is a factor of n, then f . g = n. One of these two numbers must be less than the square root of n, and the other more, unless n = f . f.

13 comments:

  1. i saw the dice problem in grad school
    and solved it by trial-and-error (or,
    if for some reason we want to sound
    like schoolteachers, by "guess and
    check"). the book i saw it in used
    *generating functions* to display
    a more systematic approach... a
    topic i knew nothing about (except
    that it gave me the heebie-jeebies;
    i'd seen it at the tail end of a
    probability course in a big hurry
    and learned nothing except
    "generating functions are scary").
    anyhow, it's a great problem
    *because* you can solve it
    without high-tech (not even
    polynomials!)... there are,
    after all, only a small number
    of cases to examine...*and* because
    it also lends itself to more
    advanced treatments.

    on factoring polynomials:
    i'll just take this opportunity
    to ask other algebra teachers
    to (obsessively) mention *what
    number set* we're allowing
    as coefficients. it would be
    very helpful in my guess to
    introduce notations... Z[x]
    for "the set of polynomials
    (in the variable 'x')
    having integer coefficients",
    for example. Z[x] can then
    be considered as a subset
    of Q[x] or C[x] (polys with
    Rational or Complex coefficients
    respectively). one then has
    the (so-called) fundamental
    theorem of algebra: all
    polynomials factor in C[x].
    also, rather a surprising result
    ("gauss's lemma"): if a Z[x]
    poly factors in Q[x], it factors
    in Z[x].

    i ranted about x^4 + x^2 +1
    almost exactly two years ago
    here (and had a great
    deal of fun doing it... the only "real
    world" reason i know or want for
    understanding more about polys
    ["but how can we use music in
    *real life*, mister mozart?"]).

    love the "alphabet", by the way.

    ReplyDelete
  2. The Polynomial Remainder Theorem is a neat result that can be used to evaluate polynomials quickly.

    As for WCYDWT, I worry that taking that philosophy to the extreme means a student tries to find applicability to everything and neglects to appreciate learning for its own sake. If one wanted a purely economical view of time, it would be more efficient to teach students how to earn money and simply inform them that there will always be a supply of highly-educated, but poor graduate students to do your math for you.

    ReplyDelete
  3. This is a post that Sam Shah wrote about factoring... includes a nice chart showing how many polynomials of the form x^2 + bx + c will/won't factor.

    http://samjshah.com/2009/08/13/factoring-schmactoring/

    ReplyDelete
  4. @Hao, I don't think anyone intends WCYDWT to apply to all of math. My impression is that it's a way to make application problems more relevant.

    @Owen (anonymous), I love your post on factoring. I vaguely remember reading it before, but enjoyed it just as much when I read it this morning. (The joys of a bad memory!)

    ReplyDelete
  5. @KFouss, Thank you! That's the one I was looking for!

    ReplyDelete
  6. The best that I can do to defend our emphasis on factoring polynomials is that it enables us to talk about a deep analogy between polynomials and integers. The zero-product law is an expression of the fact that the ring of polynomials is an integral domain, and factoring allows us to talk about that.

    At the same time, the more I think about it the less justification I have for including factoring polynomials in our curriculum. First, a survey of the defenses of factoring that I've seen on ze intertubes:
    1) Factoring leads to deeper mathematical topics
    2) Factoring can be used to solve fun puzzles.
    3) Factoring is necessary for more math.
    (And of course, those who have a problem with factoring because it isn't real-world-useful are partially missing the point.)

    I'm dismissive of 2). All that pain isn't worth a few parlor tricks. And I have a hard time agreeing with 3), since I don't remember factoring anything in between graduating high school and teaching.

    My complaint with 1) is that there are so many deeper and richer mathematical ideas that we could be teaching our students that if the richness of factoring is what justifies its place in our curriculum, I'd gladly give it up. Give me an extra two days to work on the Monty Hall Problem or to convince students that there are higher infinities, or to prove the irrationality of 2 or Zeno's Paradoxes.

    One of our goals, as math teachers, is to convince some of students that math is worth learning more about. We're salesmen for all sorts of fields where math is key, and I doubt that factoring is the deepest, most exciting mathematics that we could bring to the high school level.

    Sadly, the best justification for the presence of factoring is the instrumental one; you need factoring for so much of the high school curriculum that our students need a good factoring background. But this just passes the buck to those other topics (simplifying rational expressions, solving quadratic equations, domain issues with rational functions, some limit problems, etc.).

    ReplyDelete
  7. nicely put, MBP.
    here's john d. cook's recent
    maybe you only need it
    because you have it
    .

    but let it be said: these are "weeder" classes
    and this has been a *very* effective technique for
    treating people like weeds. why ask "why?"?

    OT... only formally anonymous
    (because "word verification" is
    already enough screening
    without further logs-in)

    ReplyDelete
  8. I found this link a few days ago: factoring and drawing stars. Besides the topic, it's really beautiful. the other video I've seen by her is also really great...
    http://www.youtube.com/watch?v=CfJzrmS9UfY

    ReplyDelete
  9. I have got to watch those Vi Hart videos, haven't I? I'll reply more thoughtfully here later. (I'm in a bookstore, trying to catch up just enough to not worry about my online life while I enjoy xmas.) ;^)

    ReplyDelete
  10. Check 2, 3, 5... good.

    Now, use that 7*11*13 = 1001 to check the next three. Divide the number into groups of three digits, and alternately add and subtract (sounds awful, example coming), leaving a 3-digit difference. Check that difference for 7, 11, 13. If one works, it works in the original number.

    Ex:

    83,123,432,798
    83 - 123 + 432 - 798 = 406. 7 goes into 406 (420 - 14 = 406), so it goes into the original number. If 7 didn't work, we'd try 11, then 13.

    23,496
    496 - 23 = 473. 7 doesn't go in (473 + 7 = 480. phhhpt). 11 does go in, so 11 goes into the original.

    Other tricks? For 11, add/subtract every other digit. If the difference is divisible by 11, so was the original.

    ex
    2348
    2 - 3 + 4 - 8 = -5. No good

    4381805
    4 - 3 + 8 - 1 + 8 - 0 + 5 = 11. Yup, 11 goes into 4381805.

    for 7, separate the last digit, double it, and subtract from the rest.

    ex:

    347291
    34729 - 2 = 34727
    3472 - 14 = 3458
    345 - 16 = 329
    32 - 18 = 14
    Yeah!
    or 1 - 8 = -7
    Yeah!

    littler number
    1964
    196 - 8 = 188
    18 - 16 = 2
    boo.

    Happy Holiday.

    Jonathan

    ReplyDelete
  11. And then the fun question is: Why do these methods work?

    ReplyDelete
  12. The coolest thing to me about factoring is that it turns an addition problem into a multiplication problem. Symmetrically, distributing turns a multiplication problem into an addition problem. This is almost mathematical alchemy!

    The value of turning addition into multiplication is that it allows us to use the "zero product property" to find solutions to polynomials which we can factor (if they are set equal to zero). It is also the basis for the "completing the square" process, which allows us to rewrite a general quadratic in vertex form and solve for the variable using square roots.

    So, without the ability to factor, the quadratic formula would not have been derived. But, I digress...

    Somehow, I just find it really neat that it is possible to rewrite an addition problem as a multiplication problem (or vice versa). This is a critical skill to be comfortable with as folks move along in algebra, as sometimes it is the only way to either collect like terms in an expression or "make this expression look like that one" (think equation forms, many trig identities, etc.).

    In real life, if students are using the quadratic formula without need for understanding why it works, then factoring is not a needed skill. For those students who like to understand how/why a process works however, I think factoring is a critical skill when studying surface area or projectile motion problems.

    http://mathmaine.wordpress.com

    ReplyDelete

Comments with links unrelated to the topic at hand will not be accepted. (I'm moderating comments because some spammers made it past the word verification.)

 
Math Blog Directory