A proof regarding cube numbers (Triggered by a student)

[Eric Macaulay]

Dear all,

While I was in high school maths class yesterday, a student asked us to prove that every cube number is either a multiple of 9, one less than a multiple of 9 or one more than a multiple of 9. The proof in his text book used case analysis and what the young man called "a magical step". He asked if there was a more systematic proof. Delighted in my young student's dissatisfaction with the "rabbit" proof, I set out to develop a calculational proof. However, it's proving more challenging than I had thought. It looks like I need properties of the lcm, but gould there be a simpler way? I thought I would post the problem here for my calculational colleagues to have a go.

Looking forward to your thoughts,

Eric M.

[Musa]

Dear Eric,

I do not have an answer for your problem, but have some suggestions that may be helpful.

One setup for your problem may be

 good : ℕ → 𝔹

 good n = “the number n is divisible by 9”

 good n = (n mod 9 = 0)   --or any equivalent definition that you prefer.

Then prove: ∀ n : ℕ. good (n³) ≡ good (n³ + 1) ≡ good (n³ - 1)

It may, or may not, be helpful to note that the product of any 3 consecutive numbers

---such as n³ - 1, n³, n³ + 1--- is necessarily divisible by 3.

It may, or may not, be helpful to note that

  goodish (m + n) ≡ goodish m ≡ goodish n

where this is a relative of `good`:

  goodish : ℕ → 𝔹

  goodish x = (x mod 2 = 0)

Perhaps `good` satisfies a similar property --but not this one since it fails for `m, n := 1, 1`.

You may find the thesis of Joao Ferreira's helpful: It is in the calculational style and devotes an entire section to number theory. See joaoff.com/wp-content/uploads/2011/06/thesis-a4-colour.pdf

All the best,

Musa

[Jeremy Weissmann]

A perfectly systematic (though not generalizable) proof would be to simply compute the cubes of the residues 0..8 mod 9. The workload can nearly be halved, since 5..8 can be written as -4..-1 mod 9. 

Incidentally, a case analysis saves work because we are presented with three cases to begin with. My spidey sense tells me we want to proceed by connecting divisibility by 9 to divisibilty by 3 (more manageable), and then exploiting the fact that ±1 are both cubes, using the sum/difference of cube formulas. 

--
You received this message because you are subscribed the mathmeth.com mailing list.
To unsubscribe from this group, send email to Calculational-Math...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/Calculational-Mathematics?hl=en
---
You received this message because you are subscribed to the Google Groups "Calculational Mathematics" group.
To unsubscribe from this group and stop receiving emails from it, send an email to calculational-math...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Eric Macaulay]

Pardon me, Jeremy, but could you clarify what you mean by the sum/difference of cube formulas?

Eric

To unsubscribe from this group, send email to Calculational-Mathematics-unsub...@googlegroups.com

For more options, visit this group at http://groups.google.com/group/Calculational-Mathematics?hl=en
---
You received this message because you are subscribed to the Google Groups "Calculational Mathematics" group.

To unsubscribe from this group and stop receiving emails from it, send an email to calculational-mathematics+unsub...@googlegroups.com.

[Jeremy Weissmann]

x³ ± y³ = (x±y)·(x²∓xy+y²)

To unsubscribe from this group, send email to Calculational-Math...@googlegroups.com

For more options, visit this group at http://groups.google.com/group/Calculational-Mathematics?hl=en
---
You received this message because you are subscribed to the Google Groups "Calculational Mathematics" group.

To unsubscribe from this group and stop receiving emails from it, send an email to calculational-math...@googlegroups.com.

[Jeremy Weissmann]

And the point is not that I know that this will be used. 

When we encounter a problem, we want to pick the sort of tools to keep at close hand, just in case they are called for. So when I see this problem, I think, okay, we may need divisibility properties, primality properties, modular arithmetic, etc. 

+j

On Feb 9, 2018, at 13:21, Eric Macaulay <elih...@gmail.com> wrote:

To unsubscribe from this group, send email to Calculational-Math...@googlegroups.com

For more options, visit this group at http://groups.google.com/group/Calculational-Mathematics?hl=en
---
You received this message because you are subscribed to the Google Groups "Calculational Mathematics" group.

To unsubscribe from this group and stop receiving emails from it, send an email to calculational-math...@googlegroups.com.

[Herwig Egghart]

I think there are two levels to this problem:

As Jeremy has indicated, we can easily use brute force to convince ourselves that each of the 9 residues yields 0, 1, or 8 when cubed. No rabbit whatsoever; we simply exploit the fact that the number of residues is finite, so checking them all leads to a finite proof. On a pragmatic first level, we are done.

However, isn't it somewhat curious that the 9 original residues shrink to only 3 residues after cubing? Well, let's see. For a cube to be a multiple of 9, all we need is a factor of 3 in the original number:

(3∙n)³ = 27∙n³

Conversely, if the original number is NOT a multiple of 3, we have:

(3∙n ± 1)³ = 27∙n³ ± 3∙9∙n² + 3∙3∙n ± 1

Apart from the final "± 1", everything is a multiple of 9 — thanks to the binomial coefficient 3 in the term "3∙3∙n". So this is the "deeper reason" why no cube can be farther away than 1 from a multiple of 9. (Similarly, no square can be farther away than 1 from a multiple of 4, etc.)

The second proof may not be as straight-forward as the first one, but it needs fewer case distinctions and creates deeper insight — including a generalization to other powers. And the only "creative" step was to correlate a number and its cube in terms of their prime factors (which I wouldn't call a rabbit either).

Cheers

Herwig

[Jeremy Weissmann]

Herwig, I am sure this is the original proof Eric was talking about. 

--

[Diethard Michaelis]

true
<=> { obvious: (natural) numbers are either even or odd }
Any number is either a multiple of 2 or 1 plus a multiple of 2.
<=> { formalize }
n = 2*k + x for all n >= 0 and some k >= 0, x = 0 or 1
<=> { squaring ; algebra }
n^2 = (2*k)^2 + 2*2*k*x + x^2 for ...
<=> { algebra ; (*) x^2 = x as x = 0 or 1 }
n^2 = 2*2*(k^2 + k*x) + x for ...
<=> { deformalize ; 4 = 2*2 }
Any square number is either a multiple of 4 or 1 plus a multiple of 4.

Exercise (easy, just repeat the steps above):
Any number is either a multiple of 3 or 1 plus or minus a multiple of 3.
Thus any cube number is ...

All very elementary,
no case analysis needed (except for "proving" (*)).

Challenge starts here: Generalize.

Diethard.

[Herwig Egghart]

Regarding ODD squares, we can even say a little more —

because every odd number can be expressed as 4∙n ± 1:

(4∙n ± 1)² = 16∙n² ± 2∙4∙n + 1

Apart from the final "+ 1", everything is a multiple of 8. Thus, every square number is either a multiple of 4 or one more than a multiple of 8.

The same idea works for an exponent of 4.

If the original number is even, we have:

(2∙n)⁴ = 16∙n⁴

If the original number is odd, we have:

(4∙n ± 1)⁴ = 256∙n⁴ ± 4∙64∙n³ + 6∙16∙n² ± 4∙4∙n + 1

Apart from the final "+ 1", everything is a multiple of 16. Thus, every bi-square number is either a multiple of 16 or one more than a multiple of 16. (The shrink effect here is even bigger than for cubes, viz. by a factor of 8 instead of 3.)