gcd commutes with Psi

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

310,881 topics

21 users

TOPICS

No tags match your search

gcd commutes with Psi

G H J

Reveal topic tags

number theory

greatest common divisor

G H BBookmark kLocked kLocked NReply

Source: USA December TST for 57th IMO 2016, Problem 3

The post below has been deleted. Click to close.

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

v_Enhance

6857 posts

v_Enhance

#1 h Dec 21, 2015, 4:20 PM • 19 Y

Y by trumpeter, DrMath, va2010, anantmudgal09, 62861, rkm0959, Tintarn, doxuanlong15052000, JasperL, don2001, tenplusten, Carpemath, Amir Hossein, megarnie, jacoporizzo, HamstPan38825, Adventure10, aidan0626, Sedro

Let $p$ be a prime number. Let $\mathbb F_p$ denote the integers modulo $p$ , and let $\mathbb F_p[x]$ be the set of polynomials with coefficients in $\mathbb F_p$ . Define $\Psi : \mathbb F_p[x] \to \mathbb F_p[x]$ by $\Psi\left( \sum_{i=0}^n a_i x^i \right) = \sum_{i=0}^n a_i x^{p^i}.$ Prove that for nonzero polynomials $F,G \in \mathbb F_p[x]$ , $\Psi(\gcd(F,G)) = \gcd(\Psi(F), \Psi(G)).$ Here, a polynomial $Q$ divides $P$ if there exists $R \in \mathbb F_p[x]$ such that $P(x) - Q(x) R(x)$ is the polynomial with all coefficients $0$ (with all addition and multiplication in the coefficients taken modulo $p$ ), and the gcd of two polynomials is the highest degree polynomial with leading coefficient $1$ which divides both of them. A non-zero polynomial is a polynomial with not all coefficients $0$ . As an example of multiplication, $(x+1)(x+2)(x+3) = x^3+x^2+x+1$ in $\mathbb F_5[x]$ .

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

Z K Y

The post below has been deleted. Click to close.

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

ABCDE

1963 posts

ABCDE

#2 h Dec 21, 2015, 4:37 PM • 33 Y

Y by AkshajK, DrMath, bearytasty, acegikmoqsuwy2000, mathtastic, va2010, pi37, Lord.of.AMC, mymathboy, zero.destroyer, BartSimpsons, Guendabiaani, fireclaw105, shootingstar8, chezbgone, rkm0959, biomathematics, JasperL, don2001, kingofgeedorah, Tawan, NoDealsHere, kapilpavase, magicarrow, Aryan-23, Eliot, megarnie, Kobayashi, IAmTheHazard, sabkx, Adventure10, aidan0626, MS_asdfgzxcvb

Here's a pretty unique solution I found after the test

Solution

Z K Y

The post below has been deleted. Click to close.

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

DrMath

2130 posts

DrMath

#3 h Dec 21, 2015, 4:49 PM • 43 Y

Y by djmathman, bigmath, va2010, ABCDE, bearytasty, acegikmoqsuwy2000, chezbgone, droid347, mssmath, rkm0959, aravindsidd, Guendabiaani, Eugenis, fireclaw105, trumpeter, FTW, Darn, WOOT2016er, TheMagician, High, biomathematics, Tintarn, MSTang, AMN300, doxuanlong15052000, JasperL, don2001, kingofgeedorah, Tawan, magicarrow, Aryan-23, Aimingformygoal, tigerzhang, franchester, Kobayashi, ghu2024, sabkx, Adventure10, aidan0626, ohiorizzler1434, Sedro, rafayaashary1, MS_asdfgzxcvb

Hello, me and ABCDE seem to be in discontent over the more beautiful solution. I post my solution:

Solution

Z K Y

The post below has been deleted. Click to close.

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

djmathman

7934 posts

djmathman

#4 h Dec 21, 2015, 4:53 PM • 9 Y

Y by DrMath, TheMagician, acegikmoqsuwy2000, rkm0959, MSTang, Tawan, nya10, Adventure10, Mango247

^^ So basically this reduction mechanism is

Dang, that's pretty nice.

(Sorry ABCDE

)

This post has been edited 2 times. Last edited by djmathman, Dec 21, 2015, 4:54 PM

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#5 h Dec 22, 2015, 4:09 AM • 21 Y

Y by ABCDE, pi37, acegikmoqsuwy2000, shootingstar8, DrMath, High, GreenKeeper, rkm0959, r31415, Uagu, smy2012, don2001, kingofgeedorah, Tawan, Supercali, Eliot, tigerzhang, Mz_T, Adventure10, Mango247, aidan0626

Solution I found during the test

Z K Y

The post below has been deleted. Click to close.

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

pi37

2079 posts

pi37

#6 h Dec 22, 2015, 4:28 AM • 5 Y

Y by ABCDE, DrMath, acegikmoqsuwy2000, Adventure10, Mango247

CantonMathGuy's solution above is how I and how I believe most people solved it.

Another solution along similar lines someone showed me
We prove that not only $P\mid Q$ implies $\Psi(P)\mid \Psi(Q)$ , but also that the converse holds as well. This implies that $\Psi$ is not only a poset homomorphism, but a poset isomorphism, which directly gives us the gcd statement. In fact, if the gcd statement is true, then $\Psi$ must be an isomorphism, which follows from plugging in some $F,G$ with $F\mid G$ or $\Psi(F)\mid \Psi(G)$ .

Other people have proved the only if direction, so let's prove the if direction. Suppose $\Psi(P)\mid \Psi(Q)$ , and $Q=PA+B$ for $\deg B<\deg P$ . Then $\Psi(Q)=\Psi(PA)+\Psi(B)$ , but as $\Psi(P)\mid \Psi(PA)$ and $\Psi(P)\mid \Psi(Q)$ , we get that $\Psi(P)\mid \Psi(B)$ . But $\deg B<\deg P$ , so $\deg \Psi(B)<\deg \Psi(P)$ , and $\Psi(B)=0$ , implying $B=0$ as well.

EDIT: This is wrong, as brian22 points out. Refer to CantonMathGuy's solution instead.

This post has been edited 3 times. Last edited by pi37, Jul 31, 2016, 1:57 PM

Z K Y

The post below has been deleted. Click to close.

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

brian22

339 posts

brian22

#7 h Dec 22, 2015, 5:50 AM • 9 Y

Y by ABCDE, DrMath, acegikmoqsuwy2000, GreenKeeper, Naysh, zacchro, AMN300, Adventure10, Mango247

@above

Another proof of P | Q implies psi(P) | psi(Q) (courtesy of zacchro and me)

This post has been edited 1 time. Last edited by brian22, Dec 22, 2015, 5:55 AM
Reason: Want to be able to claim my prize money -- along with zacchro -- for being able to find the solution that most clearly shows the inspiration for the problem. When Mark Sellke gets around to giving out such prizes.

Z K Y

The post below has been deleted. Click to close.

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

MathPanda1

1135 posts

MathPanda1

#10 h Dec 24, 2015, 3:01 AM • 3 Y

Y by BaronPit, Adventure10, Mango247

CantonMathGuy wrote:

$\Psi(Q)=\Psi\left(P\sum_{i=0}^{k}r_ix^i\right)=\sum_{i=0}^{k}\Psi(Pr_ix^i)=\sum_{i=0}^{k}r_i\Psi(P)^{p^i}\equiv0\pmod{\Psi(P)}$

Sorry if this sounds stupid, but isn't $\Psi : \mathbb F_p[x] \to \mathbb F_p[x]$ ? So why is $\Psi\left(P\sum_{i=0}^{k}r_ix^i\right)=\sum_{i=0}^{k}\Psi(Pr_ix^i))=\sum_{i=0}^{k}r_i\Psi(P)^{p^i}$ true, since you might have to first reduce the coefficients in the expression in $\Psi$ by $\pmod p$ before you can change and evaluate the expression? Thanks.

Z K Y

The post below has been deleted. Click to close.

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

MathPanda1

1135 posts

MathPanda1

#11 h Dec 24, 2015, 4:04 AM • 3 Y

Y by BaronPit, Adventure10, Mango247

To be more clear, I mean:
If $P=\sum_{i=0}^{k}p_ix^i$ , then $\Psi(Pr_ix^i)$ will have coefficients $p_jr_i$ , which could be greater than $p$ , so we would need to subtract some number of $p$ 's, giving $p_jr_i-mp$ , giving $\sum_{i=0}^{k} (p_jr_i-mp)x^{something} = \sum_{i=0}^{k} r_i\Psi(P)^{p^i} - something$ , which may not be $0 \pmod \Psi(P)$ .
$\sum_{i=0}^{k}r_i\Psi(P)^{p^i}$ could have coefficients greater than $p$ , so you would have to first reduce the coefficients by $\pmod p$ before you can say that it is $0 \pmod \Psi(P)$ , right? But reducing the coefficients by $\pmod p$ could make it no longer divisible by $\Psi(P)$ as you sort of changed the expression and coefficients.

Z K Y

The post below has been deleted. Click to close.

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

ABCDE

1963 posts

ABCDE

#12 h Dec 24, 2015, 4:43 AM • 2 Y

Y by Adventure10, Mango247

In $\mathbb{F}_{p}[x]$ we say that $F(x)\mid G(x)$ if there exists a polynomial $Q(x)$ such that $F(x)\equiv G(x)Q(x)\pmod{p}$ . Reduction doesn't affect anything, because in $\mathbb{F}_p[x]$ the polynomials $P(x)$ and $P(x)+pQ(x)$ are the same.

