MathDB

Sequence congruence !!!

Source: Romania TST 2015 Day 5 Problem 3

June 4, 2015

Sequencebinomial coefficientscongruencenumber theoryRomanian TST

Problem Statement

Define a sequence of integers by

a_0=1

, and

a_n=\sum_{k=0}^{n-1} \binom{n}{k}a_k

n \geq 1

. Let

m

be a positive integer , let

p

be a prime , and let

q

and

r

be non-negative integers . Prove that :

a_{p^mq+r} \equiv a_{p^{m-1}q+r} \pmod{p^m}