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

Click For Summary

Homework Help Overview

The discussion revolves around determining whether there exists an integer n such that the sum of the first n integers, represented as 1+2+3+...+n, ends with the last two digits 13. The mathematical formulation used is the equation for the sum, n(n+1)/2, and the problem is situated within the context of number theory and modular arithmetic.

Discussion Character

  • Exploratory, Assumption checking, Mathematical reasoning

Approaches and Questions Raised

  • Participants discuss the congruence condition n(n+1)/2 ≡ 13 (mod 100) and explore implications of this condition. Some suggest starting with simpler cases, such as examining the last digit or using modular arithmetic with mod 4 and mod 25. Others express uncertainty about how to proceed from their current conclusions and seek clarification on methods for proving or disproving the existence of such an n.

Discussion Status

The discussion is active, with various participants exploring different modular approaches and questioning the assumptions involved in the problem. Some have provided insights into the behavior of the sum under different moduli, while others are seeking further guidance on how to structure their proofs or disproofs.

Contextual Notes

Participants note that the sum must be greater than 100 and that proving impossibility for the last digit does not necessarily extend to the last two digits. There is an emphasis on the need for rigorous proof through congruences, and some participants express the challenge of excluding certain possibilities based on modular results.

d4rkwarrior
Messages
4
Reaction score
0

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 [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?
 
Physics news on Phys.org
d4rkwarrior said:

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

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?
 
You could begin with the last digit, this is easier to study. Afterwards, including the first digit should work in a similar way.
 
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.
 
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:
d4rkwarrior said:
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.
 
micromass said:
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?

That is really cool. I learned something new today! :smile:
 
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]?
 
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
But how do I prove that? What method can I use?
 
  • #11
Find them by testing, and prove them by considering appropriate sums?
 
  • #12
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.
 

Similar threads

For ## n\geq 1 ##, use congruence theory to establish?
  • · Replies 2 ·
Replies
2
Views
1K
Show that ## (-13)^{n+1}\equiv (-13)^{n}+(-13)^{n-1}\pmod {181} ##?
  • · Replies 1 ·
Replies
1
Views
2K
For n>3, show that the integers n, n+2, n+4 cannot all be prime
  • · Replies 27 ·
Replies
27
Views
4K
Prove that ## 7, 11 ##, and ## 13 ## all divide ## N ##
  • · Replies 6 ·
Replies
6
Views
2K
Prove: If the integer ## a ## is not divisible by ## 2 ## or ## 3 ##....
  • · Replies 9 ·
Replies
9
Views
3K
Finding Integer with Chinese Remainder Theorem
  • · Replies 3 ·
Replies
3
Views
2K
For ## n\geq 1 ##, use congruence theory to establish....
  • · Replies 3 ·
Replies
3
Views
1K
Prove that ## a^{({2}^{n})}\equiv 1\pmod {2^{n+2}} ## for any ##n##?
  • · Replies 6 ·
Replies
6
Views
3K
Show that ## 2^{n} ## divides an integer ## N ##.
  • · Replies 6 ·
Replies
6
Views
3K
Find the values of ## n\geq 1 ## for which ## 1+2+3+\dotsb +n ##.
  • · Replies 4 ·
Replies
4
Views
2K