Z K Y

The post below has been deleted. Click to close.

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

MathPanda1

1135 posts

MathPanda1

#13 h Dec 24, 2015, 6:54 PM • 3 Y

Y by BaronPit, Adventure10, Mango247

So just confirming, $x^3+x^2+x+1$ is divisible by $x+3$ in $\mathbb{F}_{5}[x]$ since $x^3+x^2+x+1 \equiv (x+1)(x+2)(x+3) \pmod 5$ ?

This post has been edited 1 time. Last edited by MathPanda1, Dec 24, 2015, 6:54 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6857 posts

v_Enhance

#14 h Dec 24, 2015, 7:54 PM • 3 Y

Y by HamstPan38825, Adventure10, Mango247

MathPanda1 wrote:

So just confirming, $x^3+x^2+x+1$ is divisible by $x+3$ in $\mathbb{F}_{5}[x]$ since $x^3+x^2+x+1 \equiv (x+1)(x+2)(x+3) \pmod 5$ ?

That is correct.

Z K Y

The post below has been deleted. Click to close.

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

rkm0959

1721 posts

rkm0959

#15 h Mar 17, 2016, 5:36 AM • 3 Y

Y by 62861, Adventure10, Mango247

Fun problem

I hope the solution below is okay.
Claim 1. $\Psi (F+G) = \Psi (F) + \Psi (G)$ and $\Psi(cF) = c\Psi(F)$ for integer $c$ .
This follows from definition of $\Psi$ - easy.

Claim 2. $\Psi (Fx^k) = \Psi(F)^{p^k}$ for all $k \in \mathbb{N}$ .
We go by induction. Let $F = \sum_{i=0}^n a_ix^i$ . First we prove the statement for $ik1$ .
$\Psi( Fx) = \Psi ( \sum_{i=1}^{n+1} a_{i-1}x^i) = \sum_{i=1}^{n+1} a_{i-1}x^{p^i} = (\sum_{i=1}^{n+1} a_{i-1}x^{p^{i-1}})^p = (\sum_{i=0}^n a_ix^{p^i})^p = \Psi(F)^p$ as required. Now if the result holds for $k$ , then $\Psi(Fx^{k+1}) = \Psi(Fx^k)^p = \Psi(F)^{p^{k+1}}$ so the result holds for $k+1$ as well, finishing the induction.

Claim 3. $Q|P \implies \Psi(Q)|\Psi(P)$ .
Denote $P=QR$ , and let $R = \sum_{i=0}^n a_ix^i$ .
Now $\Psi(P) = \Psi(QR) = \Psi(Q\sum_{i=0}^n a_ix^i) = \sum_{i=0}^n a_i \Psi(Qx^i) = \sum_{i=0}^n a_i \Psi(Q)^{p^i} \equiv 0 \pmod{\Psi(Q)}$ which gives us that $Q|P \implies \Psi(Q)|\Psi(P)$ as required.

Now for the main proof.
We show that $\Psi(\text{gcd}(F,G))|\text{gcd}(\Psi(F),\Psi(G))$ and $\text{gcd}(\Psi(F),\Psi(G))|\Psi(\text{gcd}(F,G))$ .

First, we show that $\Psi(\text{gcd}(F,G))|\text{gcd}(\Psi(F),\Psi(G))$ .
Since $\Psi(\text{gcd}(F,G))| \Psi(F)$ and $\Psi(\text{gcd}(F,G)) | \Psi(G)$ , the result follows.

Second, we show that $\text{gcd}(\Psi(F),\Psi(G))|\Psi(\text{gcd}(F,G))$ .
Take $A, B \in \mathbb F_p[x]$ such that $AF+BG = \text{gcd}(F,G)$ .
Now $\text{gcd}(\Psi(F),\Psi(G))|\Psi(F) | \Psi(AF)$ and $\text{gcd}(\Psi(F),\Psi(G))|\Psi(G)|\Psi(BG)$ .
This gives us $\text{gcd}(\Psi(F),\Psi(G))|\Psi(AF+BG) = \Psi(\text{gcd}(F,G))$ as required.

These two relations are enough to claim that $\Psi(\gcd(F,G)) = \gcd(\Psi(F), \Psi(G))$ , so we are done. $\blacksquare$

This post has been edited 2 times. Last edited by rkm0959, Aug 10, 2017, 1:49 PM

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#16 h Mar 17, 2016, 5:43 AM • 2 Y

Y by rkm0959, Adventure10

@above: Wow our proofs are really similar - you even use the same variable names

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6857 posts

v_Enhance

#17 h May 31, 2016, 3:33 PM • 3 Y

Y by Pluto1708, HamstPan38825, Adventure10

pi37 wrote:

This implies that $\Psi$ is not only a poset homomorphism, but a poset isomorphism, which directly gives us the gcd statement.

I think you also need to show that the image of $\Psi$ is closed under g.c.d. for this to work. Fortunately, not hard either.

Z K Y

The post below has been deleted. Click to close.

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

AMN300

563 posts

AMN300

#18 h Jul 31, 2016, 1:21 AM • 2 Y

Y by Adventure10, Mango247

Doesn't seem too bad for a 3/6? My solution isn't super nice like some of the others on this thread but it is the easiest to find imho

Solution

As a side note, was this problem motivated by the Frobenius Endomorphism?

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#19 h Jul 31, 2016, 1:25 AM • 2 Y

Y by Adventure10, Mango247

@above: Many people (including me) felt that this was the easiest problem on December TST.

This post has been edited 1 time. Last edited by 62861, Jul 31, 2016, 1:28 AM
Reason: elaborate

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6857 posts

v_Enhance

#20 h Jul 31, 2016, 4:13 AM • 7 Y

Y by 62861, smy2012, v4913, HamstPan38825, sabkx, Adventure10, Mango247

CantonMathGuy wrote:

@above: Many people (including me) felt that this was the easiest problem on December TST.

Noted. I'll make sure P3 is harder next time.

Jokes aside: I was generally of the impression that all three problems on this December TST were of comparable difficulty (all medium-easy). I personally voted this one as a bit harder than P1 or P2, but not by much.

Z K Y

The post below has been deleted. Click to close.

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

randomusername

1059 posts

randomusername

#21 h Sep 20, 2016, 4:15 PM • 3 Y

Y by anantmudgal09, Adventure10, Mango247

An ounce of linear algebra

Z K Y

The post below has been deleted. Click to close.

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

randomusername

1059 posts

randomusername

#23 h Sep 20, 2016, 5:14 PM • 1 Y

Y by Adventure10

By the way, it seems that the easier part of my solution is the same as brian22's idea. Also, it appears to be a deeper interpretation of CantonMathGuy's solution. But at least it's linear algebra!

Z K Y

The post below has been deleted. Click to close.

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

tenplusten

1000 posts

tenplusten

#24 h Sep 22, 2017, 3:22 PM • 1 Y

Y by Adventure10

Does anyone know any article (and can you send me please?) about linear algebra?
It seems this is going to be important topic in olympiad.
Thanks!!!

Z K Y

The post below has been deleted. Click to close.

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

TomMarvoloRiddle

802 posts

TomMarvoloRiddle

#25 h Sep 22, 2017, 6:52 PM • 3 Y

Y by tenplusten, Adventure10, Mango247

tenplusten wrote:

Does anyone know any article (and can you send me please?) about linear algebra?
It seems this is going to be important topic in olympiad.
Thanks!!!

I think you can do good in Olympiad without knowing linear algebra.

Z K Y

The post below has been deleted. Click to close.

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

tenplusten

1000 posts

tenplusten

#26 h Sep 23, 2017, 9:23 AM • 2 Y

Y by Adventure10, Mango247

TomMarvoloRiddle wrote:

tenplusten wrote:

Does anyone know any article (and can you send me please?) about linear algebra?
It seems this is going to be important topic in olympiad.
Thanks!!!

I think you can do good in Olympiad without knowing linear algebra.

Maybe...
But I want to learn it ...
Anyone can help me?

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6857 posts

v_Enhance

#27 h Sep 23, 2017, 9:20 PM • 6 Y

Y by Lam.DL.01, tenplusten, v4913, HamstPan38825, Adventure10, DEKT

tenplusten wrote:

Does anyone know any article (and can you send me please?) about linear algebra?
It seems this is going to be important topic in olympiad.
Thanks!!!

In terms of textbooks, I have heard good things about Linear Algebra Done Right. Most linear algebra textbooks are pretty bad though.

Part II of my Napkin also covers linear algebra briefly.

Z K Y

The post below has been deleted. Click to close.

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

MathStudent2002

934 posts

MathStudent2002

#28 h Dec 28, 2018, 7:40 PM • 3 Y

Y by Eliot, Adventure10, Mango247

Can someone check this?

Clearly $\Psi$ is linear. Now, note that if $A = \sum a_ix^i \in \mathbb F_p[x]$ , and $B = x^k$ , $\Psi(AB) = \Psi\left(\sum a_ix^{i+k}\right) = \sum a_ix^{p^{i+k}} = \left(\sum a_ix^{p^i}\right)^{p^k},$ so $\Psi(AB) = \Psi(B) \circ \Psi(A)$ by linearity. Similarly this equals $\Psi(A)\circ \Psi(B)$ . We have the following lemma:

Lemma: Let $P,Q$ be polynomials with $\gcd(P,Q) = R$ . Then, $\gcd(P(A), Q(A)) = R(A)$ .

