1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number Theory Proofs

  1. Mar 10, 2010 #1
    1. For any positive integer n, if 7n+4 is even, then n is even.
    2.Sum of any two positive irrational numbers is irrational.
    3. If m, d, and k are nonnegative integers with d=/=0 then (m+dk) mod d = m mod
    4. For all real x, if x^2=x and x=/=1 then x=0
    5. If n is an integer not divisible by 3, then n^2 mod 3=1

    2. Basically I have to prove (or disprove) all of those and I'm stuck. Any advice and feed back would be appreciated.

    3. Here are my attempts at solutions
    1. By contraposition, if n is odd then 7n+4 is odd. If N is odd, then n=2k+1 for some integer k. so 7(2k+1)+4, and by algebra we get 2(7k+5)+1. 7k+5 is an integer, so it must be odd.

    Is this right? I think it is but I'm never sure because I'm terrible at number theory.

    2. For this one I found a counterexample and I think that is sufficient to get the problem right but I want to know why it's a false statement..anyone have any insight?

    3. This is confusing. Basically after half an hour of writing stuff I haven't reached any conclusions. I'm sure it has something to do with the quotient remainder theorem because the form of (m+dk) is very similar to QRT where given any interger n and positive integer d, there exists unique integers q and r such that n=dq+r. Any help would be appreciated.

    4. This one is really bothering me. I know that it's true but I'm trouble proving it. I keep going back to the method of exhaustion but obviously that won't work. I have a feeling that this is really simple and I'm just overlooking something.

    5. This is another that I know is true but I don't know how to prove it. I think part of the problem I'm having here is defining n as a integer not divisible by 3.

    Any help on any of those would be appreciated.


    Last edited: Mar 10, 2010
  2. jcsd
  3. Mar 10, 2010 #2
    Actually I might of made some headway on number 4.

    If x^2=x then x=x/x. So x/x will always reduce to 1 unless x=0.

    Is this sufficient for a proof?
  4. Mar 10, 2010 #3


    Staff: Mentor

    You're likely to get more responses if you put each problem in itw own thread, rather than posting a whole slew of them all at once.
  5. Mar 10, 2010 #4


    Staff: Mentor

    Which is it? x^2 = 0 or x^2 = x?
  6. Mar 10, 2010 #5
    It is x^2=x
  7. Mar 10, 2010 #6


    Staff: Mentor

    For 5, if n is an integer not divisible by 3, then its remainder when divided by 3 has to be either 1 or 2. I.e., n = 1 mod 3 or n = 2 mod 3.

    Investigate each case to say something about n^2.
  8. Mar 11, 2010 #7

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook