That works. Your statement of the logic is imprecise though: you need to change:

Every even number ends on 0, 2, 4, 6, or 8.

To

If a number ends in 0, 2, 4, 6, or 8. then it is even

your implication was the wrong way round, but you used it correctly (the right way round).

Do you think you can prove:

If a number ends in 0, 2, 4, 6, or 8. then it is even.

?

Hello fdrake,

Thanks for your reply. Happy to read that my proof, though cruder, works. Sorry for my late response, lots of other responsibilities, you know the deal.

Now for your question:

Can I proof:

''If a number ends in 0, 2, 4, 6, or 8, then it is even.''

I would go about it this way:

P1: An even number is defined by it being divisible into two equal parts without any leftovers, aka, two equal integers.

P2: The last digit of any number determines it being even or uneven.

P3: Therefore we only have to take into account the last digit to cover all numbers.

P4: 0, 2, 4, 6 and 8 are divisible into two equal integers

P5: the other options for number endings, 1, 3, 5, 7, and 9 are not

Conclusion: any number ending in 0, 2, 4, 6 and 8 is even.

Problems with this proof:

*P1 is not proven
*P2 is not proven
*In general: using too many words instead of symbolism

Cheers!

Your reasoning's good, but the maths isn't there. Think you'd be able to prove P2 (and thus P3, which is just a restatement of P2) given that the link between the last digit in decimal notation of numbers and their even-ness is a consequence of the following:

any number can be written in the form 10*k+r, where r is the last digit in their decimal notation

?

Hello fdrake,

Thank you for your reply and additional challenge.

Lets see.

I want to prove:

P2: The last digit of any number determines it being even or uneven.

I can use this fact about numbers:

Any number can be written in the form 10 * k + r, where r is the last digit in their decimal notation.

I'll make use of this axiom:

An even number + an even number is an even number, or:

2m + 2n = 2(m+n)

And, for any k, 10 * k is even, for

10 * k = 2(5k), thus containing 2 as a factor, making it even.

Then, if r is an even last digit number, the options for the last digit are 0, 2, 4, 6, or 8. All even numbers because of the 2m definition.

If we add any even r to 10 * k, then the result will be even, for we are adding an even number to an even number. Thus, if the last digit is even, the whole number is even.



To prove the same for uneven numbers:

An even number + an uneven number is an uneven number, or

2m + 2n+1 = 2(m+n)+1

And, for any k, 10 * k is even, for

10 * k = 2(5k), thus containing 2 as a factor, making it even.

Then, if r is an uneven last digit number, the options for the last digit are 1, 3, 5, 7, or 9. All uneven numbers because of the 2n+1 definition.

If we add an uneven r to 10 * k, then the result will be uneven, for we are adding an uneven number to an even number. Thus, if the last digit is uneven, the whole number is uneven.


I guess I'm using too much language, I am not used to formal reasoning yet. I enjoy it, though.

It is possible to make that proof rigorous. Actually the shortest rigorous version by that path uses the following, which is the same as the book proof but replacing 2 by 10:

P3 "The square of any number ending in 0 ends in 0."

Both this and the even-ness theorem are specific cases of the more general theorem:

P4 "The square of any number divisible by integer m is divisible by integer m."

Putting P3 together with the observations that:

(a) 0, 2, 4, 6 and 8 and 10 are divisible by 2, and
(b) a number ends in 0 if and only if it is divisible by 10, and

we can infer that any number ending in 0, 2, 4, 6 or 8 is even.
Then an expansion of (10n + k)^2 enables us to see that the square of an even number ends in 0, 2, 4, 6 or 8. Then by (a) and (b) we can show that that square is divisible by 2.

There are gaps to be filled in here, but that's the general shape.

It is much quicker to just prove P4 and then consider the case where m=2. But it is a good exercise to do it the long way around.

Here are some related theorems that you might find interesting to prove:

- for any number divisible by 3, the sum of the digits is divisible by 3
- for any number divisible by 9, the sum of the digits is divisible by 9
- the decimal expansion of k/9, for k in {1,2,3,4,5,6, 7, 8} consists of an infinite series of k's.
- the decimal expansion of k/7, for k in {1,2,3,4,5,6} consists of the sequence 142857 repeated endlessly, with the first m digits removed, where m is in {0, 1, 2, 3, 4, 5} and depends on k.

The fourth one seems quite bizarre and unintuitive, but when you prove it, you see why it must be so. That then leads on to showing why that sort of phenomenon doesn't happen for any other decimal numeral. But when we consider expressions in other bases (eg base-8, base-12) we find that there are conditions where a similar phenomenon appears.

Aren't you over-complicating it?

The square of any even number is infact an even number multiplied by itself (ie another even number). And that multiplication is infact the repeated addition of a string of even numbers.
So 6 squared = 6 * 6, = 6 + 6 + 6 + 6 + 6 + 6.
Is it not axiomatic that an even number added to another even number always gives an even number?

