Proving Congruence: (p-1, k) ≡ (-1)^k (mod p)

  • Thread starter katatonia
  • Start date
Then, assuming that for any k, the combination \binom{p-1}{k} is congruent to (-1)^k (mod p), it follows that for k+1:\binom{p-1}{k+1} = \frac{p-k-1}{k+1}\binom{p-1}{k} =\frac{p-k-1}{k+1}(-1)^kIn summary, for each odd prime p and for each k such that 0<= k <=(p-1), the combination (p-1, k) is congruent to (-1)^k (mod p). This can be proven using induction and the binomial theorem.
  • #1
katatonia
2
0
Anybody know how to do this one:

For each odd prime p and for each k such that 0<= k <=(p-1), prove that:

the combination (p-1, k) is congruent to (-1)^k (mod p)




Any help would be great.
 
Physics news on Phys.org
  • #2
What is "the combination"?
 
  • #3
I'm guessing the 'combination' is referring to the binomial coefficient.

In that case consider (x+y)^p mod p. Expand/simplify it in a couple ways, using the fact that p is prime (Fermat's little theorem) and then using the binomial theorem on (x+y)(x+y)^(p-1). Then compare coefficients.
 
  • #4
combination(p-1, k) = [(p-1)!]/ [k!*(p-1-k)!]

sorry if i didn't make sense :)
 
  • #5
In other words...

[tex]
\binom{p-1}{k} = \frac{p-1}{1} \frac{p-2}{2} \cdots \frac{p-k}{k}
[/tex]

...
 
  • #6
Going back to the originial question, Does anybody know how to do this one? The answer is that you use induction. The basis will work for 0 giving:

[tex]\frac{(p-1)!}{0!(p-1)!} =1=(-1)^0 [/tex]
 

Related to Proving Congruence: (p-1, k) ≡ (-1)^k (mod p)

1. What does "mod p" mean in the equation (p-1, k) ≡ (-1)^k (mod p)?

In mathematics, "mod p" stands for "modulo p" and is used to denote the remainder when dividing by the number p. In this equation, it means that the expression on the left side is congruent to the expression on the right side modulo p.

2. How do you prove the congruence (p-1, k) ≡ (-1)^k (mod p)?

To prove this congruence, we can use the definition of congruence which states that two numbers are congruent modulo p if their difference is a multiple of p. So, we can subtract (-1)^k from (p-1, k) and show that the result is a multiple of p. This can be done using algebraic manipulation and properties of exponents.

3. Can you provide an example to illustrate this congruence?

Sure, let's take p = 7 and k = 3. Then, (p-1, k) ≡ (7-1, 3) ≡ (6, 3) ≡ 3 (mod 7). And (-1)^k ≡ (-1)^3 ≡ -1 (mod 7). Thus, (p-1, k) ≡ (-1)^k (mod p) is satisfied for p = 7 and k = 3.

4. Is this congruence always true for any values of p and k?

Yes, this congruence is always true for any values of p and k. This is because the expression on the left side, (p-1, k), is simply the greatest common divisor of p-1 and k, which is always a factor of both numbers. And on the right side, (-1)^k is always a multiple of p, since (-1)^k = 1 if k is even and -1 if k is odd. Therefore, the difference between the two expressions will always be a multiple of p, satisfying the definition of congruence.

5. How is this congruence used in mathematics?

This congruence is used in various areas of mathematics, including number theory and cryptography. In number theory, it is used to study properties of prime numbers and their factors. In cryptography, it is used to generate public and private keys for encryption algorithms. It also has applications in other fields such as computer science and physics.

Similar threads

  • Linear and Abstract Algebra
Replies
2
Views
921
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
928
  • Linear and Abstract Algebra
Replies
2
Views
982
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
20
Views
3K
  • Linear and Abstract Algebra
Replies
2
Views
1K
Back
Top