Proof: Dividing $P,Q$ by $R$ it suffices to show this for the case $R = 1$ . Then $P,Q$ do not have common roots (in $\overline{\mathbb F_p}$ ); we wish to show $P(A), Q(A)$ do not either. Indeed, if they did have some common root $\alpha$ then $A(\alpha)$ would be a common root of $P,Q$ , contradiction. $\Box$

Now, let $H = \gcd(F,G)$ , $F = HF'$ , $G = HG'$ . Then, $\Psi(F) = \Psi(HF') = \Psi(F')\circ \Psi(H)$ , and $\Psi(G) = \Psi(G')\circ \Psi(H)$ . Now, we see that $\gcd(\Psi(F), \Psi(G)) = \gcd(\Psi(F'), \Psi(G'))\circ \Psi(H)$ . Thus it suffices to show that for $\gcd(F',G') = 1$ , $\gcd(\Psi(F'),\Psi(G')) = x$ . Clearly $x$ divides both $\Psi(F')$ and $\Psi(G')$ . By Bézout there exist $A,B$ with $AF'+BG' = 1$ . Taking $\Psi$ of both sides we have $\Psi(A)\circ \Psi(F') + \Psi(B)\circ \Psi(G') = x.$ Now, let $H' = \gcd(\Psi(F'), \Psi(G'))$ , and we have $H'\mid \Psi(F')\mid \Psi(A)\circ \Psi(F')$ and $H'\mid \Psi(B)\circ\Psi(G')$ , so $H\mid x$ as well; thus $H' = x$ and we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

yayups

1614 posts

yayups

#30 h Feb 24, 2019, 7:58 AM • 2 Y

Y by Adventure10, Mango247

Let $\Phi:\mathbb{F}_p[X]\to\mathbb{F}_p[Y]$ be given by
$\Phi\left(\sum_{i=0}^n a_iX^i\right) = \sum_{i=0}^n a_iY^{1+p+p^2+\cdots+p^{i-1}}.$ For example, $\Phi(X^2+X+1)=Y^{p+1}+Y+1$ . Note that
$\Psi(F)(X)=X\Phi(F)(X^{p-1}).$ The crux of the solution is lemma 2 below, but we need lemma 1 as a prerequisite..

Lemma 1: Suppose $P\in\mathbb{F}_p[Y]$ . Then $P(Y^{p^k})=P(Y)^{p^k}$ .

Proof of Lemma 1: It's clear we can show the lemma for $k=1$ , and the other $k$ follow by repition of the $k=1$ case. This is the lemma that utilizes the fact that we are working mod $p$ . Suppose
$P(Y)=\sum_{i=0}^np_iY^i.$ Then,
$P(Y)^p=\sum_{a_0+\cdots+a_n=r}\frac{p!}{a_0!a_1!\cdots a_n!}p_{a_0}\cdots p_{a_n}Y^p.$ But if at least two of $a_0,\ldots,a_n$ are nonzero, then $\frac{p!}{a_0!a_1!\cdots a_n!}\equiv 0\pmod{p}$ , so the lemma is proved. $\blacksquare$

Lemma 2: Suppose $A,F\in\mathbb{F}_p[X]$ . There exists a polynomial $\bar{A}\in\mathbb{F}_p[Y]$ such that
$\Phi(A\cdot F)=\bar{A}\cdot\Phi(F).$
Proof of Lemma 2: For brevity, let $\bar{F}=\Phi(F)$ . Suppose
$A(X)=\sum_{i=0}^na_iX^i$ and
$F(X)=\sum_{i=0}^mf_iX^i.$ Let
$\bar{A}(Y):=\sum_{i=0}^n a_iY^{1+p+\cdots+p^{i-1}}\bar{F}(Y)^{p^i-1}.$ Then, we have that
$\begin{align*} \bar{A}(Y)\bar{F}(Y)&=\sum_{i=0}^n a_i Y^{1+p+\cdots+p^{i-1}}\bar{F}(Y)^{p^i} \\ &= \sum_{i=0}^n a_i Y^{1+p+\cdots+p^{i-1}}\bar{F}(Y^{p^i}) \\ &= \sum_{i=0}^n a_i Y^{1+p+\cdots+p^{i-1}}\sum_{j=0}^m f_j Y^{(1+p+\cdots+p^{i-1})p^j} \\ &= \sum_{i=0}^n\sum_{j=0}^m a_if_j Y^{1+p+\cdots+p^{i+j-1}} \\ &= \Phi(A\cdot F)(Y), \end{align*}$ as desired. $\blacksquare$

Suppose $\gcd(F,G)=H$ . We see that $\Phi(H)\mid\Phi(F)$ by lemma 2, so $\Psi(H)\mid\Psi(F)$ , and similarly $\Psi(H)\mid\Psi(G)$ . Therefore, $\Psi(H)\mid\gcd(\Psi(F),\Psi(G))$ . If we showed that there were $A',B'\in\mathbb{F}_P[X]$ so that
$\Psi(H)=A'\Psi(F)+B'\Psi(G),$ then we'd be done (because this would imply $\gcd(\Psi(F),\Psi(G))\mid\Psi(H)$ , and we already have $\Psi(H)\mid\gcd(\Psi(F),\Psi(G))$ ).

Suppose $H(X)=A(X)F(X)+B(X)G(X)$ . Then, construct $\bar{A},\bar{B}\in\mathbb{F}_p[Y]$ according to lemma 2. Thus,
$\Phi(H)=\Phi(A\cdot F)+\Phi(B\cdot G)=\bar{A}\cdot\Phi(F)+\bar{B}\cdot\Phi(G).$ Let $A'(X)=\bar{A}(X^{p-1})$ and $B'(X)=\bar{B}(X^{p-1})$ . Thus,
$\Psi(H)(X)=X\Phi(H)(X^{p-1})=A'(X)\Psi(F)(X)+B'(X)\Psi(G)(X),$ so $\gcd(\Psi(F),\Psi(G))=\Psi(H)$ , as desired. $\square$

This post has been edited 1 time. Last edited by yayups, Feb 25, 2019, 12:08 AM
Reason: streamlined lemma 1 and cleaned up end of proof (as per suggestion of zaccro)

Z K Y

The post below has been deleted. Click to close.

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

math_pi_rate

1218 posts

math_pi_rate

#31 h Feb 28, 2019, 1:15 PM • 2 Y

Y by Adventure10, Mango247

Even though I love geometry, I found this problem to be the easiest USA TST P3 that I have tried till now. Weird

. Anyway, I'll provide my solution (which I guess is nothing new for this forum, but still

): I don't like $F$ and $G$ so I'll use $P$ and $Q$ . First of all a trivial observation (proof's not included obviously)-

OBSERVATION $\Psi(P+Q)=\Psi(P)+\Psi(Q)$ . In particular, $\Psi(aP)=a\Psi(P)$ , where $a \in \mathbb{Z}$ .

Now, for some serious claims, which will help us conquer the problem. But before that a well-known lemma which we'll require later on-

LEMMA Let $a_1,a_2, \dots ,a_n$ be $n$ integers and $p$ be a prime. Then $(a_1+a_2+ \dots +a_n)^p \equiv a_1^p+a_2^p+ \dots +a_n^p \pmod{p}$
Proof of Lemma The proof proceeds by induction on $n$ . For $n=2$ , we just need to apply binomial theorem on the LHS, and use the fact that $p \mid \binom{p}{i}$ for $i \in \{1,2, \dots ,p-1\}$ . Then the inductive step is fairly simple to use. $\Box$

CLAIM 1 $\Psi(P) \mid \Psi(Px^m)$ for all $m \in \mathbb{Z}^+$ .

Proof of Claim 1 Let $P(x)=a_0+a_1x+ \dots +a_nx^n$ . Then $\Psi(Px^m)=\Psi(a_0x^m+a_1x^{m+1}+ \dots +a_nx^{m+n})=a_0x^{p^m}+a_1x^{p^{m+1}}+ \dots +a_mx^{p^{m+n}}$ Now, By Fermat's Little Theorem, and using the fact that $\gcd(a_i,p)=1$ for all $i \in \{0,1, \dots ,n\}$ as $a_i \in \mathbb{F}_p$ , we have that $a_i \equiv a_i^{p^m} \pmod{p} \quad \forall i \in \{0,1, \dots ,n\}$ Using the above equality, and working in $\mathbb{F}_p$ , we have $\Psi(Px^m)=\sum_{i=0}^n \left(a_ix^{p^i} \right)^{p^m} \overset{\text{LEMMA}}{\Longrightarrow} \Psi(Px^m)=\left(\sum_{i=0}^n a_ix^{p^i} \right)^{p^m}=(\Psi(P))^{p^m} \Rightarrow \Psi(P) \mid \Psi(Px^m) \quad \Box$
CLAIM 2 (Key Claim) $\Psi(P) \mid \Psi(PQ)$ for all $P,Q \in \mathbb F_p[x]$ .

Proof of Claim 2 Let $Q(x)=b_0+b_1x+ \dots +b_kx^k$ . Then using our initial observation, we have $\Psi(PQ)=\Psi(b_0P+b_1xP+ \dots +b_kx^kP)=b_0\Psi(P)+b_1 \Psi(Px)+ \dots b_k \Psi(Px^k) \overset{\text{CLAIM 1}}{\Longrightarrow} \Psi(P) \mid \Psi(PQ) \quad \Box$

Return to the problem at hand. Let $\gcd(P,Q)=R$ . Then, by Claim 2, $\Psi(R) \mid \Psi(P)$ and $\Psi(R) \mid \Psi(Q)$ , which together gives that $\Psi(R) \mid \gcd(\Psi(P),\Psi(Q))$ .

Now, By Bezout's Identity, we can write $R=AP+BQ$ for polynomials $A,B \in \mathbb F_p[x]$ . Then, using our observation once again, we get that $\Psi(R)=\Psi(AP+BQ)=\Psi(AP)+\Psi(BQ) \overset{\text{CLAIM 2}}{\Longrightarrow} \Psi(R)=C\Psi(P)+D\Psi(Q) \text{ for some polynomials } C,D \in \mathbb F_p[x]$ But this means (again by Bezout's Identity) that $\gcd(\Psi(P),\Psi(Q)) \mid \Psi(R)$ . Thus, we have $\gcd(\Psi(P),\Psi(Q))=\Psi(R)=\Psi(\gcd(P,Q)) \quad \blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Vrangr

1600 posts

Vrangr

#32 h May 4, 2019, 10:30 AM • 4 Y

Y by MathBoy23, Adventure10, Mango247, Mango247

Claim 1: $\left(\sum_{i = 1}^n a_i\right)^p = \sum_{i = 1}^n a_i^p$ for $a_i \in \mathbb{F}_p[x]$ .
Proof. $p \left| \binom{p}{k}\right.$ for all $1 \le k < p$ since no number in the denominator is divisible by $p$ .
$\begin{align*} \left(\sum_{i = i}^n a_i\right)^p = \left(a_n + \sum_{i = 1}^{n - 1} a_i\right)^p &= a_n^p + \sum_{k = 1}^{p - 1} \binom{p}{k} a_n^k \left(\sum_{i = 1} a_i\right)^{p - k} + \left(\sum_{i = 1}^{n - 1} a_i\right)^{p}\\ &= a_n^p + \left(\sum_{i = 1}^{n-1} a_i\right)^{p} = \cdots = \sum_{i = 1}^n a_i^p\qquad\qquad\qquad\square \end{align*}$
Let $\circ$ refer to composition of functions.
Let $\mathbb{S}$ be the image of $\mathbb{F}_p[x]$ under $\Psi$ .

Claim 2: $(\mathbb{S}, +, \circ)$ is a ring.
Proof. Clearly $S$ is closed under addition.
Let $P(x) = \sum_{i=1}^m a_i x^{p^i}$ and $Q(x) = \sum_{i=1}^n b_i x^{p^i}$
$(Q(x))^{p^j} = \left(\sum_{i=1}^n b_i x^{p^i}\right)^{p^j} = \left(\sum_{i=1}^n b_i^{p} x^{p^{i + 1}}\right)^{p^{j - 1}} = \left(\sum_{i=1}^n b_i x^{p^{i + 1}}\right)^{p^{j - 1}} = \cdots = \sum_{i=1}^n b_i x^{p^{i + j}}$ $(P\circ Q)(x) = P(Q(x)) = \sum_{j = 1}^m a_j (Q(x))^{p^j} = \sum_{j = 1}^m \sum_{i=1}^n a_j b_i x^{p^{i + j}} \in \mathbb{S}$ Thus $\mathbb{S}$ is closed under composition.
Clearly both the identities are present in $\mathbb{S}$ and additive inverse is present in $\mathbb{S}$ .
Thus, $(\mathbb{S}, +, \circ)$ is a ring. $\square$
It's well-known that $(\mathbb{F}_p[x], +, \times)$ is a ring.

We'll call the rings $\mathbb{S}$ and $\mathbb{F}_p[x]$ .

Claim 3: $\mathbb{F}_p[x] \cong \mathbb{S}$ with $\Psi$ as the isomorphism.
Proof. It's trivial to prove that $\Psi$ distributes over $+$ and is bijective.
Multiplicative identity of $\mathbb{F}_p[x]$ is $1$ and that of $S$ is $P(x) = x$ . So clearly $\Psi(1) = x$ .
Now from the proof of claim 2 we know that for $P(x) = \sum_{i = 1}^m a_i x^{i}$ and $Q(x) = \sum_{i=1}^n b_i x^{i}$ ,
$(\Psi (P) \circ \Psi (Q))(x) = \sum_{i = 1}^m \sum_{j =1}^n a_i b_j x^{p^{i + j}} = \Psi\left(\sum_{i = 1}^m \sum_{j =1}^n a_i b_j x^{i + j}\right) = \Psi\left(P(x) \times Q(x)\right).$ Thus, $\Psi$ is an isomorphism from $\mathbb{F}_p[x] \to \mathbb{S}$ . $\square$

Claim 4: If $P, Q \in \mathbb{F}_p[x]$ such that $Q | P$ , then $\Psi(Q) | \Psi(P)$ .
Proof. Let $P = QR$ . Since $x | T(x)$ for all $T \in \mathbb{S}$ , replacing $T$ with $\Psi(R)$ and $x$ with $\Psi(Q)$ .
$\Psi(Q) | \Psi R (\Psi Q) = (\Psi R) \circ (\Psi Q) = \Psi(RQ) = \Psi(P).\qquad \square$
Claim 5: $\Psi(\gcd(P, Q)) | \gcd(\Psi(P), \Psi(Q))$ for all $P, Q \in \mathbb{F}_p[x]$ .
Proof. $\left.\begin{cases} \gcd(P, Q) | P \\\gcd(P, Q) | Q \end{cases}\hspace{-1em}\right\} \implies \left.\begin{cases} \Psi(\gcd(P, Q)) | \Psi(P) \\\Psi(\gcd(P, Q)) | \Psi(Q) \end{cases}\hspace{-1em}\right\} \implies \Psi(\gcd(P, Q)) | \gcd(\Psi(P), \Psi(Q)) \qquad\square$
Claim 6: $\gcd(\Psi(P), \Psi(Q)) | \Psi(\gcd(P, Q))$ for all $P, Q \in \mathbb{F}_p[x]$ .
Proof. Let $\gcd(P, Q) = PX + QY$ for $X, Y \in \mathbb{F}_p[x]$ by Bezout's Identity for polynomials.
Now,
$\Psi(\gcd(P, Q)) = \Psi(PX + QY) = \Psi(PX) + \Psi(QY)$ Since $P|PX$ and $Q|QY$ , $\Psi(P)|\Psi(PX)$ and $\Psi(Q)|\Psi(QY)$ .
Therefore
$\gcd(\Psi(P), \Psi(Q))| \Psi(PX) + \Psi(QY)$ as desired. $\square$

