Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - [SOLVED] Easy Number Theory Question...for you guys, not me :)

  1. #1
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3

    [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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    Quote Originally Posted by Jhevon View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2006
    Posts
    401
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Jhevon View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by ThePerfectHacker View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ecMathGeek View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by Jhevon View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by ecMathGeek View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Jhevon View Post
    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
    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
    Last edited by Jhevon; April 29th 2007 at 03:32 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by Jhevon View Post
    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

    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?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ecMathGeek View Post
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by Jhevon View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ecMathGeek View Post
    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
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by Jhevon View Post
    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.

    Quote Originally Posted by Jhevon View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Jhevon View Post
    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
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. [SOLVED] Quick and likely easy limit theory question
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 17th 2010, 11:14 PM
  2. Number Theory , an easy proof .
    Posted in the Math Puzzles Forum
    Replies: 5
    Last Post: August 1st 2010, 08:01 PM
  3. Ahhh tan! Easy question for you guys
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: November 9th 2009, 11:45 PM
  4. [SOLVED] easy complex number questions
    Posted in the Algebra Forum
    Replies: 8
    Last Post: October 24th 2009, 12:20 AM
  5. solved problems of elemantry number theory
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 16th 2007, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum