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.
Problem
Source: ELMO Shortlist 2012, A5
Tags: algebra, polynomial, pigeonhole principle, number theory, relatively prime, algebra proposed
02.07.2012 14:12
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.
03.08.2012 07:13
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.
29.11.2014 17:15
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$.
29.11.2014 20:51
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.
03.06.2016 07:05
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.
03.06.2016 07:45
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.
08.08.2023 15:24
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.
03.09.2023 08:53
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$.
13.10.2023 18:30
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.
27.07.2024 17:15
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$