Number Theory Problem: Finding an Integer n for 1+2+3+...+n to End in 13

[d4rkwarrior]

Homework Statement

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

Homework Equations

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

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?

 

[berkeman]

Homework Statement

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

Homework Equations

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

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?

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?

 

[mfb]

You could begin with the last digit, this is easier to study. Afterwards, including the first digit should work in a similar way.

 

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

 

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

What about mod 25?

 

[mfb]

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.

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.

 

[berkeman]

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

What about mod 25?

That is really cool. I learned something new today!

 

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

 

[mfb]

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?

 

[d4rkwarrior]

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

 

[mfb]

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

 

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