Factorization by inspection

Suppose f ( x ) f(x) is a monic polynomial of degree 16 16 such that

f ( 4 ) = 5 , f ( 5 ) = 6 , f ( 6 ) = 7 , , f ( 18 ) = 19 , f ( 19 ) = 20. f(4) = 5, f(5) = 6, f(6) = 7, \ldots , f(18) = 19, f(19) = 20.

Find the remainder of f ( 20 ) f(20) divided by 17 17 .


The answer is 3.

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.

1 solution

Vens L.
Sep 23, 2019

Observe that polynomial equation of degree 16 16 f ( x ) = x + 1 f(x) = x+1 has exactly 16 16 roots: x = 4 , 5 , 6 , , 18 , 19. x = 4, 5, 6, \dots, 18, 19. And by the fact that f ( x ) f(x) is monic (i.e., leading coefficient is 1 1 ), we have the factorization f ( x ) ( x + 1 ) = ( x 4 ) ( x 5 ) ( x 6 ) ( x 18 ) ( x 19 ) , f(x) - (x+1) = (x-4)(x-5)(x-6) \cdots (x-18)(x-19), namely, f ( x ) = ( x + 1 ) + ( x 4 ) ( x 5 ) ( x 6 ) ( x 18 ) ( x 19 ) . f(x) = (x+1) + (x-4)(x-5)(x-6) \cdots (x-18)(x-19).

Next, notice that f ( 20 ) = 21 + 16 15 14 2 1 = 21 + 16 ! . f(20) = 21 + 16 \cdot 15 \cdot 14 \cdots 2 \cdot 1 = 21 + 16!.

Now that 17 17 is a prime, and by Wilson’s theorem , we then have 16 ! 1 ( m o d 17 ) . 16! \equiv -1 \pmod{17}. Thus, f ( 20 ) = 21 + 16 ! 21 + ( 1 ) ( m o d 17 ) = 20 = 3 ( m o d 17 ) . \begin{aligned} f(20) &= 21 + 16! \\ &\equiv 21 + (-1) \pmod{17} \\ &= 20 \\ &= \boxed{\mathbf{3}} \pmod{17}. \end{aligned}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...