x^m-y^n irreducible when (m,n)=1

Art of Problem Solving

AoPS Online

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

No tags match your search

M

x^m-y^n irreducible when (m,n)=1

G H J

Reveal topic tags

pigeonhole principle

relatively prime

algebra proposed

L

G H BBookmark kLocked kLocked NReply

Source: ELMO Shortlist 2012, A5

The post below has been deleted. Click to close.

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

4302 posts

#1 h Jul 2, 2012, 2:50 AM • 2 Y

Y by Adventure10 and 1 other user

Prove that if $m,n$ are relatively prime positive integers, $x^m-y^n$ is irreducible in the complex numbers. (A polynomial $P(x,y)$ is irreducible if there do not exist nonconstant polynomials $f(x,y)$ and $g(x,y)$ such that $P(x,y) = f(x,y)g(x,y)$ for all $x,y$ .)

David Yang.

Z K Y

The post below has been deleted. Click to close.

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

74 posts

#2 h Jul 2, 2012, 11:12 AM • 6 Y

Y by iarnab_kundu, jjlim7, Adventure10, Mango247, and 2 other users

math154 wrote:

Prove that if $m,n$ are relatively prime positive integers, $x^m-y^n$ is irreducible in the complex numbers. (A polynomial $P(x,y)$ is irreducible if there do not exist nonconstant polynomials $f(x,y)$ and $g(x,y)$ such that $P(x,y) = f(x,y)g(x,y)$ for all $x,y$ .)

David Yang.

Assume $x^m-y^n$ can be written as $f(x,y)g(x,y)$ , where $f,g$ have complex coefficient. Then for all $t$ , we have $f(t^n,t^m)=0$ or $g(t^n,t^m)=0$ .
W.L.O.G., we let there are infinitely $t$ , such that $f(t^n,t^m)=0$ .
Then we have for all $t$ , $f(t^n,t^m)=0$ .
Let $f=\sum_{0\le i\le m, 0\le j\le n}a_{i,j}x^iy^j$ , then $0\equiv f(t^n,t^m)=\sum_{0\le i\le m, 0\le j\le n}a_{i,j}t^{ni+mj}$ , where $a_{i,j}$ is the complex coefficient. Note that for all positive integer $i_0$ , $i_1$ , $j_0$ , $j_1$ , we have $ni_0+mj_0=ni_1+mj_1 \Leftrightarrow n(i_0-i_1)=m(j_1-j_0)$ . That means if and only if $i_0-i_1=m$ , $j_1-j_0=n$ , we have $ni_0+mj_0=ni_1+mj_1$
Therefore for all $(i,j)$ not equal to $(m,0)$ or $(0,n)$ , we must have $a_{i,j}=0$ . Also $a_{m,0}=-a_{0,n}$ .
As a result, $f(x,y)=c(x^m-x^n)$ . This means $g$ is constant, contradiction arises!
Therefore $x^m-y^n$ is irreducible.

Z K Y

The post below has been deleted. Click to close.

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

2903 posts

#3 h Aug 3, 2012, 4:13 AM • 4 Y

Y by gvole, Adventure10, MS_asdfgzxcvb, and 1 other user

Suppose for the sake of contradiction we have $x^m - y^n = f(x,y) \cdot g(x,y)$ for $f,g \in \mathbb{C}[x,y]$ as non-units, i.e. non-constant polynomials. Then for each $z$ , $(z^n)^m - (z^m)^n = 0 \implies f(z^n, z^m) = 0$ or $g(z^n, z^m) = 0$ . At least one of these conditions must happen infinitely often, WLOG $f(z^n, z^m) = 0$ for infinitely many $z \in \mathbb{C}$ . But this means $f(z^n, z^m)$ when interpreted as a polynomial in $\mathbb{C}[z]$ is the zero polynomial, thus $f(z^n, z^m) = 0 \forall z \in \mathbb{C}$ .

Let $\zeta = e^{2 \pi i / m}$ . We know $f(\zeta^k, 1) = 0$ for all $1 \le k \le m$ by using modular inverses and that $(m,n) = 1$ , thus the degree of $x$ in $f(x,1)$ is at least $m \implies \deg_x(f(x,y)) \ge m$ . By similar argument, $\deg_y(f(x,y)) \ge n$ . But then $\deg_x(g(x,y)) = \deg_y(g(x,y)) = 0 \implies g$ is constant, contradiction and hence we are done.