Is it not axiomatic that an even number added to another even number always gives an even number? — Tim3003

No. It is easy to prove though. Even numbers take the form 2k for some k (whole k). Take two even numbers 2n and 2m for any n and m. The sum is 2n+2m, which is 2(n+m), which is of the form 2k for k=n+m.

- for any number divisible by 3, the sum of the digits is divisible by 3
- for any number divisible by 9, the sum of the digits is divisible by 9 — andrewk

These are interesting. I think they both depend on being factors of 9.

Going through the multiples of 3:
The digits of 3, 6 and 9 are 3, 6 and 9 - clearly divisible by 3.
12 is next: Adding 3 to 9 results in an increase of 1 in the 10's column and a decrease of 7 in the units column. So for the digits +1 and -7 net out at -6. Hence the digits of 12 are those of 9 less 6. Ie still divisible by 3.
Then come 15, 18 - again adding 3 to the units column, so digits must be divisible by 3.
21 is like 12 - add 1 to the 10's, subtract 7 from the units. Again, net -6 from 18. Still fine.
24 and 27 are like 15 and 18.
30 is like 21 and 12.
So we've got to 10 * 3, with all having digit totals divisible by 3. Any multiplication of 3 above 30 can be built by adding combinations of these together. So they too must be divisible by 3.
Eg 54 = 30 + 24. Digits = 3 + 6 = 9.
81 = 3 * 27. Digits = 3 * 9 = 27. Or 81 = (2 * 30) + 21. Digits = (2 * 6) + 3 = 15.
189 = (6 * 30) + 9. Digits = (6 * 3) + 9 = 27.

For 9 it's simpler, as each addition of 9 adds 1 to the 10's column and subtracts 1 from the units column. So for all multiples of 9 up to 90 the digits total 9. From then on the same logic applies as for 3.

189 = (6 * 30) + 9. Digits = (6 * 3) + 9 = 27. — Tim3003

I realised in bed last night that this doesnt work, since the total of 189's digits is 18 not 27.
More thought needed...

Hello fdrake, andrewk and Tim3003,

Thanks for your input and continuation of the discussion.

To be honest, I'm lost at

- for any number divisible by 3, the sum of the digits is divisible by 3

I wouldn't know how to even begin proving this.

I scribbled around on paper a bit and thought, well, since the number is divisible by 3, it can also be written as 3n.

So we have a number 3n, if you write it down in the original form, before the division by 3, then the sum of the digits is also 3n, or say 3m. How would one express 'sum of digits' more formally in order to reason with it mathematically?

A two digit number = 10k + r = (9k + k) + r = 9k + (k + r)

[9k + (k + r)] ÷ 3 = 3k + (k + r) ÷ 3

So 10k + r is divisible by 3 if k + r is divsible by 3

Try this for 3 digit, 4 digits, n digits

Hello TheMadFool,

Thanks for your reply.

Have we now converted any two digit number into

3k + (k + r)/3

Where the left stands for the first digit, and the (k+r)/3 stands for the second digit?

Here is are a couple of hints:

1. A number in decimal notation can be written as $d_0 + 10d_1 + 10^2d_2 + ...$, where $d_0, d_1, d_2, ...$ are digits.

2. Can you prove that if you subtract 1 from any of those decimal factors ($10^n-1$), the result is divisible by 3?

1. A number in decimal notation can be written as d0+10d1+102d2+...d0+10d1+102d2+..., where d0,d1,d2,...d0,d1,d2,... are digits. — SophistiCat

I was playing about with modular arithmetic, mod 10 mod 100 etc, and I kept adding the remainders together. I completely forgot to write the number out in base 10 positional notation.

That's a really good hint as it also contains a strategy for other proofs about divisibility and digit sums (even in other bases). Beautifully tailored to the context, made my day, thanks. :grin:

How would one express 'sum of digits' more formally in order to reason with it mathematically? — Ulrik

Are you familiar with the concept of functions? That is the easiest way to express this, by defining a function f, whose domain and range are the positive integers, such that f(x) is the sum of the (base ten) digits of x.

The theorem is that, for any positive integer n, it is divisible by 3 if and only if f(n) is divisible by 3.

Many theorems that involve integers, as these do, can be proved by mathematical induction, so it's worth getting familiar with that concept. Once one has the technique down pat, it's a question of finding a way to apply it to the problem. Sometimes there is more than one way, and some ways are easier than others.

For this one, we could start by observing that the theorem is true for the numbers 1, 2, ...,9. Next we seek to prove that if it is true for n it is also true for n+1.

That's not necessarily the quickest or the easiest way to do it by mathematical induction. But it's the first that comes to mind.

@TheMadFool, Sophisticat, AndrewK

My head is still spinning a bit. I'm still at TheMadFool's proof of

