# Thread: [SOLVED] Easy Number Theory Question...for you guys, not me :)

1. ## [SOLVED] Easy Number Theory Question...for you guys, not me :)

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

2. Originally Posted by Jhevon
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.

3. 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.

4. Originally Posted by Jhevon
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

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.

5. Originally Posted by ThePerfectHacker
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).
This is the only part of the thorem that is as of yet unjustified. I don't know how to prove this.

6. Originally Posted by ecMathGeek
This is the only part of the thorem that is as of yet unjustified. I don't know how to prove this.
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

7. Originally Posted by Jhevon
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.

8. Originally Posted by ecMathGeek
This is the only part of the thorem that is as of yet unjustified. I don't know how to prove this.
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.

9. Originally Posted by Jhevon
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

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

10. Originally Posted by Jhevon

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
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?

11. Originally Posted by ecMathGeek
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).
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

I have a question. Can 0 be consider irrational?
Nope, zero is a rational number

12. Originally Posted by Jhevon
since we assumed m is rational, then s must be irrational. But that would mean (ar + s) would give an irrational result
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.

13. Originally Posted by ecMathGeek
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.
well, in that case, you are correct
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

14. 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
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.

Originally Posted by Jhevon
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
This is also an excellent proof because it draws on the same conclusions that I (and you) made above.

15. Originally Posted by Jhevon
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
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

Page 1 of 2 12 Last