Physics Forums (http://www.physicsforums.com/index.php)
-   Calculus & Beyond Homework (http://www.physicsforums.com/forumdisplay.php?f=156)
-   -   1 + 2 + 3 +...+ (p-1)(mod p) (http://www.physicsforums.com/showthread.php?t=593194)

 teddyayalew Apr3-12 07:00 PM

1 + 2 + 3 +...+ (p-1)(mod p)

1. The problem statement, all variables and given/known data
What is the value of 1 + 2 + 3 +...+ (p-1)(mod p)?

2. Relevant equations

p = 0 (mod p)
p-1 = -1 (mod p)
1 + 2 + 3 + ...+n = n(n+1)/2

3. The attempt at a solution

I know 1 + 2 + 3 +...+ (p-1) = (p-1)(p)/2

I worked the problem, but i don't know if i am correct:

work: i am looking for a b s.t.

b = (p-1)(p)/2 (mod p) or 2b = (p-1)(p) ( mod p)
we know (p-1) = -1 (mod p)
so : (p-1)p = -p (mod p)
this implies : 2b = -p(mod p) ,also we know p = 0 (mod p) so b =0 (mod p)

So the answer is 1 + 2 + 3 +...+ (p-1) = 0 (mod p)

 Mark44 Apr3-12 07:19 PM

Re: 1 + 2 + 3 +...+ (p-1)(mod p)

Quote:
 Quote by teddyayalew (Post 3848722) 1. The problem statement, all variables and given/known data What is the value of 1 + 2 + 3 +...+ (p-1)(mod p)? 2. Relevant equations p = 0 (mod p) p-1 = -1 (mod p) 1 + 2 + 3 + ...+n = n(n+1)/2 3. The attempt at a solution I know 1 + 2 + 3 +...+ (p-1) = (p-1)(p)/2 I worked the problem, but i don't know if i am correct: work: i am looking for a b s.t. b = (p-1)(p)/2 (mod p) or 2b = (p-1)(p) ( mod p) we know (p-1) = -1 (mod p) so : (p-1)p = -p (mod p) this implies : 2b = -p(mod p) ,also we know p = 0 (mod p) so b =0 (mod p) So the answer is 1 + 2 + 3 +...+ (p-1) = 0 (mod p)
I get different answers depending on whether p is even or odd.

For example, if p = 6, 1 + 2 + 3 + 4 + 5 ##\equiv## 3 (mod 6).

If p = 5, 1 + 2 + 3 + 4 ##\equiv## 0 (mod 5).

 Mark44 Apr3-12 07:21 PM

Re: 1 + 2 + 3 +...+ (p-1)(mod p)

BTW, what you're calculating is (1 + 2 + ... + (p -1))(mod p).

 teddyayalew Apr3-12 08:23 PM

Re: 1 + 2 + 3 +...+ (p-1)(mod p)

Mark, I am sorry I was not clear, when I say p I mean a prime number.

 Mark44 Apr3-12 08:32 PM

Re: 1 + 2 + 3 +...+ (p-1)(mod p)

How about if p = 2, the only even prime?

1 ≠ 0 (mod 2)

 Robert1986 Apr3-12 08:34 PM

Re: 1 + 2 + 3 +...+ (p-1)(mod p)

Well, you have the right idea by writting
$$1+2+\cdots+(p-1) = \frac{(p-1)p}{2}$$

But then you sort of take the long route to the eventual answer.

When you have this:
$$1 + \cdots + (p-1) = \frac{(p-1)p}{2}$$

just note that $p-1$ is even so that $(p-1)/2$ is an integer. Thus, the sum is divisible by $p$ and so the answer is $0$.

EDIT:
As Mark mentioned, you'll have to do a special case for 2. In fact, this happens a lot in Number Theory.

 teddyayalew Apr3-12 08:48 PM

Re: 1 + 2 + 3 +...+ (p-1)(mod p)

I see.
So if p=2 then I know the sum is : 1 + 1 = 2, which is congruent to 0 mod 2 as well.

Thank you both for you help!

 Mark44 Apr3-12 08:51 PM

Re: 1 + 2 + 3 +...+ (p-1)(mod p)

Quote:
 Quote by teddyayalew (Post 3848892) I see. So if p=2 then I know the sum is : 1 + 1 = 2, which is congruent to 0 mod 2 as well. Thank you both for you help!
No. If p = 2, the sum has only one term (you quit at 2 - 1 = 1).

 All times are GMT -5. The time now is 08:16 AM.