Z K Y

The post below has been deleted. Click to close.

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

6874 posts

#4 h Nov 29, 2014, 3:15 PM • 2 Y

Y by Adventure10, Mango247

If I'm not mistaken, you can port over the solution from this ELMO SL problem...

Take a decomposition $x^m-y^n = g(x,y) h(x,y)$ . Viewing this as polynomial identity in $x$ , assume both $g$ and $h$ are monic in $x$ ; the left-hand side factors as $\prod_{k=0}^{m-1} \left( x - y^{\frac nm} \zeta^k \right)$
where $\zeta$ is an $m$ th root of unity. Now consider $g(0,y)$ and $h(0,y)$ ; the constant terms of each is the product of a subset of these roots. But such a product cannot be a polynomial in $y$ except in the case that one of them is constant and the other is $-y^n$ .

Z K Y

The post below has been deleted. Click to close.

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

4302 posts

#5 h Nov 29, 2014, 6:51 PM • 3 Y

Y by Tawan, Adventure10, Mango247

v_Enhance wrote:

the left-hand side factors as $\prod_{k=0}^{m-1} \left( x - y^{\frac nm} \zeta^k \right)$
where $\zeta$ is an $m$ th root of unity.

This needs more justification (so does the argument in the linked problem, but I never got around to replying). There may or may not be a purely formal/algebraic way to do this, but the easiest argument I know is to note this factorization for each fixed positive real $y_0$ , and then observe by pigeonhole that one of the $2^m$ possible factorizations of $g(x,y_0)$ occurs infinitely often, whence $g(0,y_0)^{2m} = y_0^{2\ell n}$ infinitely often (for some fixed $0 < \ell < m$ ), so $g(0,y)^{2m} = y^{2\ell n}$ identically, which is absurd.