Combining claim 5 and 6, we get the desired result,
$\gcd(\Psi(P), \Psi(Q)) = \Psi(\gcd(P, Q))$ for all $P, Q \in \mathbb{F}_p[x]$ .

This post has been edited 5 times. Last edited by Vrangr, May 30, 2019, 2:25 PM

Z K Y

The post below has been deleted. Click to close.

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

rocketscience

466 posts

rocketscience

#35 h Sep 13, 2019, 3:20 AM • 2 Y

Y by Adventure10, Mango247

For an $A \in \mathbb{F}_p[x]$ , let $f_A(x)$ denote the polynomial $\Psi(A)$ . Observe that $\Psi(kA) = k\Psi(A)$ for a constant $k$ and $\Psi(A+B) = \Psi(A) + \Psi(B).$

Lemma: $f_{AB}(x) = f_A(f_B(x))$ .
Proof

Lemma: Let $d(x)$ be a monic polynomial. Then for relatively prime polynomials $A, B$ we have
$\gcd(f_A(d), f_B(d)) = d.$ Proof

To finish, let $d = \gcd(F, G)$ and write $\gcd(\Psi(F), \Psi(G)) = \gcd( f_{F/d}(f_d), f_{G/d}(f_d))$ by the first lemma. Then apply the second lemma to get that this $\gcd$ is just $f_d=\Psi(\gcd(F, G))$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

TheUltimate123

1739 posts

TheUltimate123

#36 h Feb 25, 2020, 7:42 AM • 1 Y

Y by char2539

Note that $\Psi(P+Q)=\Psi(P)+\Psi(Q)$ and $\Psi(kP)=k\Psi(P)$ .

Lemma: For $P\in\mathbb F_p[x]$ and $k\in\mathbb Z$ , we have $\Psi(Px^k)=\Psi(P)^{p^k}$ .

Proof. Let $\textstyle P(x)=\sum_{i=0}^na_ix^i$ . Write $\Psi(Px^k)=\Psi\left(\sum_{i=0}^na_ix^{i+k}\right)=\sum_{i=0}^na_i\left(x^{p^i}\right)^{p^k}=\left(\sum_{i=0}^na_ix^{p^i}\right)^{p^k}=\Psi(P)^{p^k},$ where the third equality is by Frobenius. $\blacksquare$

Lemma: For $P,Q\in\mathbb F_p[x]$ , if $P\mid Q$ , then $\Psi(P)\mid\Psi(Q)$ .

Proof. Let $Q=PR$ and $\textstyle R=\sum_{i=0}^na_ix^i$ . Then $\Psi(Q)=\Psi\left(P\sum_{i=0}^na_ix^i\right)=\sum_{i=0}^na_i\Psi(Px^i)=\sum_{i=0}^na_i\Psi(P)^{p^i},$ which is divisible by $\Psi(P)$ . $\blacksquare$

Let $H=\gcd(F,G)$ and $I=\gcd(\Psi(F),\Psi(G))$ , so it suffices to prove $\Psi(H)=I$ . Note the following:

