Some congruence properties of binomial coefficients and linear second order recurrences (Q1111589): Difference between revisions

Let \(u_ n=(r^ n-s^ n)/(r-s)\) and \(v_ n=r^ n+s^ n\) \((n=0,1,2,...)\) be second order linear recurrences, where r and s are the zeros of \(x^ 2-Ax+B\) and \(D=A^ 2-4B>0\). After showing many elementary properties of these sequences, the author proves that \(v_{kp^ n}\equiv v_{kp^{n-1}}(mod p^ n)\) for any \(n\geq 1\), \(k\geq 0\) and p prime; and \(u_{kp^ n}\equiv t\cdot u_{kp^{n-1}}(mod p^ n)\) for any \(n\geq 1\), \(k\geq 0\) and p prime with \(p\nmid D\), where \(t=(D/p)\) if p is odd and \(t=(-1)^ B\) if \(p=2\). For binomial coefficients the congruence \[ \left( \begin{matrix} ap^ n\\ bp^ m\end{matrix} \right)\equiv (- 1)^{p-1}\left( \begin{matrix} ap^{n-m}\\ b\end{matrix} \right)(mod p^ n) \] is proved, where \(0\leq m\leq n\), \(0<b<ap^{n-m}\), and \(p\nmid ab\).