Is 1+2+3+4+...+(n-1) divisible by N (odd positive integer)?

  • Thread starter Thread starter Isaak DeMaio
  • Start date Start date
  • Tags Tags
    Induction Proof
Click For Summary

Homework Help Overview

The discussion revolves around proving a statement related to the sum of the first (n-1) integers and its divisibility by an odd positive integer N. Participants are exploring how to show that the sum 1 + 2 + 3 + ... + (n-1) is congruent to 0 modulo N, particularly using induction as a method of proof.

Discussion Character

  • Exploratory, Mathematical reasoning, Problem interpretation, Assumption checking

Approaches and Questions Raised

  • Participants are discussing the use of induction to prove the statement, with some suggesting to express N as 2k + 1 for an integer k. Others are questioning how to handle the modulus and whether certain expressions are valid. There are attempts to clarify the induction steps and the base case, with some participants expressing confusion about the setup and the relationships between the variables involved.

Discussion Status

The discussion is ongoing, with various approaches being explored. Some participants have provided insights into the induction process and the necessary steps, while others are still seeking clarity on specific points. There is no explicit consensus yet, but several productive lines of reasoning have been introduced.

Contextual Notes

Participants note that the problem has not been covered in their coursework, and there are indications of uncertainty regarding the definitions and properties of modular arithmetic. The discussion includes attempts to relate the problem to known mathematical principles and previous examples.

  • #31
Isaak DeMaio said:
So it would be 3k=0(mod k+2)
No. Where are you getting that?
Isaak DeMaio said:
Could you subtract the K over to get 2k=0(mod2)?
then would that be it?

No, it doesn't work that way.

Start with 1 + 2 + 3 + ... + (k - 1) + k + (k + 1).
Use what you know (have assumed) about 1 + 2 + 3 + ... + (k - 1), to show that the expression above is congruent to 0 (mod k + 2).
 
Physics news on Phys.org
  • #32
Isaak DeMaio said:
So I should follow this:

The general statement:
n is a positive odd integer
Show that 1 + 2 + 3 + ... + (n - 1) 0 (mod n)

Base case:
1 + 2 = 3 0 (mod 3)
This establishes the base case.

Induction step:
Let n = k
Assume that 1 + 2 + 3 + ... + (k - 1) = 0 (mod k) is true. (*)

Now let n = k + 2 (to get to the next odd number)
Show that 1 + 2 + 3 + ... + (k - 1) + k + (k + 1) = 0 (mod k + 2).

Then try and prove it to get the correct answer?

Would it be:

0 (mod k) + k + (k+1) = 0 (mod k + 2)

Then:

0(mod k) + 2k + 1 = 0 (mod k+2)
 
  • #33
Isaak DeMaio said:
Would it be:

0 (mod k) + k + (k+1) = 0 (mod k + 2)

Then:

0(mod k) + 2k + 1 = 0 (mod k+2)
They are both equivalent, but you need to establish that these equations are true, not just write them down. Again, start with 1 + 2 + 3 + ... + (k - 1) + k + (k + 1). By that, I mean that this should be the first thing you write down. Then write an =. Then use what you know (have assumed) about 1 + 2 + 3 + ... + (k - 1), to show that the expression above is congruent to 0 (mod k + 2).
 
Last edited:
  • #34
Isaak DeMaio said:
Would it be:

0 (mod k) + k + (k+1) = 0 (mod k + 2)

Then:

0(mod k) + 2k + 1 = 0 (mod k+2)
Isaak DeMaio,

It appears that you continue to be confused by modular arithmetic --- or at least by the notation.

For this problem the context is:
The statement "a ≡ b (mod c)" is read as "a is congruent to b mod c."
It means that there is an integer, k, such that a ‒ b = k·c​

On the other hand:
"mod" may also be used in the context of a mathematical operation.
Sometimes it is written as (27 mod 7) other times: mod(27, 7). In either case the result is 6. It's basically the remainder when doing division (in this case 27÷7), especially with integers.​


So, when you write:
0 (mod k) + k + (k+1) = 0 (mod k + 2),
it's not clear what you mean.
0 (mod k) is (congruent to) zero.
You're left with: k + (k+1) = 0 (mod k + 2)
Do you mean: k + (k+1) is congruent to 0 mod(k+2) .
or --- since 0 (mod k + 2) =0, as a mathematical operation,
Do you mean: k + (k+1) = 0 ?​
 
  • #35
