Romania NMO 2023 Grade 12 P2

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

3 users

TOPICS

No tags match your search

M

No tags match your search

M

Romania NMO 2023 Grade 12 P2

G H J

Reveal topic tags

superior algebra

L

G H BBookmark kLocked kLocked NReply

Source: Romania National Olympiad 2023

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

196 posts

#1 h Apr 14, 2023, 2:41 AM • 1 Y

Y by Willliam_B._R.

Let $p$ be a prime number, $n$ a natural number which is not divisible by $p$ , and $\mathbb{K}$ is a finite field, with $char(K) = p, |K| = p^n, 1_{\mathbb{K}}$ unity element and $\widehat{0} = 0_{\mathbb{K}}.$ For every $m \in \mathbb{N}^{*}$ we note
$\widehat{m} = \underbrace{1_{\mathbb{K}} + 1_{\mathbb{K}} + \ldots + 1_{\mathbb{K}}}_{m \text{ times}}$ and define the polynomial

$f_m = \sum_{k = 0}^{m} (-1)^{m - k} \widehat{\binom{m}{k}} X^{p^k} \in \mathbb{K}[X].$
a) Show that roots of $f_1$ are $\left\{ \widehat{k} | k \in \{0,1,2, \ldots , p - 1 \} \right\}$ .

b) Let $m \in \mathbb{N}^{*}.$ Determine the set of roots from $\mathbb{K}$ of polynomial $f_{m}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

196 posts

#3 h Apr 14, 2023, 3:09 AM

Y by

What spam?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1995 posts

#4 h Apr 14, 2023, 3:49 AM • 1 Y

Y by CANBANKAN

They are different problems. This is all valid...

Just bump it

Not spam. Just problems...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

184 posts

#5 h Apr 14, 2023, 3:35 PM

Y by

a) Notice that $f_1=X^p-X = X(X-\widehat{1})\dots (X-\widehat{p-1})$ by Fermat's little theorem.

b) Consider the function $\varphi :\mathbb{F}_p[X]\rightarrow\mathbb{F}_p[X]$ given by $\varphi(a_nX^n + \dots + a_1X + a_0)=a_nX^{p^n}+\dots + a_1X^p + a_0.$ Then using the Frobenius endomorphism, we see that $\varphi$ is in fact a ring homomorphism, from $(\mathbb{F}_p[X],+,\cdot)$ to $(\mathbb{F}_p[X],+,\circ)$ . Indeed, $\varphi(P)\circ\varphi(Q)=\sum_{i=0}^n a_i\left(\sum_{j=0}^m b_j X^{p^j}\right)^{p^i}=\sum_{i=0}^n a_i\sum_{j=0}^m b_j X^{p^{i+j}} =\sum_{k=0}^{m+n} \left(\sum_{i+j=k} a_i b_j\right)X^{p^k} =\varphi(P\cdot Q).$ Also $\varphi(P)+\varphi(Q)=\varphi(P+Q)$ however we won't need this.

Now observe that $f_m=\varphi((X-1)^m)=\varphi((X-1)^{m-1})\circ\varphi(X-1)=f_{m-1}(X^p-X)$ . We argue by induction that the set of roots in $\mathbb{K}$ of $f_m$ is exactly $\mathbb{F}_p$ . Indeed, the case $m=1$ was proved above, so suppose it's true for some $m-1\geq 1$ . Then if $\alpha$ is a root of $f_m$ , it means that $\alpha ^p-\alpha$ is a root of $f_{m-1}$ , and thus there is some $k\in\{0,1,\dots ,p-1\}$ such that $\alpha^p = \alpha +\widehat{k}$ . Inductively, $\alpha^{p^i}=(\alpha+\widehat{k})^{p^{i-1}}=\alpha^{p^{i-1}}+\widehat{k}=\dots =\alpha + i\widehat{k}.$ However, in any finite field of order $p^n$ , $\alpha^{p^n}=\alpha$ , and thus $n\widehat{k} = \widehat{0}$ , implying that $\widehat{k}=\widehat{0}$ (since $\gcd(n,p)=1$ ). This means that $\alpha^p=\alpha$ , i.e. $\alpha$ is a root of $f_1$ , finally implying that $\alpha\in\mathbb{F}_p$ , exactly what we wanted to prove.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#6 h Apr 14, 2023, 5:12 PM

Y by

Redacted

@Below I see now, thank you!

This post has been edited 3 times. Last edited by CANBANKAN, Apr 14, 2023, 11:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

184 posts

#7 h Apr 14, 2023, 6:18 PM

Y by

You are right, however the original problem asks us to find $\mathbb{F}_{p^n}\cap \mathbb{F}_{p^p}=\mathbb{F}_{p^{\gcd(n,p)}}=\mathbb{F}_p$ , so for $m=p$ the problem is somewhat simpler.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1301 posts

#8 h Apr 17, 2023, 3:36 AM • 1 Y

