Y by trumpeter, DrMath, va2010, anantmudgal09, 62861, rkm0959, Tintarn, doxuanlong15052000, JasperL, don2001, tenplusten, Carpemath, Amir Hossein, megarnie, jacoporizzo, HamstPan38825, Adventure10, aidan0626, Sedro
Let
be a prime number. Let
denote the integers modulo
, and let
be the set of polynomials with coefficients in
. Define
by
Prove that for nonzero polynomials
,
Here, a polynomial
divides
if there exists
such that
is the polynomial with all coefficients
(with all addition and multiplication in the coefficients taken modulo
), and the gcd of two polynomials is the highest degree polynomial with leading coefficient
which divides both of them. A non-zero polynomial is a polynomial with not all coefficients
. As an example of multiplication,
in
.
Proposed by Mark Sellke



![$\mathbb F_p[x]$](http://latex.artofproblemsolving.com/1/6/3/1633a0f1c6691e5e3ecf9189e677d06ca10465e7.png)

![$\Psi : \mathbb F_p[x] \to \mathbb F_p[x]$](http://latex.artofproblemsolving.com/b/2/3/b235991d65027382c6916d1466228099becc77a3.png)
![\[ \Psi\left( \sum_{i=0}^n a_i x^i \right) = \sum_{i=0}^n a_i x^{p^i}. \]](http://latex.artofproblemsolving.com/1/a/f/1af46a31b71c32f3c194a7afeea5d5be3d23547d.png)
![$F,G \in \mathbb F_p[x]$](http://latex.artofproblemsolving.com/5/b/a/5ba6c808e48ff00cb83533b007a12711d9bde772.png)
![\[ \Psi(\gcd(F,G)) = \gcd(\Psi(F), \Psi(G)). \]](http://latex.artofproblemsolving.com/1/3/f/13ff0c15075cdac64c52ec9c62429e0e7d55a966.png)


![$R \in \mathbb F_p[x]$](http://latex.artofproblemsolving.com/2/c/5/2c5975abb489c4833da46845ade615919cce8169.png)






![$\mathbb F_5[x]$](http://latex.artofproblemsolving.com/a/f/4/af4a4857b833e03853a81db34fe5e915d127c142.png)
Proposed by Mark Sellke
This post has been edited 1 time. Last edited by v_Enhance, Dec 21, 2015, 4:29 PM
Reason: Add author
Reason: Add author