well would it be 2k+1 = 0 mod(k+2)
I don't know what I mean, which is why I asked the question. I've never done a induction proof with mod before.
 
  • #36
Here's what I said in post #33. Did you see it?

Again, start with 1 + 2 + 3 + ... + (k - 1) + k + (k + 1). By that, I mean that this should be the first thing you write down. Then write an =. Then use what you know (have assumed) about 1 + 2 + 3 + ... + (k - 1), to show that the expression above is congruent to 0 (mod k + 2).​

Instead at continuing to guess at things you think might be the key to this problem (they aren't), follow the steps in the paragraph above.
 
  • #37
that is the first thing I wrote down...

1 + 2 + 3 + ... + (k - 1) + k + (k + 1)

=

don't i know that 0 (mod k+2) will be equal to that?
 
  • #38
Isaak DeMaio said:
that is the first thing I wrote down...
But you didn't write it in your posts, and that is what I was asking for.
Isaak DeMaio said:
1 + 2 + 3 + ... + (k - 1) + k + (k + 1)

=


don't i know that 0 (mod k+2) will be equal to that?
And that's what you have to prove.

In the equation above, you can replace all but the last two terms with something. So you will have

1 + 2 + 3 + ... + (k - 1) + k + (k + 1)
= <something> + k + (k + 1)

What can you put in place of <something> above?
 
  • #39
Mark44 said:
But you didn't write it in your posts, and that is what I was asking for.

And that's what you have to prove.

In the equation above, you can replace all but the last two terms with something. So you will have

1 + 2 + 3 + ... + (k - 1) + k + (k + 1)
= <something> + k + (k + 1)

What can you put in place of <something> above?

0 (mod k +2)?
 
  • #40
No.

What do you know about 1 + 2 + 3 + ... + (k - 1)?
 
  • #41
2k+1 comes after it.
 
  • #42
Presumably you've done at least one other proof by induction. If so, you have made an assumption about the value of 1 + 2 + 3 + ... + (k - 1). That value is what you replace this expression by.
 
  • #44
and every other time I done it how I am saying but apparently I've been doing it wrong and getting the right answer.
 
  • #45
that's what I have been saying is it not?
 
  • #46
Now let n = k + 2 (to get to the next odd number)
Show that 1 + 2 + 3 + ... + (k - 1) + k + (k + 1) 0 (mod k + 2).

0 (mod k) + 2k+1 = 0 (mod k+2)
 
  • #47
Isaak DeMaio said:
and every other time I done it how I am saying but apparently I've been doing it wrong and getting the right answer.
There isn't a "right answer" like x = 3 when you do a proof.
 
  • #48
Mark44 said:
There isn't a "right answer" like x = 3 when you do a proof.

I know Sherlock.
 
  • #49
Isaak DeMaio said:
Now let n = k + 2 (to get to the next odd number)
Show that 1 + 2 + 3 + ... + (k - 1) + k + (k + 1) 0 (mod k + 2).

0 (mod k) + 2k+1 = 0 (mod k+2)
From the induction hypothesis, you have assumed that 1 + 2 + 3 + ... + (k - 1) \equiv 0 (mod k).

What does that say about 1 + 2 + 3 + ... + (k - 1) if its remainder when you divide by k is 0?
 
  • #50
k=0 (mod k)
 
  • #51
That's trivially true and irrelevant.

In different words, and without using mod, modulo, etc, what does this equation, 1 + 2 + 3 + ... + (k - 1) \equiv
0 (mod k) mean?
 
  • #52
they're congruent.
 
  • #53
You are using "mod" by implication when you say congruent.

Another tack: what is 1 + 2 + 3 + ... + (k - 1) equal to? I'm am NOT asking what it's congruent to. I already know the answer to that.
 
  • #54
As a side note, do you HAVE to prove by induction? Or did your instructor just mention this as a possible mode of attack?
 
  • #55
Mark44 said:
You are using "mod" by implication when you say congruent.

Another tack: what is 1 + 2 + 3 + ... + (k - 1) equal to? I'm am NOT asking what it's congruent to. I already know the answer to that.

Right. This has probably already been said several times at some point in this endless thread. But attacking this problem directly by induction is a mess. Proving 1+2+3+...+k=k*(k+1)/2 is easy to prove by induction. Now forget the induction, you already used it. Now attack the problem using that. We all knew this, right? Maybe best to say so in so many words.
 
  • #56
Yes by Induction Robert.

Why can't you just tell me?
 
  • #57
Isaak DeMaio said:
Yes by Induction Robert.

Why can't you just tell me?

Why can't I just tell you
1) It is against PF rules.
2) I don't want to.
3) You seem completely unwilling to learn what modular arithmetic is
4) and this is most important, I haven't figured out how to do this via induction. And you know what? I'm not going to, either. Mark44 and SammyS seem to have worked it out, so I would just follow his advice.


