# Prove Polynomial Congruence $(x+y)^n \equiv x^n + y^n$ (mod $p$)

• MHB
• lfdahl
In summary, a polynomial congruence is when two polynomials are equivalent modulo a given number, usually a prime number. The notation $(x+y)^n \equiv x^n + y^n$ (mod $p$) means that the polynomials on either side are equivalent modulo $p$. One way to prove polynomial congruences is using the Binomial Theorem and the fact that $p$ divides all binomial coefficients. Proving polynomial congruences is important in number theory and algebra, and there are other important ones such as Fermat's Little Theorem and Euler's Theorem.
lfdahl
Gold Member
MHB
Given a prime number $p$, prove that the polynomial congruence
$(x + y)^n \equiv x^n + y^n$ (mod $p$) is true if and only if $n$ is a power of $p$.

Hint:

Define the polynomial: $$P(x,y) = (x+y)^n-x^n-y^n = \sum_{k=1}^{n-1}{ n\choose k }x^ky^{n-k}$$

Consider the two cases:

(i). $n = p^a$

(ii). $n$ is not a power of $p$.

Suggested solution:

Let $P(x,y) = (x+y)^n-x^n-y^n = \sum_{k=1}^{n-1}\binom{n}{k}x^{k}y^{n-k}.$

(a). If $n = p^a$, then all the coefficients of $P$ are divisible by $p$.
Proof: For $1 \leq j \leq p^a-1$, $\binom{p^a}{j}=\frac{p^a}{j}\binom{p^a-1}{j-1}.$
If $j = rp^b$, where $gcd(r,p)=1$, then $\frac{p^a}{j}=\frac{p^{a-b}}{r}$, where $a-b \geq 1$ (since $j < p^a$). Thus $r$ must divide $\binom{p^a-1}{j-1}$ (since $\binom{p^a}{j}$ is an integer), and $\binom{p^a}{j}$ is divisible by $p^{a-b}$.

(b). If $n$ is not a power of $p$, then not all $\binom{n}{j}$ are divisible by $p$.
Proof: For $p^a < n < p^{a+1}$, let $c = n – p^a$ so $0 < c < p^a(p-1)$. Then $\binom{n}{c} = \binom{p^a+c}{c} = \prod_{j=1}^{c}\frac{p^a+j}{j}$. If $j = rp^b$, where $gcd(r,p) = 1$ and $b<a$, then $\frac{p^a+j}{j} = \frac{p^{a-b}+r}{r}$. From this $\binom{n}{c}$ equals a product of fractions none of whose numerators is a multiple of $p$.

## What is a polynomial congruence?

A polynomial congruence is a mathematical concept that states that two polynomials are equivalent modulo a given number, usually a prime number. In simpler terms, it means that the remainder when dividing one polynomial by the other is equal to 0.

## What does the notation $(x+y)^n \equiv x^n + y^n$ (mod $p$) mean?

The notation $(x+y)^n \equiv x^n + y^n$ (mod $p$) means that the polynomials on either side of the congruence are equivalent modulo the prime number $p$. In other words, when dividing $(x+y)^n$ by $x^n + y^n$, the remainder will always be 0 when taken modulo $p$.

## How can we prove the polynomial congruence $(x+y)^n \equiv x^n + y^n$ (mod $p$)?

One way to prove this polynomial congruence is by using the Binomial Theorem and the fact that $p$ divides all binomial coefficients ${n \choose k}$ where $0 < k < n$. This will show that all terms in $(x+y)^n$ are divisible by $p$, thus leaving a remainder of 0 when taken modulo $p$.

## What is the significance of proving polynomial congruences?

Proving polynomial congruences is important in number theory and algebra as it allows us to solve equations and systems of equations in a more efficient manner. It also helps us understand the structure and behavior of polynomials when taken modulo a given number, which has practical applications in fields such as coding theory and cryptography.

## Are there any other important polynomial congruences?

Yes, there are many other important polynomial congruences, such as the Fermat's Little Theorem, which states that $a^p \equiv a$ (mod $p$) for any integer $a$ and prime number $p$. Another important one is the Euler's Theorem, which is a generalization of Fermat's Little Theorem and states that $a^{\phi(n)} \equiv 1$ (mod $n$) where $n$ is any positive integer and $\phi(n)$ is Euler's totient function.

Replies
2
Views
1K
Replies
96
Views
10K
Replies
8
Views
2K
Replies
1
Views
1K
Replies
1
Views
279
Replies
2
Views
998
Replies
1
Views
810
Replies
1
Views
1K
Replies
1
Views
974
Replies
1
Views
1K