MathDB

7

Part of 2004 Romania Team Selection Test

Problems(1)

recurrent sequence with divisibility, finite field applicat

Source: Romanian ROM TST 2004, problem 7, created by Calin Popescu

5/1/2004
Let a,b,ca,b,c be 3 integers, bb odd, and define the sequence {xn}n≥0\{x_n\}_{n\geq 0} by x0=4x_0=4, x1=0x_1=0, x2=2cx_2=2c, x3=3bx_3=3b and for all positive integers nn we have xn+3=axn−1+bxn+cxn+1. x_{n+3} = ax_{n-1}+bx_n + cx_{n+1} . Prove that for all positive integers mm, and for all primes pp the number xpmx_{p^m} is divisible by pp.
algebrapolynomialinductionlinear algebramatrixbinomial coefficientsnumber theory