Let be the hyperbola . Given a point on the -axis, we construct a sequence of points on the -axis in the following manner: let be the line with slope 1 passing through , then is the orthogonal projection of the point of intersection of and onto the -axis. (If , then the sequence simply terminates.) Let be the number of starting positions on the -axis such that . Determine the remainder of when divided by 2008.
Solution
Let . Then the meet at . Since this point lies on the hyperbola, we have . Rearranging this equation gives Choose a with , and define . Using the double-angle formula, we have It follows by induction that . Then, corresponds to (assuming that is never at the origin, or equivalently, is never an integer multiple of ). So, we need to find the number of with the property that for some integer . We have , so can be any integer between 1 and inclusive (and note that since the denominator is odd, the sequence never terminates). It follows that the number of starting positions is . Finally, we need to compute the remainder when is divided by 2008. We have . Using Fermat's Little Theorem with 251, we get . So we have and . Using Chinese Remainder Theorem, we get .