Skip to main content
OlympiadHQ

Browse · harp

Print

smc

algebra senior

Problem

The sequence is defined recursively by , , and for . What is the smallest positive integer such that the product is an integer?
(A)
(B)
(C)
(D)
Solution
Let . Then and for all . The characteristic polynomial of this linear recurrence is , which has roots and . Therefore, for constants to be determined . Using the fact that we can solve a pair of linear equations for : . Thus , , and . Now, , so we are looking for the least value of so that . Note that we can multiply all by three for convenience, as the are always integers, and it does not affect divisibility by . Now, for all even the sum (adjusted by a factor of three) is . The smallest for which this is a multiple of is by Fermat's Little Theorem, as it is seen with further testing that is a primitive root . Now, assume is odd. Then the sum (again adjusted by a factor of three) is . The smallest for which this is a multiple of is , by the same reasons. Thus, the minimal value of is .
Final answer
A