By the above lemma, we have $\Psi(H)\mid\Psi(F)$ and $\Psi(H)\mid\Psi(G)$ , so $\Psi(H)\mid I$ .
Let $H=AF+BG$ for $A,B\in\mathbb F_p[x]$ by B\'ezout's lemma. We have $I\mid\Psi(F)\mid\Psi(AF)$ and $I\mid\Psi(G)\mid\Psi(BG)$ , so $I\mid\Psi(AF)+\Psi(BG)=\Psi(H)$ .

The conclusion follows.

Z K Y

The post below has been deleted. Click to close.

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

niksic

81 posts

niksic

#37 h Jun 13, 2020, 3:50 PM

Y by

Take some three polynomials $P(x)=\sum_{i=0}^{\infty}a_ix^i$ , $Q(x)=\sum_{i=0}^{\infty}b_ix^i$ and $R(x)=\sum_{i=0}^{\infty}c_ix^i$ , where coefficients are zero if large enough for simplicity

We have $\Psi(PQ) = \Psi(\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}a_ib_jx^{i+j}) = \sum_{i=0}^{\infty}\sum_{j=0}^{\infty}a_ib_jx^{p^{i+j}}$ , now notice $\Psi(P+Q)=\Psi(P)+\Psi(Q)$ and the main claim:
$gcd(\Psi(PQ), \Psi(PR)) = gcd(\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}a_ib_jx^{p^{i+j}}, \sum_{i=0}^{\infty}\sum_{j=0}^{\infty}a_ic_jx^{p^{i+j}}) =$ $= gcd(\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}a_i(b_j-c_j)x^{p^{i+j}}, \sum_{i=0}^{\infty}\sum_{j=0}^{\infty}a_ic_jx^{p^{i+j}}) = gcd(\Psi(P(Q-R)), \Psi(PR))$
This follows from $gcd(X,Y)=gcd(X-Y,Y)$ , the standard number theory lemma but for polynomials. Now, assume $F=PQ$ , $G=PR$ and $gcd(Q,R)=1$ and $gcd(F,G)=P$ . Keep repeating the main result above, $gcd(\Psi(PQ), \Psi(PR))=gcd(\Psi(P(Q-R)), \Psi(PR))$ , and by the Euclidian algorithm we arrive at $gcd(\Psi(F),\Psi(G)) = gcd(\Psi(P), \Psi(0)) = \Psi(P) = \Psi(gcd(F,G)) \implies gcd(\Psi(F),\Psi(G)) = \Psi(gcd(F,G))$ , which we wanted to prove $\blacksquare$

EDIT: Am I mistaken or does this method generalize from $\mathbb{F}_p[x]$ to $\mathbb{Z}[x]$ ?

This post has been edited 2 times. Last edited by niksic, Jun 13, 2020, 8:08 PM

Z K Y

The post below has been deleted. Click to close.

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

william122

1576 posts

william122

#38 h Jun 15, 2020, 3:55 PM

Y by

First, we claim that $a_1^p+a_2^p+\ldots +a_n^p$ leaves a remainder with all terms divisible by $p$ when divided by $a_1+\ldots +a_n$ . We prove this with induction on $n$ . For $n=2$ , the claim is trivial as $a_1+a_2|a_1^p+a_2^p$ . Now, suppose the claim is true for $n-1$ . Now, $a_1^p+a_2^p+\ldots+a_n^p=(a_1^p+\ldots + a_{n-2}^p+(a_{n-1}+a_n)^p)-\sum_{i=1}^{p-1}a_{n-1}^ia_n^{p-i}\binom{p}{i}$ For the first term, we are guaranteed a remainder divisible by $p$ by induction. On the other hand, for the latter term, $\binom{p}{i}$ is always divisible by $p$ , so of course, subtracting it will preserve the fact that the remainder has all coefficients divisible by $p$ , as desired.

