|
> Determine the remainder when (x^2-1)(x^3-1)...(x^16-1)(x^18-1) is
> divided by 1+x+x^2+...+x^16.
It's not quite clear what the first "..." stands for. The exponents are
2,3,...16,18
Had it been
2,4,...16,18
I'd assume the ... stands for even exponents.
Had it been
2,3,...17,18
or even
2,3,...16,17
I'd assume the ... stands for all integer exponents in range.
But as is, it's kind of confusing, almost a problem in itself !
/Eric
|
| If it had been
2,3,...16
You would have presumably for all the exponents between 2 and 16
inclusive, so I took
2,3,...16,18
to mean that plus a term with an eponent of 18.
Topher
|
| Solutuion by F. J. Flanigan, San Jose State University, San Jose,
California.
The remainder is 17. More generally, for p an odd prime, the remainder
when F[p](x) = (x^2-1)(x^3-1)...(x^(p-1)-1)(x^(p+1)-1) is divided by
Phi[p](x)=1+x+x^2+...+x^(p-1) is the constant p.
To see this, write F[p](x)=Q(x)Phi[p](x)+R(x), where R(x) is a
polynomial of degree at most p-2. Let eta be a root of Phi[p](x), that
is, a primitive p-th root of unity. Clearly F[p](eta)=R(eta). But
F[p](eta)=(eta^2-1)...(eta^(p-1)-1)(eta^(p+1)-1)=(1-eta)(1-eta^2)...(1-eta^(p-1))
= Phi[p](1),
where we have used eta^(p+1)=eta and the standard factorization
Phi[p](x)=(x-eta)(x-eta^2)...(x-eta^(p-1)), as well as the fact that
p-1 is even (to reverse each factor).
From this we learn that R(eta)=F[p](eta)=Phi[p](1)=1+1+...+1=p, the
given prime. But this is true for each of the p-1 primitive p-th roots
of unity. Since the polynomial R(x) has degree no larger than p-2,
R(x)=p for all x, proving the claim.
Note: For a positive integer n, recall that a complete positive
reduced residue system modulo n is a set K={k[1], k[2], ..., k[phi(n)]}
of positive integers, no two of which are congruent modulo n and each
of which is coprime to n. For n and K as above, define E[K](x)=product
over k in K of (x^k-1). Then, for n>=3, the remainder when E[K](x) is
divided by the n-th cyclotomic polynomial Phi[n](x) is the integer
Phi[n](1). The proof given above, mutatis mutandis, works here as
well.
|