The only "inductive" proof I can think of is using induction to prove what 1+2+...+(k-1) is equal to. Then showing that k divides 1 + 2 + ... + (k-1), which is what the previous poster suggested doing, and if I was turning this assignment in, I would do exactly that.


You said in another thread that this is for a number theory class; I was wondering, what is your major? Is it CS, by any chance?
 
  • #58
Dick said:
Right. This has probably already been said several times at some point in this endless thread. But attacking this problem directly by induction is a mess. Proving 1+2+3+...+k=k*(k+1)/2 is easy to prove by induction. Now forget the induction, you already used it. Now attack the problem using that. We all knew this, right? Maybe best to say so in so many words.

That is what I did, though I didn't use induction to prove 1+2+3+...+k=k*(k+1)/2, I just sort of took that for granted. Then it is pretty easy to show what you need to show. But, it seems that Mark44 has done this using a direct inductive argument, is that correct Mark44? I haven't come up with one, but I haven't really given it much thought and I doubt I will.
 
  • #59
Robert1986 said:
Why can't I just tell you
1) It is against PF rules.
2) I don't want to.
3) You seem completely unwilling to learn what modular arithmetic is
4) and this is most important, I haven't figured out how to do this via induction. And you know what? I'm not going to, either. Mark44 and SammyS seem to have worked it out, so I would just follow his advice.


The only "inductive" proof I can think of is using induction to prove what 1+2+...+(k-1) is equal to. Then showing that k divides 1 + 2 + ... + (k-1), which is what the previous poster suggested doing, and if I was turning this assignment in, I would do exactly that.


You said in another thread that this is for a number theory class; I was wondering, what is your major? Is it CS, by any chance?

Not the answer just what the hell I am not understanding. Why would you divide it all by K, that makes no sense at all.

Math Education
 
  • #60
Isaak DeMaio said:
Not the answer just what the hell I am not understanding. Why would you divide it all by K, that makes no sense at all.

Math Education

Ok, nothing is being divided by K, I'm not sure what you are referring to, perhaps I made a typo somewhere.

if 1 + 2 + ... + k = k(k+1)/2, what can you conclude?
 

Similar threads

Each integer n>11 can be written as the sum of two composite numbers?
  • · Replies 7 ·
Replies
7
Views
4K
Prove by induction or otherwise, that ##\sum_{r=1}^n r(3r-1)=n^3+n^2##
  • · Replies 20 ·
Replies
20
Views
2K
Every integer of the form n^4+4, with n>1, is composite?
  • · Replies 4 ·
Replies
4
Views
2K
Show that k is an odd integer, except when k=2
  • · Replies 9 ·
Replies
9
Views
2K
Prove n^2+2^n Composite if n not 6k+3
  • · Replies 30 ·
2
Replies
30
Views
4K
An integer n>1 is square-free if and only if?
  • · Replies 13 ·
Replies
13
Views
4K
If ## p\neq5 ## is an odd prime, prove that either ## p^{2}-1 ## or....
  • · Replies 15 ·
Replies
15
Views
4K
Every integer n>1 is the product of a square-free integer?
  • · Replies 5 ·
Replies
5
Views
4K
Proofs By Induction: Proving P(n) for All n
  • · Replies 3 ·
Replies
3
Views
2K
Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
  • · Replies 3 ·
Replies
3
Views
2K