1. Not finding help here? Sign up for a free 30min 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!

Number theory problem

  1. Feb 19, 2013 #1
    1. The problem statement, all variables and given/known data

    Does there exist an integer n, such that 1+2+3+...+n, ends with the last two digits 13?

    2. Relevant equations

    1+2+3+...+n = n(n+1)/2

    3. The attempt at a solution

    I reached a conclusion that 1+2+3+...+n [itex]\equiv 13 (mod 100)[/itex]. Also the sum has to be greater than 100, but from here I am stuck. What do I do?
     
  2. jcsd
  3. Feb 19, 2013 #2

    berkeman

    User Avatar

    Staff: Mentor

    A quick check with Excel sure seems to imply that there is no such n, but maybe in the higher numbers... What math techniques are you supposed to be using for this proof/disproof?
     
  4. Feb 19, 2013 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You could begin with the last digit, this is easier to study. Afterwards, including the first digit should work in a similar way.
     
  5. Feb 19, 2013 #4
    I am supposed to prove it by congruences, and by the way showing that it is impossible with last digit can't prove it's impossible with two, not even in a similar way. And I have to prove that it is IMPOSSIBLE or possible for certain values of n.
     
  6. Feb 19, 2013 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Since [itex]100=2^25^2[/itex], you could check what happens in mod 4.

    Which values will the sequence 1+...+n take in (mod 4)?? You can always write

    [tex]1+2+3+4+5+...+n = 1+2+3+4+(4+1)+(4+2)+...[/tex]

    So can you give a full classification of the sequence in (mod 4)?

    What about mod 25?
     
    Last edited by a moderator: Feb 19, 2013
  7. Feb 19, 2013 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The last digit can be 3. But those occurences are quite limited, and you can verify that the last digits will never be 13 at those.
    If the last digit would never be 3, this would be sufficient for the proof.
     
  8. Feb 19, 2013 #7

    berkeman

    User Avatar

    Staff: Mentor

    That is really cool. I learned something new today! :smile:
     
  9. Feb 20, 2013 #8
    micromass; how can I continue from here? By using mod 4, the sum, S, will be:

    S [itex]\equiv 0, 1, 2, 3 (mod 4)[/itex]. Also, 13 [itex]\equiv 1 (mod 4)[/itex] How do I exclude the possibility of S [itex]\equiv 1 (mod 4)[/itex]?
     
  10. Feb 20, 2013 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    You cannot exclude it in this step - the sum will be 1 mod 4 sometimes. The question is: Can it be 13 mod 25 at the same time?
     
  11. Feb 20, 2013 #10
    But how do I prove that? What method can I use?
     
  12. Feb 20, 2013 #11

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Find them by testing, and prove them by considering appropriate sums?
     
  13. Feb 20, 2013 #12

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You want to know whether/when n(n+1)/2 ≡ 13 (mod 25). Suppose it is. Simplify that, and get the LHS into a perfect square.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Number theory problem
  1. Number theory problem (Replies: 6)

  2. Number theory problem (Replies: 1)

  3. Number theory problem (Replies: 9)

Loading...