Intereting Posts

How many bracelets can be formed?
Similarity of real matrices over $\mathbb{C}$
An integral to prove that $\log(2n+1) \ge H_n$
Computing the dimension of a vector space of matrices that commute with a given matrix B,
Difference between the formula of Roger Cotes and Euler
Showing that a root $x_0$ of a polynomial is bounded by $|x_0|<(n+1)\cdot c_{\rm max}/c_1$
Convex sets proof
Functions between topological spaces being continuous at a point?
Minimization of Variational – Total Variation (TV) Deblurring
Compact space T2 satisfies first axiom of countability
Show that the $\mathbb{Z}$-span $\mathbb{Z}b'_1+\cdots+ \mathbb{Z}b'_d$ of $B^+$ does not depend on the choice of $B$
Finitely generated modules over artinian rings have finite length
Absolutely convergent sums in Banach spaces
Group of groups
Prove by induction that… $1+3+5+7+…+(2n+1)=(n+1)^2$ for every $n \in \mathbb N$

Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$

Furthermore, I have been tasked with proving that a stronger version of this holds: $$\binom{ap}{bp}\equiv \binom{a}{b} \pmod{p^2}.$$

I need an elementary proof of this (Lucas’s theorem is out of the question).

I’ve been trying to prove the first inequality using the equivalence $(1 + x)^{ap} \equiv (1 + x)^p \pmod p,$ where $x$ is an integer. I’ve tried to expand $(1+x)^{ap}$ and $(1 + x)^p$ using the binomial theorem and then match coefficients, but I haven’t been able to get the result doing this. How can I prove this first congruence (and the second one)?

- Generating function for binomial coefficients $\binom{2n+k}{n}$ with fixed $k$
- How to show that this binomial sum satisfies the Fibonacci relation?
- Proving Binomial Identity without calculus
- How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$?
- Finding $\lim\limits_{n \to \infty} \sum\limits_{k=0}^n { n \choose k}^{-1}$
- Binomial Sum Related to Fibonacci: $\sum\binom{n-i}j\binom{n-j}i=F_{2n+1}$

Thanks.

- parametric solution for the sum of three square
- Ground plan of Backward direction (<=) - Let $p$ be an odd prime. Prove $x^{2} \equiv -1 \; (mod \, p)$ has a solution $\iff p\equiv 1 \; (mod 4)$
- How to prove: $2^\frac{3}{2}<\pi$ without writing the explicit values of $\sqrt{2}$ and $\pi$
- Can I prove (if $n^2$ is even then $n$ is even) directly?
- Euler function - all values of n give $\phi(n)=10$
- Given $x^3$ mod $55$, find its inverse
- Is that true that all the prime numbers are of the form $6m \pm 1$?
- Move the last two digits in front to multiply by $6$
- Prove a property of the divisor function
- Integers can be expressed as $a^3+b^3+c^3-3abc$

Claim: $$\dbinom{pa}{pb} \equiv \dbinom{a}b \pmod {p^2}$$

Proof:

$$(x+1)^{pa} = (x^p+1+pQ(x))^a$$ for some polynomial $Q$ by the binomial theorem. Then we have

$$(x+1)^{pa} = (x^p+1)^a+a(x^p+1)^{a-1}pQ(x)+p^2f(x)$$ for a polynomial $f$.

This gives

$$(x+1)^{pa} \equiv (x^p+1)^a+a(x^p+1)^{a-1}+pQ(x) \pmod {p^2}.$$

Since $pQ(x) = (x+1)^p-1-x^p$, substitution gives

$$(x+1)^{pa} \equiv (x^p+1)^a+a(x^p+1)^{a-1}((x+1)^p-1-x^p)$$

$$ \equiv (x^p+1)^a+a(x^p+1)^{a-1}(x+1)^p-a(x^p+1)^{a-1}-x^pa(x^p+1)^{a-1}. \pmod {p^2}$$

Now by a simple counting argument, the coefficient of $x^{pb} \pmod {p^2}$ termwise is

$$\dbinom{a}b + a\left(\dbinom{a-1}b+\dbinom{a-1}{b-1}\right)-a\dbinom{a-1}{b}-a \dbinom{a-1}{b-1} \equiv \dbinom{a}b \pmod {p^2}$$

as desired.

It’s pretty cool to see that the terms conspire like that at the end. I think a similar proof would also work for $p^3$. I remember seeing a combinatorial proof for the $p^3$ case somewhere… I can possibly retrieve it if anyone wants me to.

A short proof is given here. But it uses the language of groups acting on sets, you may not be comfortable with that.

- Prove or disprove that if $f$ is continuous function and $A$ is closed, then $\,f$ is closed.
- Why is a straight line the shortest distance between two points?
- Is $\pi \cdot 7$ actually $22$?
- How can prove this $\binom{n}{p}\equiv \left\lfloor\frac{n}{p}\right\rfloor \pmod {p^2}$
- $M$ is a compact manifold with boundary $N$,then $M$ can't retract onto $N$.
- What makes the inside of a shape the inside?
- What is wrong with this fake proof $e^i = 1$?
- To what extent is it possible to generalise a natural bijection between trees and $7$-tuples of trees, suggested by divergent series?
- Could someone tell me how large this number is?
- Find the last two digits of $3^{45}$
- Prove Laurent Series Expansion is Unique
- Why is there no natural metric on manifolds?
- Algorithm for constructing primes
- Gödel's Completeness Theorem and satisfiability of a formula in first-order logic
- No Smooth Onto Map from Circle to Torus