Y by teomihai

Here is a possibly more motivating way to see that $f_m(x)$ is a polynomial in $x^p-x$ :

First, note if $f_m(x)=f_m(y)=0$ , then $f_m(ax+by)=0$ for all $a,b\in \mathbb{F}_p$ . Therefore, the set of roots of $f_m$ (call $R$ ) form a vector space. Therefore, let $S = R / \mathbb{F}_p$ , then $f_m(x) = \prod\limits_{s\in S} \prod\limits_{j=0}^{p-1} (x-s-j) = \prod\limits_{s\in S} \left((x-s)^p-(x-s)\right) = \prod\limits_{s\in S} ((x^p-x)-(s^p-s))$
We can verify that $f_m(x)=f_{m-1}(x^p-x)$ . We induct on $m$ to show that the only roots of $f_m(x)$ in $\mathbb{F}_{p^n}$ for any $p\nmid n$ is $\mathbb{F}_p$ . Suppose $f_m$ has a root in $\mathbb{F}_{p^n}$ , call $r$ . Then by closure, $r^p-r\in \mathbb{F}_{p^n}$ . By inductive hypothesis, $r^p-r\in \mathbb{F}_p$ . If $r^p-r=0$ then $r\in \mathbb{F}_p$ . Otherwise, I will prove that the minimal polynomial of $r$ has degree $p$ , which means it must be in $\mathbb{F}_{p^p}$ , and it is also in $\mathbb{F}_{p^n}$ , which means it is in $\mathbb{F}_{p^p} \cap \mathbb{F}_{p^n} = \mathbb{F}_p$ (say by analyzing gcd of splitting polynomial)

This boils down to the classic problem that $x^p-x-a$ is irreducible. Factor into irreducibles, say $f_1(x) f_2(x) \cdots f_k(x) = f_1(x+t) f_2(x+t) \cdots f_k(x+t)$ (where each is a nonconstant poly). Then we can see that our multiset $\{f_1(x), \cdots, f_k(x)\}$ is $\{f_1(x+t), \cdots, f_k(x+t)\}$ in some order. Thus $f_1(x)=f_{j_1}(x+1) = \cdots = f_{j_{p-1}}(x-1)$ , which implies $k\ge p$ and irreducibles are linear i.e. $a=0$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

392 posts

#9 h Jul 24, 2024, 12:42 AM

Y by

Related to USA TST 2016/3.

Let $\mathbb{N}$ denote the set of natural numbers, including $0$ . Let $R$ be the ring consisting of the set of $\mathbb{K}$ -polynomials
$\left\{a_k x^{p^k}+a_{k-1} x^{p^{k-1}}+\cdots+a_1 x^p+a_0x\mid k\in\mathbb{N};\,a_0,\,\ldots,\,a_k\in\mathbb{K}\right\},$ with addition $+$ and multiplication $\circ$ (function composition). It is easy to check that $R$ is a ring with additive identity $0$ and multiplicative identity $x$ . It is not hard to see that $\mathbb{K}[x]$ and $R$ are isomorphic with isomorphism $\Psi\colon\mathbb{K}[x]\to R$ given by
$a_k x^k+\cdots+a_1 x+a_0\mapsto a_k x^{p^k}+\cdots+a_1 x^p+a_0x.$ Note that $f_m=\Psi((x-1)^m)$ .

Claim. For $m\in\mathbb{Z}^+$ , $\gcd(x^n-1,(x-1)^m)=x-1$ in $\mathbb{K}[x]$ .
Proof. It suffices to find the number of factors of $x-1$ in $x^n-1$ . Since $p\nmid n$ , it follows that $1$ is not a root of $x^{n-1}+\cdots+x+1$ . Thus $x^n-1=(x-1)(x^{n-1}+\cdots+x+1)$ has one factor of $x-1$ , as desired. $\square$

By Bezout's identity, there exists $A,\,B\in\mathbb{K}[x]$ for which $A(x)(x^n-1)+B(x)(x-1)^m=x-1$ . Then
$C(x)\circ(x^{p^n}-x)+D(x)\circ f_m(x)=x^p-x$ where $C:=\Psi(A)$ and $D:=\Psi(B)$ . Since $C$ and $D$ have no constant terms, $0$ is a root of both of them. If $\alpha\in\mathbb{K}$ is a root of $f_m$ , then $\alpha^{p^n}=\alpha$ . Hence
$\alpha^p-\alpha=C(\alpha^{p^n}-\alpha)+D(f_m(\alpha))=C(0)+D(0)=0$ so $\alpha\in\mathbb{F}_p$ . Conversely, by the binomial theorem, all elements of $\mathbb{F}_p$ are roots of $f_m$ . Thus $\boxed{\mathbb{F}_p}$ is the set of roots of $f_m$ in $\mathbb{K}$ . $\square$

This post has been edited 1 time. Last edited by KevinYang2.71, Jul 24, 2024, 5:24 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a