Let p and q be prime numbers. The sequence (xn) is defined by x1=1, x2=p and xn+1=pxn−qxn−1 for all n≥2. Given that there is some k such that x3k=−3, find p and q.
Problem
Source:
Tags: algebra, polynomial, number theory unsolved, number theory
03.05.2010 02:53
If p,q are both odd, then mod 2, the sequence goes: 1,1,0,1,1,0,1,1,0,... So x3k is even, and cannot be −3. Therefore, either p=2 or q=2. If both are 2, then all terms past the second are even, so exactly one is 2. Next, mod x3=p2−q the sequence goes: 1,p,0,−qp,−qp2,0,q2p2,p3q2,0,..., easy to find the general term of the sequence, and more importantly, it is easy to show that we have x3k is divisible by x3. Thus, x3 is either 3 or −3. p=2 gives q=1,7, but 1 is not prime, so q=7. q=2 does not give a p that works. Thus, p=2, q=7 must be the candidate. To see that it is indeed the solution, note that x3=22−7=−3. Cheers, Rofler Edit: Thank you uglysolutions, if it is 1 then we get p=2, q=3, and if it is −1 then we get p=2, q=5 as the only possibilities. The first of these makes the sequence mod 3 1,2,1,2,..... so cannot make 0 mod 3, and the second sequence I don't actually know about... I haven't actually tried, but I am pretty sure that it is easy to show it never hits −3 because of the magnitude of the terms (more specifically, we can consider the characteristic polynomial that generates the sequence of every third term, and show this recurrence creates a sequence which has non-decreasing magnitude).
03.05.2010 03:38
Rofler wrote: and more importantly, it is easy to show that we have x3k is divisible by x3. Thus, x3 is either 3 or −3. Am I missing something here or x3 could also be ±1? (It's not hard to discard these cases, though)