HR - proof - state things [ 'tractably' , 'comprehensively']

Submitted by metaperl on Sat, 04/01/2006 - 11:33am.
::
I am reading p.4 of The Haskell Road and for a long time struggled with one part of a proof on that page. It was his comment about c, a divisor of n. ... there are natural numbers a and b with c = a * b, and also 1 < a and a < c. but then a divides n..." and that is what confused me. He did not directly show how it was true that a divides n just because c was the least divisor of n.

Stating things tractably:

Let's forget about my problem for a second and look at how to state things tractably. It may be true that if n is prime then that means that n is only divisible by 1 and itself. But is that the most algebraic way of stating it? Can you go from that statement you just made to anything useful? Maybe, but let's take a look at this way of stating it: n prime means that only 1 * n = n and nothing else

One other thing. Let's try this same technique for what it means for a to be divisible by b? It means that b * x = a, where x is integral.

Now what have we bought ourselves? Instead of primeness and divisibility being two concepts with no apparent relation, we see them both in terms of what it means for products involving things which are prime and things which are divisible. Both concepts are now expressed as 

 E * F
where E and F vary based on which concept we are talking about.

Why is this useful? Because at one point in my following the proof, I hit this statement: assume c = LD(n) is not prime. In other words "Assume that the least divisor of n is c and it is not prime." Now we reach the second thing:

State all implications

So let's take our statement and explore each isolated fact: First, c is the least divisor of n tell us all of this:
  • c * q = n
  • 1 * n = n
  • c > 1

    And c not prime tells us all of this:

  • 1 * c = c
  • a * b = c, where a != 1

    Now what threw me is when the author of the text said: "Then there are natural numbers a and b with c = a * b, and also 1 < a and a < c. but then a divides n..." and that is what confused me. He did not directly show how it was true that a divides n. But if you look above, we have 

     c * q = n
    but also 
    a * b = c
    . By substituing 
    a * b
    for c, we have 
     a * b * q = n
    which means that a divide n.