# Homework Help: Number theory problem

1. Feb 19, 2013

### d4rkwarrior

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 $\equiv 13 (mod 100)$. Also the sum has to be greater than 100, but from here I am stuck. What do I do?

2. Feb 19, 2013

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

3. Feb 19, 2013

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

4. Feb 19, 2013

### d4rkwarrior

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.

5. Feb 19, 2013

### micromass

Since $100=2^25^2$, you could check what happens in mod 4.

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

$$1+2+3+4+5+...+n = 1+2+3+4+(4+1)+(4+2)+...$$

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

Last edited by a moderator: Feb 19, 2013
6. Feb 19, 2013

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

7. Feb 19, 2013

### Staff: Mentor

That is really cool. I learned something new today!

8. Feb 20, 2013

### d4rkwarrior

micromass; how can I continue from here? By using mod 4, the sum, S, will be:

S $\equiv 0, 1, 2, 3 (mod 4)$. Also, 13 $\equiv 1 (mod 4)$ How do I exclude the possibility of S $\equiv 1 (mod 4)$?

9. Feb 20, 2013

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

10. Feb 20, 2013

### d4rkwarrior

But how do I prove that? What method can I use?

11. Feb 20, 2013

### Staff: Mentor

Find them by testing, and prove them by considering appropriate sums?

12. Feb 20, 2013

### haruspex

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.