Now, note that if $P(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots + a_0$ , then $\Psi(P(x))=a_nx^{p^n}+\ldots +a_0x^{p^0}$ and $\Psi(xP(x))=\left(a_nx^{p^n}\right)^p+\ldots +\left(a_0x^{p^0}\right)^p$ as $a^p\equiv a\pmod p$ . Now, using our claims, the remainder when $\Psi(xP(x))$ is divided by $\Psi(P(x))$ has all terms divisible by $p$ , and since we are working in $\mathbb{F}_p$ , this means $\Psi(P(x))|\Psi(xP(x))$ . Using induction, this gives $\Psi(P(x))|\Psi(x^kP(x))$ , and since $\Psi$ is additive, we get $\Psi(P(x))|\Psi(Q(x))$ whenver $P|Q$ .

To finish, we just use the Euclidean Algorithm. We have that $\gcd(\Psi(P(x)),\Psi(Q(x)))=\gcd(\Psi(P(x)),\Psi(Q(x)-R(x)P(x)))$ by properties of $\gcd$ , additivity of $\Psi$ , and the fact that $\Psi(P(x))|\Psi(P(x)R(x))$ , so applying normal Euclidean algorithm gives $\gcd(\Psi(P(x)),\Psi(Q(x)))=\gcd(\Psi(\gcd(P(x),Q(x))),\Psi(\gcd(P(x),Q(x))))=\Psi(\gcd(P(x),Q(x)))$ as desired.

This post has been edited 1 time. Last edited by william122, Jun 18, 2020, 9:48 PM

Z K Y

The post below has been deleted. Click to close.

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

Idio-logy

206 posts

Idio-logy

#39 h Nov 28, 2020, 7:24 AM

Y by

This is essentially the same idea as brian22's solution, but phrased differently. We define a notation $[a_0, a_1, a_2, \dots, a_n]$ recursively such that
$[a_0,a_1,\dots,a_n] = a_0 + [a_1,\dots,a_n]^p.$ Then we can prove by induction (using a property of Frobenius endomorphism) that
$[a_0x, a_1x,\dots, a_nx] = \Psi(a_0 + a_1x+\dots +a_nx^n).$ Notice also that $[a_0,\dots,a_n] + [b_0,\dots,b_n] = [a_0+b_0,\dots, a_n+b_n]$ and $c[a_0,\dots,a_n] = [ca_0,\dots,ca_n]$ for any $c\in \mathbb{F}_p$ .

Claim. If $a(x) \mid f(x)$ , then $\Psi(a(x)) \mid \Psi(f(x)).$

Proof. Let $a(x) = a_0 + a_1x+ \dots +a_nx^n$ and $f(x) = a(x)b(x)$ where $b(x) = b_0 + b_1x + \dots + b_m x^m$ . Write $A = [a_0, a_1, \dots, a_n] = \Psi(a(x))$ , then it suffices for us to prove that
$\Psi(f(x)) = [b_0A, b_1A, \dots, b_mA].$ This can be easily shown by expanding out the entire thing. $\square$

Back to the original problem, we use the Euclidean algorithm. Suppose WLOG that $G(x) = F(x)\cdot Q(x) + R(x)$ where $\deg R < \deg F$ , and assume the problem is true for the pair $(R,F)$ . Our notation implies $\Psi$ is linear, so
$\gcd(\Psi(F), \Psi(G)) = \gcd(\Psi(F), \Psi(R) + \Psi(F\cdot Q)) = \gcd(\Psi(F), \Psi(R)) = \Psi(\gcd(F,R)) = \Psi(\gcd(F,G))$ as desired.

This post has been edited 1 time. Last edited by Idio-logy, Nov 28, 2020, 7:25 AM

Z K Y

The post below has been deleted. Click to close.

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

pi271828

3359 posts

pi271828

#40 h Nov 30, 2022, 2:32 PM

Y by

Claim: $\Psi(F) | \Psi(G)$ iff $F | G$ . We can split this claim into two parts, proving that $\Psi(F) | \Psi(G) \implies F | G$ , and $F | G \implies \Psi(F) | \Psi(G)$ . Notice that this claim is enough to complete the problem.

For the first part, notice that you can use the fact that $P(A+B) = P(A)+P(B)$ to split the polynomials into monomials.

For the second part, FTSOC, we let $F = GA + R$ where $R$ is a nonzero polynomial with $\deg R < \deg P$ . This implies that $\Psi(Q) = \Psi(PA) + \Psi(R)$ . $\Psi(PA) \equiv 0 \pmod \Psi(P)$ , so therefore $\Psi(P)|\Psi(R)$ . Since $\deg R < \deg P$ , $R \equiv 0$ , therefore implying the result. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Inconsistent

1455 posts

Inconsistent

#41 h Dec 23, 2022, 11:41 PM

Y by

Just brute force by inventing your own EA. Let $[F, G]$ denote the statement that the desired condition holds for $F, G$ .

First: $\Psi$ is linear so $[F, G] \leftrightarrow [F-kG, G]$
Next: By substitution, $[F, G] \leftrightarrow [xF, xG]$
Next: By symmetry, $[F, G] \leftrightarrow [G, F]$
Finally: I claim $[xF, G] \leftrightarrow [F, G]$ if $x \nmid G$ .

This is because $\Psi(xF)(x) = \Psi(F)(x^p) = \Psi(F)^p$ , so it suffices to show $\gcd(\Psi(F)^p, \Psi(G)) = \gcd(\Psi(F), \Psi(G))$ . This follows immediately from the claim that $\Psi(G)$ has no double roots for arbitrary $G$ . This is because given $\alpha$ a root of $\Psi(G)$ , $\Psi(G)' = G(0)$ which must be nonzero by assumption, finishing.

Now, these operations together compose the backward Euclidean algorithm, which cancels the constant term and divides out factors of $x$ until the degree is minimal, finishing.

Z K Y

The post below has been deleted. Click to close.

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

IAmTheHazard

5000 posts

IAmTheHazard

#42 h Feb 2, 2023, 3:35 PM

Y by

Really nice.

We have the three following key properties:

$\Psi(f+g)=\Psi(f)+\Psi(g)$ . This is obvious.
$c\Psi(f)=\Psi(cf)$ , where $c \in \mathbb{F}_p$ . This is clear because $c^p=c$ in $\mathbb{F}_p$ .
$\Psi(f)^p=\Psi(\mathrm{id}\cdot f)$ (as a polynomial equality). This is because if $f(x)=a_nx^n+\cdots+a_0$ , then both sides are equal to $a_nx^{p^{n+1}}+\cdots+a_0x^{p^1}$ , since for any $a \in \mathbb{F}_p[x]$ we have $a(x^p)=a(x)^p$ .

Now we will essentially apply the Euclidean algorithm to $\Psi(\gcd(F,G))$ and essentially show that the same thing works on $\gcd(\Psi(F),\Psi(G))$ . Indeed, WLOG let $\deg F>\deg G$ select $c \in \mathbb{F}_p$ and $k\in \mathbb{Z}_{\geq 0}$ such that
$\deg F-cx^kG < \deg F,$ so
$\Psi(\gcd(F(x),G(x)))=\Psi(\gcd(F(x)-cx^kG(x),G(x)))$ Likewise, we have
$\gcd(\Psi(F(x)),\Psi(G(x)))=\gcd(\Psi(F(x))-c\Psi(G(x))^{p^k},\Psi(G(x)))=\gcd(\Psi(F(x)-cx^kG(x)),\Psi(G(x))).$ Thus by repeatedly doing this (which is just the Euclidean algorithm on $F$ and $G$ ), we reduce $\Psi(\gcd(F,G))$ to $\Psi(\gcd(H,H))=\Psi(H)$ where $H=\gcd(F,G)$ . The same sequence of operations reduce $\gcd(\Psi(F),\Psi(G))$ to $\gcd(\Psi(H),\Psi(H))$ , which clearly equals $\Psi(H)$ as well. Thus we are done. $\blacksquare$

Remark: My initial solution to this was a bit different. Similarly to the third key property we may prove the more general statement that $\Psi(fg)=\Psi(f)(\Psi(g))$ (if $f \equiv \mathrm{id}$ we obtain the third key property). Then if $F \equiv ab$ and $G \equiv ac$ where $b \perp c$ , we want to prove that $\Psi(a)=\gcd(\Psi(ab),\Psi(ac))=\gcd(\Psi(b)(\Psi(a)),\Psi(c)(\Psi(a)))$ . From here the solution basically remains the same. The "necessity" of the third property or its generalization come from a need to find some property of $\Psi$ which will connect it with $\gcd$ .
It's a bit unclear how the third property actually relates to $\gcd$ , but in its general form it seems much clearer, since $\gcd$ is certainly related to products of polynomials. Indeed, from the general form it is essentially immediate that at the very least we have $\Psi(a) \mid \gcd(\Psi(b)(\Psi(a)),\Psi(c)(\Psi(a)))$ , which indicates that this route should be pushed further.

This post has been edited 3 times. Last edited by IAmTheHazard, Feb 2, 2023, 3:38 PM

Z K Y

The post below has been deleted. Click to close.

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

Leo.Euler

577 posts

Leo.Euler

#43 h Jul 27, 2023, 5:30 PM

Y by

Neat problem, the key idea is to inductively show that all pairs $(F(x), G(x))$ in $\mathbb{F}_p[x]^2$ work. For $(F, G) \in \mathbb{F}_p[x]^2$ , let $\alpha(F, G) = \begin{cases} 1 & (F, G) \ \text{works} \\ 0 & (F, G) \ \text{does not work}. \end{cases}$ We say that $(F, G) \sim (H, K)$ if $\alpha(F, G)=1$ implies $\alpha(H, K)=1$ .

Lemma: [Symmetry] We have $(F, G) \sim (G, F)$ . Proof. Note that $\gcd(F, G)$ is symmetric with respect to $F, G$ , so we are done. :yoda:

The above lemma completes the proof of the fact that $\sim$ is an equivalence relation.

Lemma: [Euclidean algorithm] We have $(F, G) \sim (F-G, G)$ , $(F, G) \sim (F+G, G)$ .
Proof. This holds due to the linearity property of $\Psi$ . :yoda:

Lemma: [Factoring monomials] We have $(F, G) \sim (xF, xG)$ .
Proof. By definition, it can be easily seen that $\begin{align*} \Psi(xF(x)) &= F(x^p) \\ &= F(x)^p , \end{align*}$ from which the lemma follows (this is by the use of $\gcd$ on $p$ th powers of polynomials). :yoda:

Now onto the hardest one.

Lemma: [Factoring monomials from one term] If $x \nmid G$ , then $(F, G) \sim (xF, G)$ .
Proof. As in the proof of the prior lemma, $\Psi(xF(x)) = \Psi(F)^p$ . Note that $\Psi(G)'(x)=G(0)$ for all $x$ must be nonzero, so $\Psi(G)$ must have no double root. Thus, $\gcd(\Psi(F)^p, \Psi(G)) = \gcd(\Psi(F), \Psi(G))$ , and we are done from our first observation. :yoda:

Using the above lemmas, we can inductively show that $\alpha(F, G)=1$ for all $F, G$ by following an algorithm similar to that of the Euclidean Algorithm. We are done. :starwars:

This post has been edited 2 times. Last edited by Leo.Euler, Jul 27, 2023, 8:36 PM

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8847 posts

HamstPan38825

#44 h Oct 21, 2023, 6:01 PM

Y by

The key is to offer the following characterization of $\Psi$ multiplicatively.

Claim. We have $\Psi(fg) = \Psi(f) \circ \Psi(g)$ .

Proof. It suffices to prove the monomial case $\Psi(x^n f(x)) = \Psi(f(x))^{p^n}$ because $\Psi$ is additive. To see this, set $f(x) = pg(x) + h(x)$ in $\mathbb Z$ and apply the binomial theorem. $\blacksquare$

Now we obviously have $\Psi(\gcd(f, g)) \mid \gcd(\Psi(f), \Psi(g))$ because if $f \mid g$ , then $\Psi(f)\mid \Psi(g)$ . (This is because in the above expression, $\Psi$ has no constant term.) To show the other direction, use Bezout's lemma: there exists polynomials $a, b$ such that $af+bg = \gcd(f, g).$ Taking $\Psi$ of both sides, $\Psi(f) \circ \Psi(a) + \Psi(g) \circ \Psi(b) = \Psi(\gcd(f, g)).$ On the other hand, $\gcd(\Psi(f), \Psi(g))$ divides both terms on the LHS, so it divides the RHS too.

Thus $\Psi(\gcd(f, g)) =\gcd(\Psi(f), \Psi(g))$ , as needed.

This post has been edited 1 time. Last edited by HamstPan38825, Mar 15, 2024, 3:37 PM

Z K Y

The post below has been deleted. Click to close.

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

Shreyasharma

666 posts

Shreyasharma

#45 h Apr 3, 2024, 5:42 PM

Y by

Napkin wrote:

(USA Team Selection Test 2016) Let $\mathbb{F}_p$ denote the integers modulo a fixed prime $p$ . Define $\Psi \colon \mathbb{F}_p[x] \mapsto \mathbb{F}_p[x]$ by,
$\begin{align*} \Psi\left(\sum_{i = 0}^n a_ix^i\right) = \sum_{i = 0}^n a_ix^{p^i} \end{align*}$ Denote by $S$ the image of $\Psi$ . Show that,

$S$ is a ring with addition given by polynomial addition, and multiplication given by \textit{function composition}.
Prove that $\Psi \colon \mathbb{F}_p[x] \mapsto S$ is then a ring isomorphism.

We begin by characterizing $S$ ; Take two arbitrary elements in $S$ :
$\begin{align*} A = \sum_{i= 0}^{n} a_ix^{p^i}\\ B = \sum_{i = 0}^n b_ix^{p_i} \end{align*}$ with some $a_i$ and $b_i$ possibly $0$ .

Claim: $S$ is closed under addition.
Proof. Simply note that,
$\begin{align*} A + B = \sum_{i = 0}^n (a_i + b_i)x^{p^i} = \sum_{i = 0}^n (a_i + b_i \bmod{p})x^{p^i} \in S \end{align*}$ Also, there is an additive identity, namely the $0$ polynomial. $\square$

Claim: $S$ obeys multiplication given by function composition.
Proof. We first demonstrate $S$ obeys exponentiation by powers of $p$ . Then we wish to show that,
$\begin{align*} \left( \sum_{i = 0}^n a_ix^{p^i} \right)^p &\in S\\ \end{align*}$ We are working with something of the form $(y_1 + y_2 + \dots + y_n)^p \equiv 0 \bmod{p}$ . Note that lower order terms not of the form $y_i^{p}$ die modulo $p$ ; to see this say that some term in our expansion is of the form,
$\begin{align*} \prod_{i = 0}^k y_i^{e_i} \end{align*}$ where we without loss of generality assume that the $k$ variables are $y_1$ , $y_2$ , and so on. The coefficient of this term is then,
$\begin{align*} \binom{p}{e_1} \cdot \binom{p - e_1}{e_2} \dots \end{align*}$ Clearly $p$ divides this coefficient, given that $e_1 < p$ , thus proving that these terms vanish. This in turn proves that $S$ behaves well under exponentiation by $p$ and in fact that,
$\begin{align*} \left( \sum_{i = 0}^n a_ix^{p^i} \right)^{p^t} &\in S\\ \end{align*}$ lies in $S$ for any $t$ , by induction. Now to see that $S$ obeys function composition, simply take $A, B \in S$ and note,
$\begin{align*} A \circ B = \sum_{i = 0}^n a_iB^{p^i} \in S \end{align*}$ which is clearly in $S$ as $S$ is closed under exponentiation by powers of $p$ and addition. Moreover it clearly has identity element $x$ , is associative, and distributes over addition. $\square$

Therefore $S = (S, + , \circ)$ is a ring, finishing the first bullet.

For the second bullet we wish to show that $\Psi \colon \mathbb{F}_p[x] \mapsto S$ is a ring isomorphism. Thus we wish to show $\Psi$ is a bijective map satisfying,

$\Psi(x + y) = \Psi(x) + \Psi(y)$
$\Psi(x \times y) = \Psi(x) \circ \Psi(y)$
$\Psi(1) = x$

The first and last bullets follow easily from the definition of $\Psi$ , and so does the bijectivity of the map. It remains to verify the second bullet; namely we wish to show,
$\begin{align*} \Psi(AB) = \Psi(A) \circ \Psi(B) \end{align*}$ The right hand side clearly is just,
$\begin{align*} \sum_{i = 0}^n a_iB^{p^i} &= \sum_{i = 0}^n \left( a_i\left(\sum_{j = 0}^n b_jx^{p^{j + 1}} \right) \right)\\ &= \sum_{i = 0}^n \left(\sum_{j = 0}^n a_ib_jx^{p^{i + j}} \right) \end{align*}$ whereas we may observe the left hand side is,
$\begin{align*} \Psi\left(\sum_{i = 0}^n a_ix^i \cdot B \right) &= \sum_{i = 0}^n \Psi(a_ix^i \cdot B)\\ &= \sum_{i = 0}^n a_i \Psi\left(\sum_{j = 0}^n b_jx^{i + j}\right)\\ &= \sum_{i = 0}^n \left(\sum_{j = 0}^n a_ib_jx^{p^{i + j}} \right) \end{align*}$ which are clearly equal. This finishes the problem.

Remarks: Oops I got braindead and needed help on the last part (which was supposed to be easy :wacko:

This post has been edited 1 time. Last edited by Shreyasharma, Apr 3, 2024, 5:43 PM

Z K Y

The post below has been deleted. Click to close.

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

KevinYang2.71

393 posts

KevinYang2.71

#46 h May 10, 2024, 4:17 AM • 5 Y

Y by deduck, purplepenguin2, Orthogonal., LostDreams, EpicBird08

Let $\mathbb{N}$ denote the set of natural numbers, including $0$ . Let $R$ be the ring consisting of the set of $\mathbb{F}_p$ -polynomials
$\left\{a_n x^{p^n}+a_{n-1} x^{p^{n-1}}+\cdots+a_1 x^p+a_0x\mid n\in\mathbb{N};a_0,\ldots,a_n\in\mathbb{F}_p\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$ . Let $\overline{\mathbb{F}_p}$ denote the algebraic closure of $\mathbb{F}_p$ .

Lemma 1. $\mathbb{F}_p[x]$ is isomorphic to $R$ with isomorphism $\Psi$ .

Proof. We first prove that $\Psi:\mathbb{F}_p[x]\rightarrow R$ is a homomorphism:

$\Psi(f+g)=\Psi(f)+\Psi(g)$ is trivial.
We have $\Psi(x^\alpha x^\beta)=x^{p^{\alpha+\beta}}=\left(x^{p^\alpha}\right)^{p^\beta}=\Psi(x^\alpha)\circ\Psi(x^\beta)$ . Clearly we also have $\Psi(cx^\alpha)=c\Psi(x^\alpha)$ for any constant $c$ . It follows that $\Psi(fg)=\Psi(f)\Psi(g)$ .
$\Psi(1)=x$ is trivial.

Clearly $\ker\Psi=\{1\}$ and $\Psi$ is surjective so $\Psi$ is an isomorphism. $\square$

Let $\overline{R}\supseteq R$ be the ring consisting of the set of $\overline{\mathbb{F}_p}$ -polynomials
$\left\{a_n x^{p^n}+a_{n-1} x^{p^{n-1}}+\cdots+a_1 x^p+a_0x\mid n\in\mathbb{N};a_0,\ldots,a_n\in\overline{\mathbb{F}_p}\right\},$ with addition $+$ and multiplication $\circ$ . Let $\tilde{\Psi}:\overline{\mathbb{F}_p}[x]\rightarrow\overline{R}$ be the extension of $\Psi$ given by
$\sum_{i=0}^n a_i x^i\mapsto\sum_{i=0}^n a_i x^{p^i}.$ By the same argument as Lemma 1, $\tilde{\Psi}$ is an isomorphism.

Lemma 2. For $f\in\overline{R}$ and all $a,b\in\overline{\mathbb{F}_p}$ and $c\in\mathbb{F}_p$ , we have

$f(a+b)=f(a)+f(b)$ ,
$f(ca)=cf(a)$ .

Proof. The first part follows directly from freshman's dream. For the second part, note that $c^{p^\alpha}=c$ for all $a\in\mathbb{N}$ by FlT. The result immediately follows. $\square$

Lemma 3. All $f\in\overline{R}$ (viewed as a polynomial in $\overline{\mathbb{F}_p}[x]$ ) is separable.

Proof. The formal derivative of $f$ is equal to the coefficient of $x$ in $f$ , which is in $\overline{\mathbb{F}_p}$ . Thus the formal derivative of $f$ is relatively prime with $f$ so $f$ is separable. $\square$

For $f\in\overline{R}$ , let
$Z(f):=\{r\in\overline{\mathbb{F}_p}\mid f(r)=0\}$ denote the set of roots of $f$ . By Lemma 3, all the roots of $f$ have multiplicity $1$ . It follows that
$f(x)=\prod_{r\in Z(f)}(x-r).$ Lemma 4. For all $f\in\overline{R}$ , $Z(f)$ forms a vector space over $\mathbb{F}_p$ , with addition and multiplication the same as that of $\overline{\mathbb{F}_p}$ .

Proof. We first prove that $Z(f)\subseteq\overline{\mathbb{F}_p}$ is an abelian group:

If $r_1,r_2\in Z(f)$ , then $f(r_1+r_2)=f(r_1)+f(r_2)=0$ by Lemma 2 so $r_1+r_2\in Z(f)$ .
$Z(f)$ is commutative because the additive group of $\overline{\mathbb{F}_p}$ is abelian.
$f(0)=0$ because $f$ has no constant term. Thus $0\in Z(f)$ .
If $r\in Z(f)$ , then $f(-r)=-f(r)=0$ by Lemma 2 so $-r\in Z(f)$ .

For all $c\in\mathbb{F}_p$ and $r\in Z(f)$ , we have $f(cr)=cf(r)=0$ by Lemma 2 so $cr\in Z(f)$ . Thus $Z(f)$ is a vector space over $\mathbb{F}_p$ . $\square$

From now on, " $=$ " will denote equality up to multiplication by a unit of $\overline{\mathbb{F}_p}[x]$ .

Lemma 5. If $F,G\in\overline{R},H\in\overline{\mathbb{F}_p}[x]$ and $F(x)=H(G(x))$ , then $H\in\overline{R}$ .

Proof. Assume for the sake of contradiction $H\not\in\overline{R}$ . Then $H$ has a $cx^\alpha$ term where $\alpha$ is not a power of $p$ . Take the minimum such $\alpha$ . Let
$G(x)=:a_nx^{p^n}+a_{n-1}x^{p^{n-1}}+\cdots+a_0x.$ Clearly the $x^\alpha$ term of $H(G(x))$ appears only in $c(G(x))^\alpha$ , so it has coefficient $ca_0^\alpha\neq 0$ . This implies that $F$ has an $x^\alpha$ term, a contradiction. $\square$

Lemma 6. For nonzero polynomials $F,G\in\overline{\mathbb{F}_p}[x]$ , we have $G\mid F$ if and only if $\tilde{\Psi}(G)\mid\tilde{\Psi}(F)$ .

Proof. Suppose $F=HG$ for some $H\in\overline{\mathbb{F}_p}[x]$ . Then $\tilde{\Psi}(F)=\tilde{\Psi}(H)\circ\tilde{\Psi}(G)$ . Since $\tilde{\Psi}(H)$ has no constant term, it follows that $\tilde{\Psi}(G)\mid\tilde{\Psi}(F)$ .

Now let $P:=\tilde{\Psi}(F)$ and $Q:=\tilde{\Psi}(G)$ , and suppose $Q\mid P$ . Then $Z(Q)$ is a subspace of $Z(P)$ . Let $\alpha:=\dim Z(P)$ and $\beta:=\dim Z(Q)$ . Let $e_1,\ldots,e_\beta$ be a basis for $Z(Q)$ and extend it to a basis $e_1,\ldots,e_\alpha$ for $Z(P)$ . We have
$\begin{align*} P(x)&=\prod_{r\in Z(P)}(x-r)\\ &=\prod_{c_1,\ldots,c_\alpha\in\mathbb{F}_p}\left(x-\sum_{i=1}^\alpha c_ie_i\right)\\ &=\prod_{c_{\beta+1},\ldots,c_\alpha\in\mathbb{F}_p}\prod_{c_1,\ldots,c_\beta\in\mathbb{F}_p}\left(\left(x-\sum_{i=\beta+1}^\alpha c_ie_i\right)-\sum_{j=1}^\beta c_je_j\right)\\ &=\prod_{c_{\beta+1},\ldots,c_\alpha\in\mathbb{F}_p}Q\left(x-\sum_{i=\beta+1}^\alpha c_ie_i\right)\\ &=\prod_{c_{\beta+1},\ldots,c_\alpha\in\mathbb{F}_p}\left(Q(x)-\sum_{i=\beta+1}^\alpha c_i Q(e_i)\right)\\ &=A(Q(x)) \end{align*}$ where
$A(x):=\prod_{c_{\beta+1},\ldots,c_\alpha\in\mathbb{F}_p}\left(x-\sum_{i=\beta+1}^\alpha c_i Q(e_i)\right).$ By Lemma 5, $A\in\overline{R}$ so $P=A\circ Q$ . It follows that $F=\tilde{\Psi}^{-1}(A)\cdot G$ so $G\mid F$ , as desired. $\square$

Lemma 7. Let $\mathbb{F}$ be an algebraic extension of $\mathbb{F}_p$ . For nonzero polynomials $F,G\in\mathbb{F}[x]$ , we have $G\mid F$ if and only if $\tilde{\Psi}(G)\mid\tilde{\Psi}(F)$ (where divisibility is taken in $\mathbb{F}[x]$ ).

Proof. Since $\mathbb{F}$ is an algebraic extension, it is a subfield of $\overline{\mathbb{F}_p}$ . Suppose $F=HG$ for some $H\in\mathbb{F}[x]$ . Then $\tilde{\Psi}(F)=\tilde{\Psi}(H)\circ\tilde{\Psi}(G)$ . Since $\tilde{\Psi}(H)$ has no constant term, it follows that $\tilde{\Psi}(G)\mid\tilde{\Psi}(F)$ .

If $\tilde{\Psi}(G)\mid\tilde{\Psi}(F)$ , by Lemma 6 we have $F=GH$ for some $H\in\overline{\mathbb{F}_p}[x]$ . Let
$\begin{align*} F(x)&=:a_\alpha x^\alpha+\cdots+a_0\\ G(x)&=:b_\beta x^\beta+\cdots+b_0\\ H(x)&=:c_\gamma x^\gamma+\cdots+c_0. \end{align*}$ Then $a_0=b_0c_0$ so $c_0\in\mathbb{F}$ . Assume we already have $c_0,\ldots,c_i\in\mathbb{F}$ . Then
$b_{i+1}c_0+b_ic_1+\cdots+b_1c_i+b_0c_{i+1}=a_{i+1}\in\mathbb{F}$ (where we set $b_{\beta+1},\ldots$ equal to $0$ ) so $c_{i+1}\in\mathbb{F}$ . Thus $H\in\mathbb{F}[x]$ as desired. $\square$

Let $K$ be an algebraic extension of $\mathbb{F}_p$ (for the problem just take $K:=\mathbb{F}_p$ ). Fix $F,G\in K[x]$ and let $H_1:=\gcd(F,G)$ ( $K[x]$ is a Euclidean domain because $K$ is a field). By Lemma 7, $\tilde{\Psi}(H_1)\mid\tilde{\Psi}(F)$ and $\tilde{\Psi}(H_1)\mid\tilde{\Psi}(G)$ so
$\tilde{\Psi}(H_1)\mid\gcd(\tilde{\Psi}(F),\tilde{\Psi}(G)).$ Let $H_2:=\gcd(\tilde{\Psi}(F),\tilde{\Psi}(G))$ . By Lemma 7, $\tilde{\Psi}^{-1}(H_2)\mid F$ and $\tilde{\Psi}^{-1}(H_2)\mid G$ so
$\tilde{\Psi}^{-1}(H_2)\mid\gcd(F,G).$ It follows that $H_2\mid\tilde{\Psi}(H_1)$ and $\tilde{\Psi}(H_1)\mid H_2$ so $H_2=\tilde{\Psi}(H_1)$ , as desired. $\square$

This post has been edited 21 times. Last edited by KevinYang2.71, Jun 19, 2024, 5:08 AM

Z K Y

The post below has been deleted. Click to close.

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

john0512

4170 posts

john0512

#47 h Oct 22, 2024, 10:11 PM • 6 Y

Y by dolphinday, megarnie, Leo.Euler, qwerty123456asdfgzxcvb, OronSH, megahertz13

All statements made in this solution are in $\mathbb F_p$ .

Run two Euclidean algorithms in parallel!

Ritwin writes two polynomials in $\mathbb F_p$ , $B$ and $C$ , on a whiteboard. Ivy writes $\Psi(B)$ and $\Psi(C)$ on the whiteboard. In each step, they select a nonnegative integer $k$ , and say Ritwin has $(R_1,R_2)$ and Ivy has $(I_1,I_2)$ written respectively. Then, Ritwin replaces $R_2$ with $R_2-x^kR_1$ (either that or replace $R_1$ with $R_1-x^kR_2$ ), and Ivy replaces $I_2$ with $I_2-I_1^{p^k}$ , (or other way, but using the same index as Ritwin).

Claim: During every step of this process, we always have $I_1=\Psi(R_1)$ and $I_2=\Psi(R_2)$ . Use induction. This is clearly true at the start. Note that
$\Psi(R_2-x^kR_1)=\Psi(R_2)-\Psi(x^kR_1)=I_2-\Psi(x^kR_1).$ Now, we wish to show that $\Psi(x^kR_1)=\Psi(R_1)^{p^k}$ , to show that Ivy's new polynomial is still the $\Psi$ of Ritwin's new polynomial. However, if we shift all the exponents of $x$ up by $k$ before applying $\Psi$ , it multiplies every exponent later by $p^k$ due to the definition of $\Psi$ . However, on the RHS, raising the result of $\Phi(R_1)$ to the power of $p^k$ is also equivalent to multiplying every exponent by $p^k$ as we are working in $\mathbb F_p$ (Freshman's dream!), so we have shown the claim.

Have Ritwin perform the Euclidean algorithm on $B$ and $C$ until one of his polynomials is $0$ . Then, suppose he ends with $(0,G)$ . By the above claim, Ivy ends with $(0,\Phi(G))$ . However, note that because $I_1\mid I_1^{p^k},$ Ivy is also performing a Euclidean algorithm, which means from Ivy's process that
$\gcd(\Phi(B),\Phi(C))=\Phi(G)$ and we are done!

Remark: The way found this solution was like this. First, I realized that we can freely subtract constant multiples of $B$ from $C$ because $\Psi$ is an additive function so the Euclidean algorithm is automatically being handled there. However, this alone isn't enough, as eventually in the algorithm, once the degrees are different, we must start subtracting multiples of $x^k$ . So first, I just experimented with trying to replace $C$ with $C-xB$ . When this is done, on the other side, $\gcd(\Psi(B),\Psi(C))$ becomes $\gcd(\Psi(B),\Psi(C-xB))=\gcd(\Psi(B),\Psi(C)-\Psi(xB)).$ In order for this to be a legal Euclidean algorithm move, we must have $\Psi(B)\mid \Psi(xB)$ . After a bit of playing around however, I realized that $\Psi(xB)$ is just $\Psi(B)^p$ , and then I realized this generalized to higher powers of $x$ as well and solved the problem. Finally, I phrased the solution this way to hopefully be easier to understand, and also of course as a tribute to some friends from MOP

Z K Y

The post below has been deleted. Click to close.

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

kotmhn

56 posts

kotmhn

#48 h Dec 12, 2024, 6:25 AM

Y by

Cool question, though i believe was a bit on the easier side for a p3.
As in i was able to get it in 2ish hours .
And if you know grp theory its even easier.

Z K Y

The post below has been deleted. Click to close.

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

OronSH

1718 posts

OronSH

#49 h Jan 25, 2025, 1:14 PM • 1 Y

Y by ihategeo_1969

It suffices to show $P\mid Q\iff\Psi(P)\mid\Psi(Q)$ .

First note $\Psi(cP)=c\Psi(P)$ and $\Psi(P+Q)=\Psi(P)+\Psi(Q)$ .The main idea is $\Psi(P)^p=\Psi(xP)$ , which follows by binomial theorem and FLT. Now if $Q=P\cdot\sum_{i=0}^na_ix^i$ we have $\Psi(Q)=\sum_{i=0}^n a_i\Psi(x^iP)=\sum_{i=0}^na_i\Psi(P)^{p^i}$ which is divisible by $\Psi(P)$ . For the other direction, if $P\nmid Q$ consider the polynomial $Q'$ for which $P\mid Q'$ and $\deg(Q'-Q)<\deg P$ . Then $\Psi(P)\mid\Psi(Q')-\Psi(Q)=\Psi(Q'-Q)$ but $\deg\Psi(P)>\deg\Psi(Q'-Q)$ , contradiction, so we finish.

Z K Y

The post below has been deleted. Click to close.

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

cj13609517288

1862 posts

cj13609517288

#50 h Feb 1, 2025, 4:08 PM • 1 Y

Y by OronSH

The main observation of the problem is that
$\left(\sum a_ix^{p^i}\right)^p=\sum a_ix^{p^{i+1}}.$ Therefore, $\Psi(F)\mid\Psi(xF)$ . Since $\Psi$ is a linear transformation, we can then get that if $F\mid G$ , then $\Psi(F)\mid\Psi(G)$ .

So the LHS divides the RHS. But note that we can just apply the Euclidean Algorithm to the RHS to always stay inside the image of $\Psi$ , done.

Z K Y

N Quick Reply