Binomial coefficient modulo a prime

In summary, a binomial coefficient modulo a prime is a mathematical concept used to find the remainder when a binomial coefficient is divided by a prime number. It is important in various applications such as cryptography, coding theory, and probability. The most common method for calculating it is using Lucas' Theorem, but other methods include using modular arithmetic and the extended Euclidean algorithm. Using a prime number in binomial coefficients modulo a prime simplifies the calculation process and ensures a unique result. Binomial coefficients modulo a prime are always positive and can be calculated by adding the prime number to a negative remainder until it becomes positive.
  • #1
erszega
36
0
A question:

Let bin(a,b) denote the binomial coefficient a! / ( b! (a - b)! ).

Is it true that

bin( 2p, p ) = 2 (mod p) if p is prime and p>=3 ?
 
Physics news on Phys.org
  • #2
Yes, it's fermat's little theorem: x^p=x mod p, for p a prime, hence

(1+x)^2p = (1+x^p)^2 = 1+2x^p+x^{2p} mod p

note your requirement on p>=3 is not necessary. 4 choose 2 =6 whcih is congruent to 2 mod 2 as well.
 
  • #3


Yes, it is true that bin(2p, p) = 2 (mod p) if p is prime and p>=3. This is known as Lucas's Theorem, which states that for any prime number p and any non-negative integers n and k, the binomial coefficient bin(n,k) is congruent to the product of the binomial coefficients bin(n_i, k_i) modulo p, where n_i and k_i are the base p expansions of n and k respectively. In this case, since p is prime, the base p expansion of 2p is (2,0) and the base p expansion of p is (1,0), so the product of the binomial coefficients is (2,0)*(1,0) = (2,0) = 2 (mod p). Therefore, bin(2p, p) is congruent to 2 modulo p.
 

1. What is a binomial coefficient modulo a prime?

A binomial coefficient modulo a prime is a mathematical concept that involves finding the remainder when a binomial coefficient (also known as a combination) is divided by a prime number. It is often used in number theory and combinatorics.

2. Why is finding binomial coefficients modulo a prime important?

Finding binomial coefficients modulo a prime can be useful in various applications, such as cryptography, coding theory, and probability. It can also help in solving problems related to prime numbers and modular arithmetic.

3. How do you calculate a binomial coefficient modulo a prime?

The most common method for calculating a binomial coefficient modulo a prime is using the Lucas' Theorem, which states that the binomial coefficient mod p is equivalent to the product of the binomial coefficients mod p of each individual term in the expansion. Other methods include using the properties of modular arithmetic and the extended Euclidean algorithm.

4. What is the significance of using a prime number in binomial coefficients modulo a prime?

Using a prime number in binomial coefficients modulo a prime is significant because it simplifies the calculation process and ensures that the result is unique. This is because prime numbers only have two factors (1 and itself), making it easier to determine the remainder when dividing by the prime.

5. Can binomial coefficients modulo a prime be negative?

No, binomial coefficients modulo a prime are always positive. This is because the remainder of a division operation is always a non-negative integer. If the result is negative, we can add the prime number to it until the remainder becomes positive.

Similar threads

  • Linear and Abstract Algebra
Replies
5
Views
877
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
730
  • Linear and Abstract Algebra
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
760
  • Precalculus Mathematics Homework Help
Replies
16
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
622
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
992
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top