Let $p$ be a prime number and $a, k$ be positive integers such that $p^a<k<2p^a$. Prove that there exists a positive integer $n$ such that \[n<p^{2a}, C_n^k\equiv n\equiv k\pmod {p^a}.\]
Problem
Source: 25 Mar 2013
Tags: modular arithmetic, geometry, geometric transformation, real analysis, number theory proposed, number theory
29.03.2013 20:22
This is false for $a=2, p = 7, k = 56$ Maybe the condition $p \nmid k$ got lost in the translation? If so I can post my solution.
30.03.2013 06:55
Thanks! The question is right. Please check your answer
30.03.2013 07:48
Oh oops, I messed up. I apologize My solution actually works when $p|k$, here it is. Let $c > c'$ be two distinct integers in $0,1,...,p^a-1$. I claim that $\dbinom{k + cp^a}{k} \not \equiv \dbinom{k + c'p^a}{k} \pmod{p^a}$. Note this would imply the problem. To prove this we first prove that if \[\dbinom{z + cp^{a+b}}{k} \not \equiv \dbinom{z + c'p^{a+b}}{k} \pmod{p^{b+1}}\] then $c \equiv c' \pmod{p}$ when $z \equiv k \pmod{p^a}$ and $b \le a-1$. Note that by Vandermonde Convolution: \[\dbinom{z+cp^{a+b}}{k} \equiv \dbinom{z}{k} + \dbinom{z}{k-p^a} \dbinom{cp^{a+b}}{p^a} \pmod{p^{b+1}}\] by the fact that $\frac{n}{\gcd(m,n)}$ divides $\dbinom{n}{m}$. Note that $k - p^a < p^a$, so it follows that $\dbinom{z}{k-p^a} \equiv \dbinom{k}{k-p^a} \equiv \dbinom{k}{p^a} \equiv 1 \pmod{p}$, so it is a unit modulo $p^{b+1}$ so we can cancel it out. Thus we require that \begin{eqnarray*} \dbinom{cp^{a+b}}{p^a} & \equiv & \dbinom{cp^{a+b}}{p^a} \pmod{p^{b+1}} \\ \frac{cp^{a+b}}{p^a} \dbinom{cp^{a+b}-1}{p^a-1} & \equiv & \frac{c'p^{a+b}}{p^a} \dbinom{c'p^{a+b}-1}{p^a-1} \pmod{p^{b+1}} \\ c \dbinom{cp^{a+b}-1}{p^a-1} & \equiv & c' \dbinom{c'p^{a+b}-1}{p^a-1} \pmod{p} \\ c & \equiv &c' \pmod{p} \end{eqnarray*} as desired. Now, suppose that $\dbinom{k + cp^a}{k} \equiv \dbinom{k + c'p^a}{k} \pmod{p^a}$. By the lemma letting $b=0$ we have $c \equiv c' \pmod{p}$ so let $c = c_1 + a_1p$ and $c' = c'_1 + a'_1p$. By the lemma again we have $a_1 \equiv a_1' \pmod{p}$ so in fact $c \equiv c' \pmod{p^2}$. By continuing this process and defining the $c_i, a_i, c'_i, a'_i$ similarly we yield that in fact $c \equiv c' \pmod{p^a}$. But this is a contradiction if $c,c'$ are distinct so we are done. Hence the problem immediately follows, as the numbers of the form $\dbinom{k+cp^a}{k}$ for $c=0,1,...,p^a$ must cover all residues modulo $p^a$.
14.04.2013 02:01
@dinoboy, I know this may sound stupid, but why does your first claim imply the problem statement?