[This method is more robust than it seems: see http://en.wikipedia.org/wiki/Branch_point]

EDIT: Actually if we do $x^n - (z^n)^m = g(x,z^n) h(x,z^n)$ (formally) then the formal argument should be OK.

Z K Y

The post below has been deleted. Click to close.

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

1963 posts

ABCDE

#6 h Jun 3, 2016, 4:05 AM • 2 Y

Y by Adventure10, Mango247

Suppose that $x^m-y^n=f(x,y)g(x,y)$ for nonconstant $f,g\in\mathbb{C}[X,Y]$ with $f(x,y)=P_k(y)x^k+x^{k-1}P_{k-1}(y)+x^{k-2}P_{k-2}(y)+\ldots+P_0(y)$ for $P_0,P_1,\ldots,P_k\in\mathbb{C}[X]$ .

Let $a$ be a positive real number, and note that the roots of $f(x,a)$ as a polynomial in $x$ must be a subset of the roots of $x^m-a^n$ , which are the $m$ -th roots of unity scaled by a factor of $a^{\frac{n}{m}}$ . Hence, the roots of $f(x,a)$ consist of some $k$ -element-subset of the $m$ -th roots of unity scaled up by $a^{\frac{n}{m}}$ . Call this subset the $a$ -set. Among all of the $k$ -element-subsets of the $m$ -th roots of unity, there exists one of them that is the $u$ -set for infinitely many positive real numbers $u$ . If $P(x)=x^k+c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+\ldots+c_0$ is the polynomial with those $k$ $m$ -th roots of unity as its roots, then for infinitely many $u$ we must have that $P_i(u)=c_iu^{\frac{(k-i)n}{m}}$ for all $0\leq i<k$ . But since $m$ and $n$ are relatively prime, $\frac{(k-i)n}{m}$ cannot be an integer, so this forces $c_i=0$ for all $0\leq i<k$ . This in turn implies that $P_i=c_i=0$ for all $0\leq i<k$ , so $x^k\mid f(x,y)\mid x^m-y^n$ for some $k>0$ , a contradiction. Hence, $x^m-y^n$ is irreducible over the complex numbers.

Z K Y

The post below has been deleted. Click to close.

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

2079 posts

pi37

#7 h Jun 3, 2016, 4:45 AM • 2 Y

Y by toto1234567890, Adventure10

Suppose $x^m-y^n = f(x,y)g(x,y)$ . Then $x^{m}-y^{mn} = f(x,y^m)g(x,y^m)$ . But
$x^m-y^{mn} = \prod_{\omega^m=1} (x -\omega y^n)$ and notice that each of the factors are irreducible in $\mathbb{C}[x,y]$ . Thus $f$ must be a product of some number of these factors, but it's easy to see that largest power of $y$ in the product of $r$ of these terms is $nr$ . But $f$ is a polynomial in $y^m$ , so we must have $m\mid nr$ , implying $r=0$ or $r=m$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

5589 posts

#8 h Aug 8, 2023, 12:24 PM

Y by

Solved with GoodMorning.

Suppose this was not the case for some positive integers $m,n$ . Let $x^m - y^n = f(x,y)g(x,y)$ For any complex number $z$ , we have $f(z^n, z^m) g(z^n , z^m) = 0$ WLOG that $f(z^n, z^m)= 0$ for infinitely many $z$ . Since $f(z^n, z^m)$ is a polynomial in $z$ , we have $f(z^n , z^m) = 0\forall z\in \mathbb{C}$ Now, we fix $y\ne 0$ and view the equation as a polynomial in $x$ . Notice that there are $m$ distinct complex numbers $z$ satisfying $z^m = y$ .

Claim: If $z_1, z_2$ are two nonzero complex numbers, then $(z_1)^m = (z_2)^m$ and $(z_1)^n = (z_2)^n$ implies $z_1 = z_2$ .
Proof: By Bezout, we can choose positive integers $a,b$ such that $am - bn = 1$ . Then $(z_1)^{am} = (z_2)^{am}$ and $(z_1)^{am - 1} = (z_2)^{am - 1}$ . Dividing both sides by $(z_1)^{am - 1}$ in the first equation gives $z_1 = z_2$ . $\square$

For each $z$ with $z^m = y$ , we have $f(z^n, y) = 0$ . Since $y$ is fixed and $z^n$ has $m$ distinct values, $f(x,y)$ has at least $m$ distinct roots viewed as a polynomial in $x$ . This implies that $\deg_x (f(x,y)) \ge m$ . Now viewing $g(x,y)$ as a polynomial in $x$ , we see it must be constant, so it doesn't have any terms involving $x$ . Then we have $f(0,y)g(0,y) = -y^n$ , so $f(0,y)$ and $g(0,y) = g(x,y)$ must both be monomials. However, if $g(x,y)$ was a nonconstant monomial, then all terms of $f(x,y)g(x,y)$ must have a $y$ in them, so it cannot be equal to $x^m - y^n$ . Therefore $g(x,y)$ is constant, so $x^m- y^n$ is irreducible.

Z K Y

The post below has been deleted. Click to close.

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

1518 posts

#9 h Sep 3, 2023, 5:53 AM

Y by

FTSOC suppose that for some monic $f, g \in {\mathbb C}[x,y]$ that $x^m - y^n = f(x, y) \cdot g(x, y)$ Let $x = z^n$ so that this becomes $f(z^n, y) \cdot g(z^n, y) = z^{mn} - y^n = \prod_{i=1}^{mn} (z - \zeta^i \sqrt[m]{y})$ where $\zeta$ is the $mn$ th primitive root of unity.
This implies that for some index set $S$ with $|S| = kn$ , that $f(z^n, y) = \prod_{i \in S} (z - \zeta^i \sqrt[m]{y})$ which is impossible by considering when $y = 0$ unless $f$ is either trivial or $x^m - y^n$ .

Z K Y

The post below has been deleted. Click to close.

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

8857 posts

#10 h Oct 13, 2023, 3:30 PM

Y by

Let $P(x, y)$ be the given polynomial. Notice that $P(a^n, b^m) = \prod_{\omega^{mn} = 1} (a-b\omega^k).$ For the product of some number of these terms to only contain $a^n$ and $b^m$ terms, the number $k$ of terms must satisfy $n \mid k$ and $m \mid k$ , hence $k \geq mn$ . It follows $P$ is irreducible.

Z K Y

The post below has been deleted. Click to close.

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

136 posts

#11 h Jul 27, 2024, 2:15 PM

Y by

Let $y=z^n.$ Then we have that
$x^m-z^{mn}=\prod_{\omega^m=1}(x-\omega z^n).$ Therefore a factor will have $r$ of these linear irreducibles. However, plugging in $(x,y)=(0,z^m),$ we get that it equals some constant times $z^{rn},$ so $z^m|z^{rn}$ so $r$ must be $0$ or $n,$ as desired $.\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1891 posts

#12 h Feb 9, 2025, 2:19 AM

Y by

Suppose otherwise, then $x^m-y^n=f(x,y)g(x,y)$ where $f(x,y)=\bullet x^a+\bullet y^b+\dots$ and $g(x,y)=\bullet x^c+\bullet y^d+\dots$ , with $a+c=m$ and $b+d=n$ . Assume WLOG $q_1=\frac ba<\frac dc=q_2$ (they can't be equal because $\gcd(m,n)=1$ ). Then choose a real number $\alpha$ between them.

Let the monomial $x^s y^t$ have a " $\lambda$ -score" of $\lambda s+t$ . Then call a monomial $(p,\lambda)$ -(exact, satisfied, oversatisfied) if its $\lambda$ -score is (exactly, at least, more than) $p$ , respectively.

Now let a polynomial be $(p,\lambda)$ -(exact, satisfied, oversatisfied) if the maximum $\lambda$ -score over all of its monomials is (exactly, at least, more than) $p$ , respectively.

Note that if a monomial is $(p_1,\lambda)$ -exact, then a second monomial is $(p_2,\lambda)$ -satisfied if and only if their product is $(p_1+p_2,\lambda)$ -satisfied.

Claim. If polynomials $f_1$ and $f_2$ are $(p_1,\lambda)$ -exact and $(p_2,\lambda)$ -exact, respectively, then $f_1f_2$ is $(p_1+p_2,\lambda)$ -exact.
Proof. Obviously it won't be oversatisfied so we just have to prove the $(\bullet,\lambda)$ -exact monomials don't cancel out somehow. But that's obvious just by taking the monomials of both with the largest exponent of $x$ .

Corollary. If polynomials $f_1$ and $f_2$ are $(p_1,\lambda)$ -satisfied and $(p_2,\lambda)$ -satisfied, respectively, then $f_1f_2$ is $(p_1+p_2,\lambda)$ -satisfied.

Now note that $f(x,y)$ is $(a\alpha,\alpha)$ -satisfied and $g(x,y)$ is $(d,\alpha)$ -satisfied, so their product is $(a\alpha+d,\alpha)$ -satisfied. But the $\alpha$ -score of $x^m$ is $m\alpha=a\alpha+c\alpha<a\alpha+d$ , and the $\alpha$ -score of $-y^n$ is $n=b+d<a\alpha+d$ , so $x^m-y^n$ is not $(a\alpha+d,\alpha)$ -satisfied. $\blacksquare$

Remark. This solution was motivated by comparative advantage from Economics. Both polynomials will accept the "trade rate" of $\alpha$ , so this trade will benefit both of them and therefore do better than if they both only produce $x$ or both only produce $y$ .

This post has been edited 3 times. Last edited by cj13609517288, Feb 9, 2025, 3:41 AM

Z K Y

The post below has been deleted. Click to close.

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

1500 posts

#13 h Feb 9, 2025, 3:44 AM

Y by

Suppose FTSOC such $f,g \in \mathbb C[x,y]$ existed, then notice:
$x^m-z^{mn}=\prod_{\omega^m=1} (x-\omega z^n)$ Clearly each of the monomials is irreducible in $\mathbb C[x,z]$ and so $f$ is the product of some of them but the higher degree of $y$ with $k$ terms picked is $nk$ meaning that $m \mid nk$ therefore $k=0$ or $k=m$ , either way leads to a contradiction, thus we are done :cool:

:cool:

.

This post has been edited 1 time. Last edited by MathLuis, Feb 9, 2025, 3:45 AM

Z K Y

The post below has been deleted. Click to close.

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

9 posts

#14 h Apr 14, 2025, 2:32 AM

Y by

What is FTSOC

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a