Question

Question: "For which n does the expression 1+2+...+(n-1) congruent to 0(mod n) hold?"

If I am reading this correctly, for the expression 0 is the least positive residue of (1+2+...+(n-1))(mod n). However, if that is correct, I am not sure where to go from there. Would n be 0 or 1 then? Or something else entirely?

Answer 1

let's look at some examples
let's say n is 1...
then you have 0 congruent to 0 mod 1

let's say n is 2
then you have 0+1 congruent to 0 mod 2 which is false

let's say n is 3
what happens?

Answer 2

Then if n=3, it would be 1+2=3 congruent to 0mod3, which would be true then, aye?

Answer 3

yes
so let's look at the more general thing
you have
0+1+2+3+...+(n-1)
or
1+2+3+...+(n-1)
or
1+(n-1)
+
2+(n-2)
+
3+(n-3)
+.....

now I can pair the terms of the sum up if there are an even amount of terms
by the way
you do know that k+(n-k) is n right?
so each of those rows I wrote have sum n
and what is n mod n

Answer 4

for example
n=4
gives
1+2+3
which doesn't have a odd amount of terms
you have (1+3)+2

for n=5
you have
1+2+3+4
you have an even amount of terms so we have
(1+4)+(2+3)

for n=6
you have
1+2+3+4+5
or (1+5)+(2+4)+3


...

Answer 5

do you know how to evaluate k+(n-k) mod n?

Answer 6

I do not off the top of my head. I am looking back through my text right now to see if it was mentioned and if so where. As for n(mod n), that would be 0 though, aye?

Answer 7

right and k+(n-k) is n
so k+(n-k) mod n is 0

Answer 8

Ah okay! And if I am understanding pairing up the terms correctly: that is being done to see if the sum is divisible by n, right? For example, for n=6, that would be false because it has an extra 3, aye?

Answer 9

right and 3 mod 6 isn't 0

Answer 10

6+6+3=3 but 3 mod 6 isn't 0

Answer 11

if you have an even amount of terms in your sum you can pair them up and such away you
have n+n+n+n+...+n mod n

Answer 12

I think I also have another way to look at it too after you get this way

Answer 13

Okay, that makes sense! We did not cover pairing them up like that at all, so that's really useful to know, thank you. And if I am noticing the pattern correctly here, the only n's for which the statement hold thus far are for odd integers as the even ones result in false statements, right?

Answer 14

right

Answer 15

another way:
now \[1+2+3+ \cdots +(n-1)=\frac{n(n-1)}{2} \text{ do you remember this formula }\]

Answer 16

think back to calculus 1 days

Answer 17

if that isn't too far back

Answer 18

\[\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\]

Answer 19

except we have to n-1

Answer 20

Calculus 1 was awhile ago, but that was covered under a section on mathematical induction in this class recently.

Answer 21

\[\sum_{i=1}^{n-1}i=\frac{(n-1)n}{2} \text{ or } \frac{n(n-1)}{2}\]

Answer 22

oh cool

Answer 23

so we can solve this equation
\[\frac{n(n-1)}{2} \equiv 0 \mod n \]

Answer 24

now if n-1 is even then we can cancel out the two's and we are left with
\[\frac{n(2a)}{2} =n a \equiv 0 a \equiv 0 (\mod n)\]

Answer 25

if n-1 is even then n is odd

Answer 26

if n-1 is odd we can't cancel out the 2 on the bottom
but n would be even and n would get destroyed by that division by 2 if you know what I mean so we wouldn't get 0 when modding it by n

Answer 27

you can write the fraction like this:
\[n \frac{n-1}{2} \equiv 0 \mod n \text{ As long as } \frac{n-1}{2} \in \mathbb{Z} \]

Answer 28

Aye, I do. That makes a lot of sense. Thank you for explaining it so well; your explanation was a lot more understandable than the section of the text relating to this problem.

Answer 29

np

Answer 30

you know when (n-1)/2 is an integer right?
I kind of already said but just want to be sure you know

Answer 31

Aye, I do! Can only deal with integers with congruences, right?

Answer 32

well I think you can actually use other numbers

but in number theory yeah I think you only use integers
that is all I ever seen in number theory


n is a positive integer
and...
for (n-1)/2 to be an integer n-1 would have to be even because that is the only sorta of number to be divisible by 2

and if n-1 is even then n is odd since n and n-1 are consecutive integers

Answer 33

Ah okay. This is all relating to brief stint into elementary number theory for this class, so all we have dealt with with problems is either all integers or positive integers/natural numbers, which is why I presumed that. And okay, that makes sense!

Answer 34

anyways glad I can help

Answer 35

Thank you very much for the assistance, I greatly appreciate it!