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
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.
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.
you and me both
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)
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.
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.
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 = -1
(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.
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 numberI have a question. Can 0 be consider irrational?
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.
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.
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 have
ar + s = m = s
=> 0 + s = s
which is trivial, but nevertheless, i think the proof should account for that in some way