Degree reduction

Task number: 2632

In \(\mathbb Z_p\) find a polynomial \(r\) of degree at most \(p\), that attains the same values as the polynomial \(q\) for all \(x\in \mathbb Z_p\).

Variant 1
In \(\mathbb Z_5\), \(q(x)=4x^{20}+3x^{17}+2x^{16}+x^{13}+3x^{12}+2x^{10}+4x^9+2x^7+2x^5+x+3\).
Hint
Use the Fermat's little theorem.
Resolution
We replace \(x^k\) where \(k\ge p\) with \(x^{k-p+1}\).
Result
\(r(x)=4x^4+2x^3+2x^2+x+3\)
Variant 2
In \(\mathbb Z_7\), \(q(x)=5x^{16}+6x^{15}+4x^{13}+x^{12}+3x^{11}+6x^{10}+2x^9+3x^7+5x^5+2x+1\).
Result
\(r(x)=x^6+x^5+4x^4+x^3+2x+1\)

Difficulty level: Easy task (using definitions and simple reasoning)

Degree reduction

Task number: 2632

Variant 1

Hint

Resolution

Result

Variant 2

Result