Define a sequence of polynomials P 0 , P 1 , … by the recurrence P 0 ( x ) = 1 , P 1 ( x ) = x , P n + 1 ( x ) = 2 x P n ( x ) − P n − 1 ( x ) . Let S = ∣ ∣ ∣ ∣ P 2 0 1 7 ′ ( 2 i ) ∣ ∣ ∣ ∣ and T = ∣ ∣ ∣ ∣ P 1 7 ′ ( 2 i ) ∣ ∣ ∣ ∣ , where i is the imaginary unit. Then T S is a rational number with fractional part n m , where m and n are relatively prime positive integers. Compute m .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I got those formulas for S and T but wasn't sure if there was a nice way to compute S mod T . Did you just generate the sequence mod 1 7 F 1 7 on a computer?
Log in to reply
I did it by computer originally but, since you ask...
F 1 7 = 1 5 9 7 is (prime and) coprime to 1 7 .
Since F N + 3 6 ≡ F N ( m o d 1 7 ) , we deduce that F 2 0 1 7 ≡ F 1 ( m o d 1 7 ) , and hence 2 0 1 7 F 2 0 1 7 ≡ 1 1 ( m o d 1 7 ) .
Since F m + n − 1 = F m − 1 F n − 1 + F m F n we have that F N = F 1 7 F N − 1 8 + F 1 8 F N − 1 7 , and hence F N ≡ F 1 8 F N − 1 7 ( m o d F 1 7 ) Thus F 2 0 1 7 ≡ F 1 8 F 2 0 0 0 ≡ F 1 8 2 F 1 9 8 3 ≡ ⋯ ≡ F 1 8 1 1 8 F 1 1 ( m o d F 1 7 ) Since F n + 1 F n − 1 − F n 2 = ( − 1 ) n we see that F 1 8 2 ≡ − 1 ( m o d F 1 7 ) , and hence 2 0 1 7 F 2 0 1 7 ≡ − 2 0 1 7 F 1 1 ≡ 9 4 8 ( m o d F 1 7 )
This last calculation is "small enough" to be done manually. Solving the appropriate Chinese Remainder equations, we have 2 0 1 7 F 2 0 1 7 ≡ 4 1 4 2 ( m o d 1 7 F 1 7 ) as required.
Log in to reply
Nice, I did what you did on the mod 17 part but I missed the nice argument for mod F 1 7 .
Problem Loading...
Note Loading...
Set Loading...
If we write P n ( i x ) = i n Q n ( x ) then we have Q 0 ( x ) = 1 , Q 1 ( x ) = x and Q n ( x ) = 2 x Q n − 1 ( x ) + Q n − 2 ( x ) Thus Q 0 ( 2 1 ) = 1 , Q 1 ( 2 1 ) = 2 1 and Q n ( 2 1 ) = Q n − 1 ( 2 1 ) + Q n − 2 ( 2 1 ) so that Q n ( 2 1 ) = 2 1 L n for all n ≥ 0 . Moreover Q 0 ′ ( x ) = 0 , Q 1 ′ ( x ) = 1 and Q n ′ ( x ) = 2 x Q n − 1 ′ ( x ) + Q n − 2 ′ ( x ) + 2 Q n − 1 ( x ) so that Q 0 ′ ( 2 1 ) = 0 , Q 1 ′ ( 2 1 ) = 1 and Q n ′ ( 2 1 ) = Q n − 1 ′ ( 2 1 ) + Q n − 2 ′ ( 2 1 ) + 2 Q n − 1 ( 2 1 ) = Q n − 1 ′ ( 2 1 ) + Q n − 2 ′ ( 2 1 ) + L n − 1 Since n F n = ( n − 1 ) F n − 1 + ( n − 2 ) F n − 2 + L n − 1 we deduce that [ Q n ′ ( 2 1 ) − n F n ] = [ Q n − 1 ′ ( 2 1 ) − ( n − 1 ) F n − 1 ] + [ Q n − 2 ′ ( 2 1 ) − ( n − 2 ) F n − 2 ] and since Q n ′ ( 2 1 ) − n F n = 0 when n = 0 and 1 , we deduce that Q n ′ ( 2 1 ) = n F n n ≥ 0 . Thus S = 2 0 1 7 F 2 0 1 7 and T = 1 7 F 1 7 , and hence the fractional part of T S is 2 7 1 4 9 4 1 4 2 , making the answer 4 1 4 2 .
This approach seemed simpler than considering the Chebyshev polynomials P n ( x ) trigonometrically.