- for any number divisible by 3, the sum of the digits is divisible by 3

Just to be sure, k and r each stand for a digit in any two digit number?

So if a number is divisible by 3, the sum of k and r should be divisible by 3?

I think Sophisticat's method will be easier. Just to make the hint a bit broader, consider that if $d_n, d_{n-1}, d_{n-2}, ..., d_2,d_1,d_0$ are the digits of our number from left to right, then the number's value is:

$d_0 + 10d_1 + 10^2d_2 + ... 10^n d_n$, which we can re-write as

$d_0 + (10 - 1) d_1 + d_1 + (10^2 - 1)d_2 + d2 + .....+ (10^n - 1)d_n + d_n$

which is equal to $(d_0 + d_1 + .... + d_n) + (10 - 1) d_1 + (10^2 - 1)d_2 + .....+ (10^n - 1)d_n$.

So if we can prove that $(10^k -1 )$ is divisible by 3 for every positive integer k, the sum of digits $(d_0 + d_1 + .... + d_n)$ will be divisible by 3 if and only if the original number is.

Now if $k$ is even, equal to $2m$, we have
$(10^k -1 ) = (10^{m}-1)(10^{m}+1)$, which is divisible by 3 if $(10^{m}-1)$ is.
Alternatively, if $k$ is odd, equal to $2m+1$, we have
$(10^k -1 ) = 9\cdot 10^{2m} + (10^{m}-1)(10^{m}+1)$, which is divisible by 3 if $(10^{m}-1)$ is.

We can then use induction on $k$ to prove our result.

And since for k=1, the basis for induction, it is also divisible by 9, then if sum of digits is divisible by 9, then the number is also.

@andrewk, Hrvoje,

I must admit that this is all a bit beyond me.

Let's see where I lose track.

I understand that any number can be rewritten as

d0 + d1(10) + d2(10^2) + ad infinitum

Where d stands for a digit between 0 and 9. ( I also don't know how to write the make-up you used)

So, what we are trying to proof is that:

if d0 + d1(10) + d2(10^2) / 3

then

d0 + d1 + d3 / 3

Do I at least understand the theorem to be proved?

First small step I lose track with: how do you know when you can write any number as

d0 + d1(10) + d2(10^2) + dn(10^n) ? I have trouble understanding this method of notation and when to use it and what it means.

d0 + d1(10) + d2(10^2) + dn(10^n) ? I have trouble understanding this method of notation and when to use it and what it means. — Ulrik

$10365 = 5*10^0+6*10^1+3*10^2+0*10^3+1*10^4$
so
$d_0 =5, d_1=6, d_2=3, d_3=0, d_5=1$
can do the same for any number. That's what it means to write something in base 10 positional notation (the usual way we write numbers).

@fdrake,

Thanks for clearing that up for me. So what I don't understand is how one can suddenly grow broader to any number and still use that broadest definition for our to be proven theorema, like andrewk wrote:

d0 + d1(10^1) + d2(10^2) +....+ dn(10^n)

So we can just take this and generalize our findings to represent any number? Why? It's the +....+ dn(10^n) I have trouble with. And how can I know what to do in cases like this? I.e,. using this generalized formula of a number to proof our statement.

So we can just take this and generalize our findings to represent any number? — Ulrik

If I understand you correctly, the question that you are asking is "How can we know that any number can be given a decimal representation?" (Because the expression d0 + d1(10^1) + ... is just what the decimal representation stands for.)

This is a good question. Note that in order to ask this question, you must first acknowledge that a number - a natural number in this case - is a mathematical entity that exists independently of its representation. So it is at least a priori conceivable that there may be a number that cannot be represented in decimal notation.

Natural numbers are usually formalized by Peano axioms. Any set of entities that satisfy these axioms represent natural numbers. So if we can prove that the set of decimal numbers satisfy Peano axioms, then we have proven that decimal numbers represent natural numbers - in other words, any natural number has a decimal representation. (Now, of course, every decimal number is a natural number, but what is in question is whether every natural number is also a decimal number.)

If you take a look at the Peano axioms, you will see that decimal numbers automatically satisfy most of them, since every decimal number is a natural number. The one that is not obviously true is the postulate that says that natural numbers are closed under succession, i.e. the successor of every natural number is also a natural number. Is the successor of every decimal number a decimal number? In other words, does $(d_0 + 10d_1 + 10^2d_2 + ...) + 1$ always have a decimal representation?

We can prove this by induction. First we can easily show that the postulate holds for every single-digit decimal number: d + 1 is either another single-digit decimal number or 10. Then we assume that any n-digit decimal number has a decimal successor, and using this assumption we can prove that any (n+1)-digit decimal number has a decimal successor...

Hello Sophisticat, thanks for your reply. I have however decided to let the matter rest. I'm getting on fine with my mathematics book, and this is clearly a bit beyond my current capabilities.

Thanks to all who contributed to the thread.