Someone asked me this question a few days ago, and I have a few ideas on how to do it, but it seems to be too much work for a problem of this nature.
We know that a number is divisible by 3 if the sum of all its digits are divisible by 3.
The question is either:
Prove that this is so
or
Prove why this is so
I don't remember, but I think they amount to pretty much the same thing
Thanks guys
It's one of the basic counting applications. I'll prove it later tonight when I get back home.Quote:
Originally Posted by Jhevon
I got some time I'll do that now.
Let n = a_k*10^(k) + .. + a_(3)*10^(3) + a_2*10^(2) + a_1*10^(1) + a_0
Note:
a_k*10^(k) is 99...99 + 1
a_(3)*10^(3) is 999 + 1
a_2*10^(2) is 99 + 1
a_1*10 is 9 + 1
= a_k*99...9 + a_k*1 + a_(k - 1)*9...9 + a_(k - 1)*1 + ... + a_2*99 + a_2*1
= a_k*99...9 + a_(k - 1)*99...9 + ... + a_2*99 + a_1*9 + [a_k + a_(k - 1) + ... + a_1 + a_0]
Bold is div. by 3 (and 9), thus it should be obvious now why a number is divisible by 3 if the sum of all its digits are divisible by 3 (and also the same is true for 9).
Q.E.D.
There are other divisibility tests, such as for 11, you alternate between +/- and see if it's divisible by 11 to determine if the number is.
Quote:
Originally Posted by Jhevon
Here is my method.
Let P(x) be some polynomial in Z[x] (meaning the ring of integers).
We have a theorem, if,
a = b (mod c)
Then,
P(a) = P(b) (mod c)
(I am not goint to prove this. Rather do what my professor does, leave it as an excercise).
We know that,
10 = 1 (mod 3)
Let,
N=a_n*10^n +a_{n-1}*10^{n-1}+...+a_1*10^1 +a_0
Be the way you write the positive integer in base 10.
And consider the polynomial,
P(x)=a_n*x^n+a_{n-1}*x^{n-1}+...+a_1*x +a_0
Then,
P(10)=P(1) (mod 3)
BUT!
P(10)=N
And P(1)=a_1+a_2+...+a_n=S (where S is digits sum).
Thus,
N = S (mod 3)
Hence,
3|N if and only if 3|S.
Q.E.D.
This is the only part of the thorem that is as of yet unjustified. I don't know how to prove this.Quote:
Originally Posted by ThePerfectHacker
you and me bothQuote:
Originally Posted by ecMathGeek
it kind of seems intuitive though, but that often counts for nothing
you know, i forgot to show the guy that ask me this proof, lol, i guess he doesn't need it anymore. i'll ask him
here's another if you guys are bored (i'm doing this from memory, so pardon any errors, the same guy asked me this question, so if you guys have problems, i'll check with him to make sure i got the question right):
i actually thought up two ways to do this, but i ran into trouble at the punchline. here goes
let r be a rational number
let a be an irrational number
let s be a real number
Prove or disprove: either (ar + s) or (ar - s) is irrational
If s is rational, then this is false. (I might go through the process of proving this)Quote:
Originally Posted by Jhevon
If s is irrational then I have no idea how to prove this. I would assume only if s = ar + n or s = n - ar for some rational number n will either (ar + s) or (ar - s) be rational. Otherwise, it is irrational.
It is trivial.Quote:
Originally Posted by ecMathGeek
Let, P(n) = an^2+bn+c
And,
x = y (mod z) &
Then,
x^2 = y^2 (mod z)
Thus,
ax^2 = ay^2 (mod z) *
Using & again we find that,
bx = by (mod z) **
And,
c = c (mod z) ***
Adding * and ** and *** we get:
ax^2+bx+c = ay^2+by+c (mod z)
Thus,
P(x) = P(y) (mod z)
Now prove it for the n>2 case.
Again trival.
How about this one. i don't like this proof, but i figured i'd get your opinions on it.Quote:
Originally Posted by Jhevon
Proof: either (ar + s) or (ar - s) is irrational
Assume to the contrary that both (ar + s) and (ar - s) are rational, and let ar + s = m. then we have ar - s = m - 2s, and m - 2s is rational, so s and m must be rational
but we have a = (m - s)/r, but that would make the number a rational, contrary to our assumption.
QED
Here's another, i don't like this one much either
Proof: either (ar + s) or (ar - s) is irrational
take ar + s, and let ar + s = m, then we have two cases: either m is irrational or m is rational
if m is irrational we have the desired result
if m is rational then we can write r = (m - s)/a. but a is irrational. therefore the only way that (m - s)/a can be rational is if (m - s) is irrational. since we assumed m is rational, then s must be irrational. But that would mean (ar + s) would give an irrational result, which makes m irrational, contrary to our assumption.
QED
Here's a third proof that kind of evolved from my second one. i like this one a bit better
Proof: either (ar + s) or (ar - s) is irrational
take ar + s, and let ar + s = m, then we have two cases: either m is irrational or m is rational
if m is irrational, we have the desired result
if m is rational then we can write r = (m - s)/a. but a is irrational. therefore the only way that (m - s)/a can be rational is if (m - s) is irrational. since we assumed m is rational, then s must be irrational.
now ar - s = m - 2s, since s is irrational, m - 2s is irrational. so we have whenever (ar + s) is rational, (ar - s) is irrational, and therefore, one or the other is always irrational
QED
Please give your opinions on the proofs above, which is the best and whether or not i proved what i set out to. if none do the job, please tell me what mistakes i made, i don't like the first two myself, so i'm banking on the third one
Let s = sqrt(2), a = sqrt(2), r = -1Quote:
Originally Posted by Jhevon
(sqrt(2)*(-1) + sqrt(2)) = 0, which is rational.
OR
Let s = 2pi, a = (1 - pi), r = 2
(2(1 - pi) + 2pi) = 2, which is rational.
The point I am trying to make is the assumption that if a and s are irrational then (ar + s) is irrational is false. But your third proof takes care of this (I think).
I have a question. Can 0 be consider irrational?
maybe you misread my proof, or i made something unclear. i never made the assumption that if a and s are irrational then (ar + s) is irrational, what the proof you quoted says is that, for (ar + s) to be rational then a and s must be irrational.Quote:
Originally Posted by ecMathGeek
i never indicated case 1 and case 2, so maybe that's why. but you have an issue with case 2 apparently, in case 2, i assumed ar + s was rational, not irrational
Nope, zero is a rational numberQuote:
I have a question. Can 0 be consider irrational?
This was the part of your proof that I was commenting on. Perhaps you didn't mean to say this, but my point is that this is not true.Quote:
Originally Posted by Jhevon
well, in that case, you are correct:DQuote:
Originally Posted by ecMathGeek
i didn't mean to say that (i hope)
what about the third proof? do you see any porblems with that one, or the other proof for that matter? the one without the line you quoted
I like this proof. If (ar + s) and (ar - s) are rational and we let (ar + s) = m, then (ar - s) = m - 2s, and so m and m - 2s must be rational, which can only be true if s is rational. However solving for a in either term (ar + s or ar - s) we would get a = (m - s)/r, where m, s, and r, are rational numbers, making a rational, but a is irrational thus we have a contradiction.Quote:
Originally Posted by Jhevon
I think this proves it. It does not declare whether m or m - 2s really are rational, but it indirectly dictates that one or the other must not be, otherwise a = (m - s)/r would be rational, which it cannot be.
Basically, both the rationality of m and s are being called into question, where we know that a cannot be and r must be rational. Since s and m cannot both be rational, we know that either m or m - 2s MUST be irrational, which means that (ar + s) or (ar - s) MUST be irrational.
This is also an excellent proof because it draws on the same conclusions that I (and you) made above.Quote:
Originally Posted by Jhevon
I don't remember what problem i had with the first one, but now with the second one i realize there are two ways that (m - s)/a can be rational if a is irrational. we can have (m - s) irratonal, or (m - s) = 0 which is rational. however, in the case where (m - s) is 0, we would have r = 0, so we would haveQuote:
Originally Posted by Jhevon
ar + s = m = s
=> 0 + s = s
which is trivial, but nevertheless, i think the proof should account for that in some way