Let $n$ be a given positive integer. We say that a positive integer $m$ is $n$-good if and only if there are at most $2n$ distinct primes $p$ satisfying $p^2\mid m$. (a) Show that if two positive integers $a,b$ are coprime, then there exist positive integers $x,y$ so that $ax^n+by^n$ is $n$-good. (b) Show that for any $k$ positive integers $a_1,\ldots,a_k$ satisfying $\gcd(a_1,\ldots,a_k)=1$, there exist positive integers $x_1,\ldots,x_k$ so that $a_1x_1^n+a_2x_2^n+\cdots+a_kx_k^n$ is $n$-good. (Remark: $a_1,\ldots,a_k$ are not necessarily pairwise distinct) Proposed by usjl.
Problem
Source: 2021 Taiwan TST Round 3 Independent Study 2-N
Tags: number theory, Taiwan
01.05.2021 09:26
OH MY GOD BEAUTIFUL ANALYTICAL (oops) NUMBER THEORY WOO HOO. Pardon any errors I make, I'm tired after school and my brain probably has 3 brain cells left, all trying to figure out what a prime really is. Let $\mathcal P$ be the set of primes. Let the congruence, for some $S\subseteq\mathbb Z\setminus\{1\}$ \[x\equiv a\pmod S\]as the simultaneous congruences \[x\equiv a\pmod s\qquad\text{for all }s\in S\] We will first show that part b follows from part a, as that is the easier part. First, we show the following claim: Claim. Given positive integers $a,b,c,n$ with $\gcd(a,b,c)=1$, there exist positive integers $x,y$ such that $\gcd(ax^n+by^n,c)=1$. Proof. Let $d_1=\gcd(a,c)$ and $d_2=\gcd(b,c)$. Note that $\gcd(d_1,d_2)=\gcd(a,b,c)=1$, and we shall carefully construct the following sets: $\mathcal P_1$ consisting of the set of primes dividing $d_1$. $\mathcal P_2$ consisting of the set of primes dividing $d_2$. $\mathcal P_3$ consisting of the set of primes dividing $c$ but not $d_1,d_2$. Note that $\mathcal P_i\cap\mathcal P_j=\emptyset$ for $1\leq i<j\leq 3$, so by the Chinese Remainder Theorem, we can write down \[x\equiv 1\pmod{\mathcal P_2}\qquad x\equiv 1\pmod{\mathcal P_3}\]\[y\equiv 1\pmod{\mathcal P_1}\qquad y\equiv 0\pmod{\mathcal P_3}\]If a prime divides $c$, if $p\in\mathcal P_1$, then $ax^n+by^n\equiv 0+b\equiv b\not\equiv 0\pmod p$. If $p\in\mathcal P_2$, then $ax^n+by^n\equiv a+0\equiv a\not\equiv 0\pmod p$. If $p\in\mathcal P_3$, then $ax^n+by^n\equiv a+0\equiv a\not\equiv 0\pmod p$. Thus $\gcd(ax^n+by^n,c)=1$ for the chosen $(x,y)$. $\blacksquare$ Now, we can plainly induct on $k$ to win: Base Case. $k=2$. In this case, this is just part a. Induction Hypothesis. Assume the result holds for some $k$. We show it for $k+1$. Induction Step. By the claim, we get that we can "collapse" $a_k,a_{k+1}$ into some number $b=a_kx^n+a_{k+1}y^n$ such that $\gcd(a_1,\ldots,a_{k-1},b)=1$ and find a solution $(y_1,\ldots,y_k)$. Now, the solution to the original congruence as \[(x_1,\ldots,x_{k+1})=(y_1,\ldots,y_{k-1},xy_k,yy_k)\]as needed. $\blacksquare$ Now, we shall die on part a. Note there are strictly less than $2n$ primes less than or equal to $2n$. Now, consider primes that are greater, and we shall show there exist a positive density of numbers $x$ such that \[a+bx^n\]is squarefree, outside of the above primes.
We shall try again, this time actually using our brains. Let $\mathcal P_a$ be the set of primes dividing $a$, and consider the set \[S=\left\{1+k\prod_{p\in\mathcal P_a}p\mid k\in\mathbb Z\right\}\]Note that $a+bx^n$ is not divisible by any prime dividing $a$. Now, if we ignore all primes at most $2n$ (there are at most $2n$ such numbers), we get \[p\mid a+bx^n\]has at most $n$ solutions by Lagrange's Theorem, so by Hensel's Lemma, as $\gcd(n,p)=1$, we have there are at most $n$ solutions modulo $p^2$. Thus, for large $N$, we have at most \[\sum_{p\in\mathcal P\setminus\mathcal P_a\cup[2n]}\left\lceil\frac N{p^2}\right\rceil\leq\sum_{p\in\mathcal P}\frac N{p^2}+\pi(N)\]Thus, we can get as $N$ tends to infinity, the quantity must be at least $\frac N2$, so there exists a number $x$ such that \[p^2\mid a+bx^n\]implies $p\leq 2n$ as desired. If any part of this is wrong, I apologize in advance. Bye.
01.05.2021 09:48
It seems that density arguments based on squarefree never lose their charm.For instance China tst 2015 ,Imc 2013 ,Iranian OurMO 2020, China southeast 2020
01.05.2021 11:21
naman12 wrote: OH MY GOD BEAUTIFUL ANALYTICAL (oops) NUMBER THEORY WOO HOO. Pardon any errors I make, I'm tired after school and my brain probably has 3 brain cells left, all trying to figure out what a prime really is. Let $\mathcal P$ be the set of primes. Let the congruence, for some $S\subseteq\mathbb Z\setminus\{1\}$ \[x\equiv a\pmod S\]as the simultaneous congruences \[x\equiv a\pmod s\qquad\text{for all }s\in S\] We will first show that part b follows from part a, as that is the easier part. First, we show the following claim: Claim. Given positive integers $a,b,c,n$ with $\gcd(a,b,c)=1$, there exist positive integers $x,y$ such that $\gcd(ax^n+by^n,c)=1$. Proof. Let $d_1=\gcd(a,c)$ and $d_2=\gcd(b,c)$. Note that $\gcd(d_1,d_2)=\gcd(a,b,c)=1$, and we shall carefully construct the following sets: $\mathcal P_1$ consisting of the set of primes dividing $d_1$. $\mathcal P_2$ consisting of the set of primes dividing $d_2$. $\mathcal P_3$ consisting of the set of primes dividing $c$ but not $d_1,d_2$. Note that $\mathcal P_i\cap\mathcal P_j=\emptyset$ for $1\leq i<j\leq 3$, so by the Chinese Remainder Theorem, we can write down \[x\equiv 1\pmod{\mathcal P_2}\qquad x\equiv 1\pmod{\mathcal P_3}\]\[y\equiv 1\pmod{\mathcal P_1}\qquad y\equiv 0\pmod{\mathcal P_3}\]If a prime divides $c$, if $p\in\mathcal P_1$, then $ax^n+by^n\equiv 0+b\equiv b\not\equiv 0\pmod p$. If $p\in\mathcal P_2$, then $ax^n+by^n\equiv a+0\equiv a\not\equiv 0\pmod p$. If $p\in\mathcal P_3$, then $ax^n+by^n\equiv a+0\equiv a\not\equiv 0\pmod p$. Thus $\gcd(ax^n+by^n,c)=1$ for the chosen $(x,y)$. $\blacksquare$ Now, we can plainly induct on $k$ to win: Base Case. $k=2$. In this case, this is just part a. Induction Hypothesis. Assume the result holds for some $k$. We show it for $k+1$. Induction Step. By the claim, we get that we can "collapse" $a_k,a_{k+1}$ into some number $b=a_kx^n+a_{k+1}y^n$ such that $\gcd(a_1,\ldots,a_{k-1},b)=1$ and find a solution $(y_1,\ldots,y_k)$. Now, the solution to the original congruence as \[(x_1,\ldots,x_{k+1})=(y_1,\ldots,y_{k-1},xy_k,yy_k)\]as needed. $\blacksquare$ Now, we shall die on part a. Note there are strictly less than $2n$ primes less than or equal to $2n$. Now, consider primes that are greater, and we shall show there exist a positive density of numbers $x$ such that \[a+bx^n\]is squarefree, outside of the above primes. Consider a prime $p>2n$. If $p\mid a$, the values $x$ such that $p^2\mid a+bx^n$ are $pk$ if $p^2$ divides $a$, and none otherwise. In any other case, we have \[p\mid a+bx^n\]has at most $n$ solutions by Lagrange's Theorem, so by Hensel's Lemma, as $\gcd(n,p)=1$, we have there are at most $n$ solutions modulo $p^2$. Thus, by the Chinese Remainder Theorem, for some large integer $m$, we must have for \[N=\prod_{p\in\mathcal P\cap[m]}p^2\]by the Chinese Remainder Theorem, we have that the number of integers $x\leq kN$ such that $a+bx^n$ is \textbf{not} divisible by any of $p^2$ for $2n<p\leq m$ is at least \[(k-1)N\cdot\left[\prod_{p\in\mathcal P\cap[m]~\text{and}~p\nmid a}\left(1-\frac 1{p^2}\right)\right]\cdot\left[\prod_{p\mid a}\left(1-\frac 1p\right)\right]\]Taking the limit as $m,k\to\infty$, we get that if $\chi(N)$ is the number of integers $x\leq N$ such that $a+bx^n$ is not divisible by $p^2$ for $2n<p$ \begin{align*} \frac{\chi(N)}N&\geq\lim_{m\to\infty}\frac 12\left[\prod_{p\in\mathcal P\cap[m]~\text{and}~p\nmid a}\left(1-\frac 1{p^2}\right)\right]\cdot\left[\prod_{p\mid a}\left(1-\frac 1p\right)\right]\\ &\geq\frac 12\cdot\frac{6}{\pi^2}\cdot \left[\prod_{p\mid a}\left(1-\frac 1p\right)\right]\\ &>0 \end{align*}implying that such $x$ exists. If any part of this is wrong, I apologize in advance. Bye. The idea looks similar to mine, but I'm not quite sure if the detail in the computation of the density is alright. Why does the inequality following CRT holds?
01.05.2021 12:08
naman12 wrote: OH MY GOD BEAUTIFUL ANALYTICAL (oops) NUMBER THEORY WOO HOO. Pardon any errors I make, I'm tired after school and my brain probably has 3 brain cells left, all trying to figure out what a prime really is. Let $\mathcal P$ be the set of primes. Let the congruence, for some $S\subseteq\mathbb Z\setminus\{1\}$ \[x\equiv a\pmod S\]as the simultaneous congruences \[x\equiv a\pmod s\qquad\text{for all }s\in S\] We will first show that part b follows from part a, as that is the easier part. First, we show the following claim: Claim. Given positive integers $a,b,c,n$ with $\gcd(a,b,c)=1$, there exist positive integers $x,y$ such that $\gcd(ax^n+by^n,c)=1$. Proof. Let $d_1=\gcd(a,c)$ and $d_2=\gcd(b,c)$. Note that $\gcd(d_1,d_2)=\gcd(a,b,c)=1$, and we shall carefully construct the following sets: $\mathcal P_1$ consisting of the set of primes dividing $d_1$. $\mathcal P_2$ consisting of the set of primes dividing $d_2$. $\mathcal P_3$ consisting of the set of primes dividing $c$ but not $d_1,d_2$. Note that $\mathcal P_i\cap\mathcal P_j=\emptyset$ for $1\leq i<j\leq 3$, so by the Chinese Remainder Theorem, we can write down \[x\equiv 1\pmod{\mathcal P_2}\qquad x\equiv 1\pmod{\mathcal P_3}\]\[y\equiv 1\pmod{\mathcal P_1}\qquad y\equiv 0\pmod{\mathcal P_3}\]If a prime divides $c$, if $p\in\mathcal P_1$, then $ax^n+by^n\equiv 0+b\equiv b\not\equiv 0\pmod p$. If $p\in\mathcal P_2$, then $ax^n+by^n\equiv a+0\equiv a\not\equiv 0\pmod p$. If $p\in\mathcal P_3$, then $ax^n+by^n\equiv a+0\equiv a\not\equiv 0\pmod p$. Thus $\gcd(ax^n+by^n,c)=1$ for the chosen $(x,y)$. $\blacksquare$ Now, we can plainly induct on $k$ to win: Base Case. $k=2$. In this case, this is just part a. Induction Hypothesis. Assume the result holds for some $k$. We show it for $k+1$. Induction Step. By the claim, we get that we can "collapse" $a_k,a_{k+1}$ into some number $b=a_kx^n+a_{k+1}y^n$ such that $\gcd(a_1,\ldots,a_{k-1},b)=1$ and find a solution $(y_1,\ldots,y_k)$. Now, the solution to the original congruence as \[(x_1,\ldots,x_{k+1})=(y_1,\ldots,y_{k-1},xy_k,yy_k)\]as needed. $\blacksquare$ Now, we shall die on part a. Note there are strictly less than $2n$ primes less than or equal to $2n$. Now, consider primes that are greater, and we shall show there exist a positive density of numbers $x$ such that \[a+bx^n\]is squarefree, outside of the above primes. Consider a prime $p>2n$. If $p\mid a$, the values $x$ such that $p^2\mid a+bx^n$ are $pk$ if $p^2$ divides $a$, and none otherwise. In any other case, we have \[p\mid a+bx^n\]has at most $n$ solutions by Lagrange's Theorem, so by Hensel's Lemma, as $\gcd(n,p)=1$, we have there are at most $n$ solutions modulo $p^2$. Thus, by the Chinese Remainder Theorem, for some large integer $m$, we must have for \[N=\prod_{p\in\mathcal P\cap[m]}p^2\]by the Chinese Remainder Theorem, we have that the number of integers $x\leq kN$ such that $a+bx^n$ is \textbf{not} divisible by any of $p^2$ for $2n<p\leq m$ is at least \[(k-1)N\cdot\left[\prod_{p\in\mathcal P\cap[m]~\text{and}~p\nmid a}\left(1-\frac 1{p^2}\right)\right]\cdot\left[\prod_{p\mid a}\left(1-\frac 1p\right)\right]\]Taking the limit as $m,k\to\infty$, we get that if $\chi(N)$ is the number of integers $x\leq N$ such that $a+bx^n$ is not divisible by $p^2$ for $2n<p$ \begin{align*} \frac{\chi(N)}N&\geq\lim_{m\to\infty}\frac 12\left[\prod_{p\in\mathcal P\cap[m]~\text{and}~p\nmid a}\left(1-\frac 1{p^2}\right)\right]\cdot\left[\prod_{p\mid a}\left(1-\frac 1p\right)\right]\\ &\geq\frac 12\cdot\frac{6}{\pi^2}\cdot \left[\prod_{p\mid a}\left(1-\frac 1p\right)\right]\\ &>0 \end{align*}implying that such $x$ exists. If any part of this is wrong, I apologize in advance. Bye. I don't get the part where you got the inequality after taking the limit, I think it is much more simple by using similar idea but finding a large x where there is no prime p smaller than x such that p^2 divides a+b*(x^n), and for such x of course there is no more than 2n primes p bigger than x such that p^2 divides a+b*(x^n). If there is any grammar mistake, sorry for my poor English.
01.05.2021 18:29
I do agree it seems wrong, because it proves an unsolved problem ($x^4+2$ is square free infinitely often). I will think about this a bit more today and hopefully not be braindead.
01.05.2021 18:46
huh thats a lot of math
01.05.2021 20:13
Just a brief sketch I am giving so it might be wrong. First ignore the primes less than $n$ as there are almost $O(\frac{n}{\log{n}})$ of them then one can show using density arguments like naman12 that for $x\leq N$ the density of $x$ such that $v_{p}(a+bx^{n})<2$ for all $n<p<\sqrt{N}$ is positive. In order to prove it first note that there exists a large enough constant $r$ such that $\sum_{p>r}\frac{1}{p^{2}}\rightarrow 0$. So we will calculate the proportion $d$ of integers $x<N$ such that $p^{2}|a+bx^{n}$ for some $n<p<\sqrt{N}$. So $$d\leq 1-\prod_{n<p<r,p\nmid a}c\cdot (1-\frac{n}{p^{2}})+\sum_{p>r}\frac{n}{p^{2}}$$However we also know that $$\prod_{n<p<r,p\nmid a}(1-\frac{n}{p^{2}})<\epsilon$$for some constant $0<\epsilon<1$ irrespective of $r$ which follows by taking the log of the expression and also $c<1$ which arises in the expression due to the primes dividing $a$. So if we choose a large enough $r$ then we can see that $0<d<1$ which implies what we wished to prove. Now among those $x$ one needs to look at the prime divisors of $a+bx^{n}$ which are in range$(\sqrt{x},x^{\frac{n}{2}})$ and if we assume that all such prime divisors are such that $p^{2}|a+bx^{n}$ then $a+bx^{n}$ can have at most $n$ divisors of this type and thus one can see that we are done. I will give a detailed sketch later
01.05.2021 22:19
Quite hard to get a foothold, but it's not hard to see this is asymptotic density and after that a correct setup is not so obscure either. Part a): We only consider primes not dividing $abn$ and consider $x,y$ such that any primes dividing $abn$ doesn't divide them. Inspired by $\sum\limits_{p} p^{-2} < \frac 12$, we use a global idea of asymptotic density (construction looks quite hopeless anyways, so that's another piece of motivation) Suppose $p^2\mid ax^n+by^n$, we have two cases. Since $\gcd(abn,p)=1$, then $ax^n\equiv -by^n(\bmod\; p^2)$, so $$-\frac ba \equiv \left(\frac xy \right)^n (\bmod\; p^2)$$ Consider the equation $c^n \equiv t(\bmod\; p)$. There are at most $n$ integer solutions mod $p$ as $\mathbb{Z}_p[x]$ is a UFD (there are a lot of proofs of this). Furthermore, note $c^n, (c+p)^n, \cdots, (c+(p-1)p)^n$ are distinct mod $p$. Therefore, $\frac{n}{p^2}$ of the points $(x,y)$ with $\gcd(xy,abn)=1$ has $p^2\mid ax^n+by^n$. Assume for the sake of contradiction there are at least $2n+1$ primes on each such point $(x,y)$, then $\sum\limits_p \frac{n}{p^2} \ge 2n+1$. However, $n \sum\limits_p p^{-2} < \frac n2$, contradiction. b) It suffices to show there exist $\gcd(\sum\limits_{i=1}^{k-1} a_iw_i^n, a_k)=1$. Why? Let $C=\sum\limits_{i=1}^{k-1} a_iw_i^n$, then I can reduce this problem to $Cx^n+a_ky^n = \sum\limits_{i=1}^{k-1} a_i(xw_i)^n + a_ky^n$ being $n$-good. This is not hard; suppose $p\mid a_k$, then consider all $p\nmid a_i$. There exist at least one because $\gcd(a_1, a_2, \cdots, a_k)=1$. Set all but one such $x_i$ to be NOT divisible by $p$. The conclusion follows by the Chinese Remainder Theorem.
02.05.2021 08:55
KaiDaMagical336 wrote: Quite hard to get a foothold, but it's not hard to see this is asymptotic density and after that a correct setup is not so obscure either. Part a): We only consider primes not dividing $abn$ and consider $x,y$ such that any primes dividing $abn$ doesn't divide them. Inspired by $\sum\limits_{p} p^{-2} < \frac 12$, we use a global idea of asymptotic density (construction looks quite hopeless anyways, so that's another piece of motivation) Suppose $p^2\mid ax^n+by^n$, we have two cases. Since $\gcd(abn,p)=1$, then $ax^n\equiv -by^n(\bmod\; p^2)$, so $$-\frac ba \equiv \left(\frac xy \right)^n (\bmod\; p^2)$$ Consider the equation $c^n \equiv t(\bmod\; p)$. There are at most $n$ integer solutions mod $p$ as $\mathbb{Z}_p[x]$ is a UFD (there are a lot of proofs of this). Furthermore, note $c^n, (c+p)^n, \cdots, (c+(p-1)p)^n$ are distinct mod $p$. Therefore, $\frac{n}{p^2}$ of the points $(x,y)$ with $\gcd(xy,abn)=1$ has $p^2\mid ax^n+by^n$. Assume for the sake of contradiction there are at least $2n+1$ primes on each such point $(x,y)$, then $\sum\limits_p \frac{n}{p^2} \ge 2n+1$. However, $n \sum\limits_p p^{-2} < \frac n2$, contradiction. b) It suffices to show there exist $\gcd(\sum\limits_{i=1}^{k-1} a_iw_i^n, a_k)=1$. Why? Let $C=\sum\limits_{i=1}^{k-1} a_iw_i^n$, then I can reduce this problem to $Cx^n+a_ky^n = \sum\limits_{i=1}^{k-1} a_i(xw_i)^n + a_ky^n$ being $n$-good. This is not hard; suppose $p\mid a_k$, then consider all $p\nmid a_i$. There exist at least one because $\gcd(a_1, a_2, \cdots, a_k)=1$. Set all but one such $x_i$ to be NOT divisible by $p$. The conclusion follows by the Chinese Remainder Theorem. I'm still a bit worried about the step where you compute the density. Can you say more about how the inequality $\sum n/p^2\geq 2n+1$ is obtained?
02.05.2021 09:02
Assume the problem is false; Let $f(x,y)$ denote the number of primes $p$ st $p^2\mid ax^n+by^n$. However, in the desired set of points $(x,y)\in \mathbb{Z}^2, \gcd(x,abn)=\gcd(y,abn)=1$, we can see, as $m\to\infty$, $\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1} < \sum\limits_{p} \frac{1.01 n + 1}{p^2}$. However, $f(x,y)\ge 2n+1$ so $\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1}\ge 2n+1$
02.05.2021 09:04
KaiDaMagical336 wrote: Assume the problem is false; Let $f(x,y)$ denote the number of primes $p$ st $p^2\mid ax^n+by^n$. However, in the desired set of points $(x,y)\in \mathbb{Z}^2, \gcd(x,abn)=\gcd(y,abn)=1$, we can see, as $m\to\infty$, $\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1} < \sum\limits_{p} \frac{1.01 n}{p^2}$. However, $f(x,y)\ge 2n+1$ so $\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1}\ge 2n+1$ I guess I'm worried about the first inequality then. Can you actually show this for finite (but large enough) m?
02.05.2021 09:15
$\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1} = \frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} \sum\limits_{p^2\mid ax^n+by^n} 1 } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1}$ If $p^2\mid ax^n+by^n$, then it's clear that $p\nmid ab$. Clearly, $p\nmid ab$. Case 1: $p\mid x,y$: this gives $\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} p^{-2}$ Case 2: $p\nmid n,x,y$: let $c=\frac xy(\bmod\; p)$, then there are up to $n$ values for $c$. For each value of $x$ there are at most $n$ values for $y$. By Chinese Remainder theorem, this should be rather "uniform". This is where that $\sum\limits_p \frac{n}{p^2}$ comes from. Case 3: $p\mid n, p\nmid xy$ Each such prime can contribute at most $1$ to $f(x,y)$, and thus can contribute at most $1$ to the fraction $\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1}$. Since there are less than $\frac{3n}{2}$ such primes, we should be safe. Thank you USJL for pointing out my flaws! I'll update my first sol once you think it's fully correct.
02.05.2021 13:42
KaiDaMagical336 wrote: $\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1} = \frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} \sum\limits_{p^2\mid ax^n+by^n} 1 } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1}$ If $p^2\mid ax^n+by^n$, then it's clear that $p\nmid ab$. Clearly, $p\nmid ab$. Case 1: $p\mid x,y$: this gives $\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} p^{-2}$ Case 2: $p\nmid n,x,y$: let $c=\frac xy(\bmod\; p)$, then there are up to $n$ values for $c$. For each value of $x$ there are at most $n$ values for $y$. By Chinese Remainder theorem, this should be rather "uniform". This is where that $\sum\limits_p \frac{n}{p^2}$ comes from. Case 3: $p\mid n, p\nmid xy$ Each such prime can contribute at most $1$ to $f(x,y)$, and thus can contribute at most $1$ to the fraction $\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} 1}$. Since there are less than $\frac{3n}{2}$ such primes, we should be safe. Thank you USJL for pointing out my flaws! I'll update my first sol once you think it's fully correct. I still don't think this is rigorous or correct. I think to convince me, you would have to restrict to a finite set of primes and numbers $x, y$ and show the uniformity/independency rigorously. I'm worried that when $p$ is large compared to $ax^n+by^n$, the uniformity argument/CRT argument would break down.
03.05.2021 06:21
Posting my solution here, but I think this might be similar to what Superguy does. We first prove (a). Let $N,C_1,C_2$ be some positive integers to be determined. Let $P$ be the product of all primes at most $\max(a,b,2n+4)$. Let $S_1=\{Pn+C_1|n\in[N]\}$ and $S_2=\{Pn+C_2|n\in[N]\}$. For each prime $\max(a,b,2n+4)<p<\sqrt{N}$, we first count the number of $(x,y)\in S_1\times S_2$ that satisfies $p^2\mid ax^n+by^n$. For each $y\in S_2$, if $p\mid y$, then we also need $p\mid x$, showing that there are at most $(N/p+1)$ values for $x$ in $S_1$ such that $p^2\mid ax^n+by^n$ (here we use the fact that $\gcd(p,P)=1$). If $p\nmid y$, then we know that there are at most $n$ roots for $ax^n+by^n\equiv 0\mod p$. Since $p\nmid n$, each solution modulo $p$ lifts uniquely to a solution modulo $p^2$, showing that there are at most $n(N/p^2+1)$ values for $x$ in $S_1$ such that $p^2\mid ax^n+by^n$ (here we use the fact that $\gcd(p,P)=1$ once again). Therefore, in total, there are at most \[\left(\frac{N}{p}+1\right)^2+\left(N-\frac{N}{p}-1\right)\times n\left(\frac{N}{p^2}+1\right)<\frac{2n+4}{p^2}N^2\]pairs of $(x,y)\in S_1\times S_2$ that satisfy $p^2\mid ax^n+by^n$. Since we know that \[\sum_{i=2n+5}^{\infty}\frac{1}{i(i-1)}=\sum_{i=2n+5}^{\infty}\left(\frac{1}{i-1}-\frac{1}{i}\right)=\frac{1}{2n+4},\]we have that \[\sum_{\text{prime }p\in [2n+5,\sqrt{N})}\frac{2n+4}{p^2}<\sum_{i=2n+5}^{\infty}\frac{2n+4}{i(i-1)}=1.\]As a consequence, we know that for every $C_1,C_2,N$, there exists a pair $(x,y)\in S_1\times S_2$ such that for any prime $\max(a,b,2n+4)<p<\sqrt{N}$ we have $p^2\nmid ax^n+by^n$. Next, we will choose $C_1,C_2$ properly to deal with the case $p\leq \max(a,b,2n+4)$. For each prime $p\leq \max(a,b,2n+4)$, if $p\nmid a$ then we can choose $C_1\equiv 1\mod p, C_2\equiv 0\mod p$; otherwise, we know by the condition that $p\nmid b$, and so we can choose $C_1\equiv 0\mod p, C_2\equiv 1\mod p$. By the Chinese Remainder Theorem, we know that we can choose $1\leq C_1,C_2\leq P$ such that the above conditions hold for all prime $p\leq \max(a,b,2n+4)$. As a consequence, we now also have that for any prime $p\leq \max(a,b,2n+4)$ and any $(x,y)\in S_1\times S_2$, we have $p\nmid ax^n+by^n$. With this choice of $C_1,C_2$, we know that for all $N$, we can choose $(x,y)\in S_1\times S_2$ such that $p^2\nmid ax^n+by^n$ for all $p<\sqrt{N}$. Note that $ax^n+by^n\leq 2\max(a,b)P^n(N+1)^n<2^{n+1}\max(a,b)P^nN^n$, and also that if $p$ is a prime such that $p^2|ax^n+by^n$ then $p\geq \sqrt{N}$. We thus have the number of distinct primes $p$ satisfying $p^2\mid ax^n+by^n$ is at most $$\log_{\sqrt{N}}2^{n+1}\max(a,b)P^nN^n=2n+\log_{\sqrt{N}}2^{n+1}\max(a,b)P^n,$$which is less than $2n+1$ if $N$ is large enough. Thus, we know that there exists $x,y$ such that there are at most $2n$ distinct primes $p$ that satisfy $p^2\mid ax^n+by^n$. Now we use (a) to prove (b). For each prime factor $p$ of $a_k$, we know that there exists $i(p)\in[k-1]$ so that $p\nmid a_{i(p)}$. We can thus set $x_j\equiv \delta_{i(p),j)}\mod p$ so that $p\nmid a_1x_1^n+\cdots+a_{k-1}x_{k-1}^n$. By the Chinese Remainder Theorem, we know there exist positive integers $x_1,\ldots,x_{k-1}$ such that $x_j\equiv \delta_{i(p),j}\mod p$ for all $j\in[k-1]$ and prime factors $p$ of $a_k$. Thus, we have that $a_1x_1^n+\cdots+a_{k-1}x_{k-1}^n$ and $a_k$ are coprime. We can thus choose $x,y\in\mathbb{N}$ by (a) so that $(a_1x_1^n+\cdots+a_{k-1}x_{k-1}^n)x^n+a_ky^n$ is $n$-good. Therefore, $a_1(x_1x)^n+\cdots+a_{k-1}(x_{k-1}x)^n+a_ky^n$ is $n$-good, as desired.
03.05.2021 08:06
Here is the corrected version of my solution: Part a): We only consider $x,y$ such that any primes dividing $ab$ doesn't divide them. Inspired by $\sum\limits_{p} p^{-2} < \frac 12$, we use a global idea of asymptotic density (construction looks quite hopeless anyways, so that's another piece of motivation) Let $f(x,y)$ denote the number of primes $p$ st $p^2\mid ax^n+by^n$. However, in the desired set of points $(x,y)\in \mathbb{Z}^2, \gcd(x,ab)=\gcd(y,ab)=1$, we want to show, as $m\to\infty$,$$\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,ab)=1} 1} < 2n+1$$We only need to check primes not dividing $ab$. Suppose $p^2\mid ax^n+by^n$, we have two cases. Case 1: $p\mid n$: note each prime contributes $1$ to the sum so this contributes $\sum\limits_{p^2\mid n} 1$ to the final result. Case 2: $p\nmid n$. If $p\nmid x,y$ then $ax^n\equiv -by^n(\bmod\; p^2)$, so$$-\frac ba \equiv \left(\frac xy \right)^n (\bmod\; p^2)$$Consider the equation $c^n \equiv t(\bmod\; p)$. There are at most $n$ integer solutions mod $p$ as $\mathbb{Z}_p[x]$ is a UFD (there are a lot of proofs of this). Furthermore, note $c^n, (c+p)^n, \cdots, (c+(p-1)p)^n$ are distinct mod $p$. Therefore, $\frac{n}{p^2}$ of the points $(x,y)$ with $\gcd(xy,abn)=1$ has $p^2\mid ax^n+by^n$ within If $p\mid x,y$ then this gives on average $p^{-2}$ to $f(x,y)$ if I consider $(x,y)\in \mathbb{Z}_p^2$ Call a prime large if it's $>m^{0.99}$ and small otherwise. Small primes contribute less than $\sum\limits_{p} \frac{1.01n}{p^2}$ on $\mathbb{E}[f(x,y)]$, which is a comfortable bound as $m$ is very, very large (we can even imagine extending our bounds to $1\le x,y\le pab\left\lceil \frac {m}{abp} \right\rceil$). For large primes, I claim $\frac 12 \cdot \frac{1}{0.99} \log_m ( \prod\limits_{1\le x,y\le m, \gcd(xy,ab)=1} (ax^n+by^n) ) \le n \sum\limits_{1\le x,y\le m, \gcd(xy,ab)=1} 1 $ would suffice, as on average, each $ax^n+by^n$ would have at most $n$ large primes. LHS $\le 0.51 \left(\sum\limits_{1\le x,y\le m, \gcd(xy,ab)=1} 1\right) \log_m((a+b)m^n) \le 0.51 (\sum\limits_{1\le x,y\le m, \gcd(xy,ab)=1} 1) (n+\log_m(a+b))$ so it suffices to have $m>a+b$. Summing gives$$\frac{\sum\limits_{1\le x,y\le m, \gcd(xy,abn)=1} f(x,y) } {\sum\limits_{1\le x,y\le m, \gcd(xy,ab)=1} 1} < \frac{n+1}{2} + n + \sum\limits_{p^2\mid n} 1 < 2n+1$$as desired.
12.07.2021 17:36
USJL wrote: We thus have the number of distinct primes $p$ satisfying $p^2\mid ax^n+by^n$ is at most $$\log_{\sqrt{N}}2^{n+1}\max(a,b)P^nN^n=2n+\log_{\sqrt{N}}2^{n+1}\max(a,b)P^n,$$ You can write detail this statement? Why number of prime numbers $\sqrt{N}<p<2^{n+1}\max(a,b)P^nN^n$? I tried to using the bounded of $\pi(x)$, but I didn't find it.
14.07.2021 10:33
analysis90 wrote: USJL wrote: We thus have the number of distinct primes $p$ satisfying $p^2\mid ax^n+by^n$ is at most $$\log_{\sqrt{N}}2^{n+1}\max(a,b)P^nN^n=2n+\log_{\sqrt{N}}2^{n+1}\max(a,b)P^n,$$ You can write detail this statement? Why number of prime numbers $\sqrt{N}<p<2^{n+1}\max(a,b)P^nN^n$? I tried to using the bounded of $\pi(x)$, but I didn't find it. This is simply because that we've already made sure that all $p$ satisfying $p^2\mid ax^n+by^n$ has to be at least $\sqrt{N}$, and the product of such primes is still at most $ax^n+by^n$.
17.07.2021 18:05
USJL wrote: analysis90 wrote: USJL wrote: We thus have the number of distinct primes $p$ satisfying $p^2\mid ax^n+by^n$ is at most $$\log_{\sqrt{N}}2^{n+1}\max(a,b)P^nN^n=2n+\log_{\sqrt{N}}2^{n+1}\max(a,b)P^n,$$ You can write detail this statement? Why number of prime numbers $\sqrt{N}<p<2^{n+1}\max(a,b)P^nN^n$? I tried to using the bounded of $\pi(x)$, but I didn't find it. This is simply because that we've already made sure that all $p$ satisfying $p^2\mid ax^n+by^n$ has to be at least $\sqrt{N}$, and the product of such primes is still at most $ax^n+by^n$. I understanded, thank you.
23.08.2023 09:23
Concerning solution found with anonymous. Note that $n = 1$ follows immediately. Claim: Fix a prime $p > n$. The density of solutions to \[ a_1x_1^n+a_2x_2^n+\cdots+a_kx_k^n \equiv 0 \pmod{p^2} \]for $x_i \in \{1, 2, \dots, N\}$ is at most $\frac{n}{p(p-1)} + \frac{kn}{p^2(N-1)}$. Proof. Let the answer for a specific $k$ be $D(k)$. WLOG let $p$ only divide $a_1$, if at all. By considering the value of $x_k$ and primitive roots, it follows that for $k > 2$ that \[ D(k) = \frac{\left\lfloor \frac{N}{p} \right\rfloor}{N} \cdot D(k-1) + \frac{N - \left\lfloor \frac{N}{p} \right\rfloor}{N} \cdot \frac{\gcd(p^2-p,n)}{(p^2-p)} \]Removing floors gives \[ \frac{1}{p} \cdot D(k-1) + \frac{\gcd(p-1, n)}{p^2}s < \frac{1}{p} \cdot D(k-1) + \frac{n}{p^2} \]The result then follows since $D(2) \le \frac{n}{p^2}$ and by considering the maximum influence of removing error bounds. $\blacksquare$ Claim: For primes $p$, \[ \sum_{p} \frac{1}{p(p-1)} < 0.95. \]Proof. Take an integral after finitely many terms. $\blacksquare$ As such, the density of prime square divisors for $x_i \in \{1, 2, \dots, N\}$ is at most \[ n + \sum_{n < p < (a_1 + \dots + a_k) N^n} \frac{n}{p(p-1)} + \frac{kn}{p^2(N-1)} < 1.95n + \frac{kn}{2(N-1)} \]giving the result for sufficiently large $N$.