USEMO P6 (Idk what to say here)

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

USEMO P6 (Idk what to say here)

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: USEMO 2020/6

The post below has been deleted. Click to close.

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

23531 posts

#1 h Oct 25, 2020, 11:03 PM • 4 Y

Y by Ss0-0, Rounak_iitr, Kingsbane2139, NO_SQUARES

Prove that for every odd integer $n > 1$ , there exist integers $a, b > 0$ such that, if we let $Q(x) = (x + a)^ 2 + b$ , then the following conditions hold:
$\bullet$ we have $\gcd(a, n) = gcd(b, n) = 1$ ;
$\bullet$ the number $Q(0)$ is divisible by $n$ ; and
$\bullet$ the numbers $Q(1), Q(2), Q(3), \dots$ each have a prime factor not dividing $n$ .

This post has been edited 1 time. Last edited by v_Enhance, Oct 26, 2020, 1:40 AM
Reason: fix typo

Z K Y

The post below has been deleted. Click to close.

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

186 posts

#2 h Oct 25, 2020, 11:07 PM • 6 Y

Y by MarkBcc168, yayups, Gaussian_cyber, Wizard_32, gvole, Aryan-23

Does this work?

This post has been edited 1 time. Last edited by SnowPanda, Oct 26, 2020, 12:08 AM

Z K Y

The post below has been deleted. Click to close.

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

538 posts

#3 h Oct 25, 2020, 11:09 PM • 1 Y

Y by Mango247

@above I think so, that's what I did

Z K Y

The post below has been deleted. Click to close.

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

539 posts

Mr.C

#4 h Oct 25, 2020, 11:27 PM

Y by

letting $b=2k$ where $(k,n)=1$ and $a=n-k$
this gives $2|Q(m)$ for every $m$ but not $n$ as its odd.
am i missing some thing?
@below .
but $Q(x)=2x+(2a+b)=2x+2n=2(x+n)$
so $2|Q(x)$ always holds.
note

This post has been edited 1 time. Last edited by Mr.C, Oct 25, 2020, 11:32 PM

Z K Y

The post below has been deleted. Click to close.

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

538 posts

#5 h Oct 25, 2020, 11:29 PM

Y by

@above you only get $2 \mid Q(m)$ for either odd $m$ or even $m$

Z K Y

The post below has been deleted. Click to close.

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

1010 posts

mira74

#6 h Oct 25, 2020, 11:34 PM • 4 Y

Y by MarkBcc168, Mango247, Mango247, Mango247

@2above, the OP should say $(x+a)^2+b$

alternate solution outline

This post has been edited 1 time. Last edited by mira74, Oct 25, 2020, 11:35 PM

Z K Y

The post below has been deleted. Click to close.

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

6877 posts

#9 h Oct 26, 2020, 1:40 AM • 6 Y

Y by mijail, Math_olympics, v4913, Wizard_32, HamstPan38825, Rounak_iitr

Let $p_1 < p_2 < \dots < p_m$ denote the odd primes dividing $n$ and call these primes small. The construction is based on the following idea:

Claim: For each $i= 1, \dots, m$ we can choose a prime $q_i \equiv 1 \pmod 4$ such that $\left( \frac{p_j}{q_i} \right) = \begin{cases} -1 & \text{if } j = i \\ +1 & \text{otherwise}. \end{cases}$ Proof. Fix $i$ . By quadratic reciprocity, it suffices that $q_i \equiv 1 \pmod 4$ and that $q_i$ is a certain nonzero quadratic residue (or not) modulo $p_j$ for $j \neq i$ .
By Chinese remainder theorem, this is a single modular condition, so Dirichlet theorem implies such primes exist. $\blacksquare$
We commit now to the choice $b = k q_1 q_2 \dots q_m$ where $k \ge 1$ is an integer (its value does not affect the following claim).

Claim: [Main argument] There are only finitely many integers $X$ for which $X^2+b$ has only small prime factors.
Proof. If $X^2 + b = p_1^{e_1} \dots p_m^{e_m}$ , then the RHS is a quadratic residue modulo $b$ . For any $i > 0$ , modulo $q_i$ we find $+1 = \prod_j \left( \frac{p_i^{e_i}}{q_i} \right) = (-1)^{e_i}$ so $e_i$ must be even. This holds for every $i$ though! In other words all $e_i$ are even.
Hence if $X$ has the property that $X^2 + b$ has only small prime factors, it must in fact be a solution to $X^2 + b = Y^2$ . And there are only finitely many solutions to this. $\blacksquare$
We now commit to choosing any $k \ge 1$ such that $k \equiv -q_1q_2 \dots q_m \pmod{n}$ which in particular means $\gcd(k,n) = 1$ .

Claim: [Hensel] There are infinitely many integers $a$ with $a^2 \equiv -b \pmod n$ .
Proof. It suffices to fix $i$ and prove $-b$ is a quadratic residue mod $p_i^e$ for $e \ge 1$ .
By construction, $-b \equiv (q_1 \dots q_m)^2 \pmod{p_i}$ is a nonzero quadratic residue modulo $p_i$ , i.e.\ there is a solution to $a^2 \equiv -b \pmod{p_i}$ . This implies the result for $e \ge 2$ as well, either by quoting Hensel lemma (since $p_i \nmid b$ ), or by quoting the fact that odd prime powers have primitive roots. $\blacksquare$
All that remains is to take $a$ satisfying the second claim larger than any of the finitely many bad integers in the fist claim. (The condition $\gcd(b,n) = 1$ holds by construction, and $\gcd(a,n) = 1$ follows automatically.)

Remark: [Motivational comments from Nikolai Beluhov] The solution I ended up with is not particularly long or complicated, but it was absurdly difficult to find. The main issue I think is that there is nothing in the problem to latch onto; no obvious place from which you can start unspooling the yarn. So what I did was throw an awful lot of different strategies at it until one stuck.
Eventually, what led me to the solution was something like this. I decided to focus on the simplest nontrivial case, when $n$ contains just two primes. I spent some time thinking about this, and then at some point I remembered that in similar Diophantine equations I've seen before, like $2^x + 3^y = z^2$ or $3^x + 4^y = 5^z$ , the main trick is first of all to prove that the exponents are even. After that, we can rearrange and factor a difference of squares. This idea turned out to be fairly straightforward to implement, and this is how I found the solution above.

Remark: [The problem is OK with $n$ even] The problem works equally well for $n$ even, but the modifications are both straightforward and annoying, so we imposed $n$ odd to reduce the time taken in solving this problem under exam conditions.

Remark: [On the choice of conditions] The conditions have been carefully chosen to prevent two ``trivial'' constructions.
If the condition that $\gcd(a,n) = \gcd(b,n) = 1$ is dropped, the problem becomes much easier because one can simply ensure that $\nu_p(Q(x))$ is bounded for all $p \mid n$ , by taking $b = n$ (or $b = \operatorname{rad} n$ , etc.).
If $b < 0$ is permitted, an easier approach to make sure that $Q(x)$ factors as the product of two polynomials by requiring $b$ to be the negative of a perfect square. Several easier approaches become possible in this situation. For example, one can try to use Kobayashi's theorem to generate the value of $a$ after ensuring the first two conditions are true.

Remark: [Author remarks on generalization] In general, if $b$ satisfies $\gcd(b,n) = 1$ , it seems like $Q(x)$ should have prime factors not dividing $n$ for sufficiently large $x$ (in other words, the first claim ``should'' always be true for $\gcd(b,n) = 1$ ). The author comments that this would be a statement of Kobayashi's theorem in the ring of integers of the quadratic field ${\mathbb Q}(\sqrt{-b})$ , but the organizers of the competition were not able to locate such a statement in the literature.

This post has been edited 1 time. Last edited by v_Enhance, Oct 26, 2020, 1:40 AM

Z K Y

The post below has been deleted. Click to close.

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

558 posts

#10 h Oct 26, 2020, 5:08 PM • 1 Y

Y by Kingsbane2139

This problem is really beautiful !

We start off with a classic result on QRs.

Lemma : Let $p_1, p_2, \cdots, p_n$ be odd primes and $f_1, f_2, \cdots, f_n \in \{-1,1\}$ . Then there exists a prime $q$ with the property that $(\tfrac{p_i}q) = f_i$ for all $1\leq i \leq n$

Proof : Assume $p_1<p_2<\cdots<p_n$ . By using quadratic reciprocity, it is equivalent to finding, for any $f_1,\ldots,f_n\in\{\pm 1\}$ , $\left(\frac q{p_i}\right)=f_i$ . However, as there are $\frac{p_i-1}2$ (nonzero) quadratic and non-quadratic residues modulo $p_i$ , we can choose some $k_1,\ldots,k_n$ such that:
$\left(\frac {k_i}{p_i}\right)=f_i\neq 0$ Then, the rest follows by considering $k$ satisfying
$k\equiv k_i\pmod{p_i}$ and $P=\prod\limits_{i=1}^n p_i$ . As $\gcd(k,P)=1$ and we have $k+\ell P$ satisfies the conditions, applying Dirichlet's Theorem to that arithmetic sequence we can find some prime $q$ (actually infinitely many). This ends the proof. $\square$

note

Let $n= \left ( \prod_{i=1}^{k} p_i^{\alpha_i} \right) \cdot \left ( \prod_{j=1}^{l} q_j^{\beta_j} \right)$ . Where $p_i \equiv 1\pmod 4$ and $q_i \equiv 3 \pmod 4$ . Pick a prime $r$ such that $(\tfrac{p_i}r)=1$ and $(\tfrac{q_i}r)=-1$ .

Now pick $a \equiv 1 \mod(n)$ and let $b$ satisfy the following criteria :

$b\equiv 1\pmod n$
$b\equiv 2 \pmod 4$
$b \equiv 0 \pmod r$

Suppose some for some $x$ , no other prime apart from the $p_i$ 's and $q_i$ 's divide $Q(x)$ . Set $Q(x) = \left ( \prod_{i=1}^{k} p_i^{a_i} \right) \cdot \left ( \prod_{j=1}^{l} q_j^{b_j} \right)$

Note that $Q(x) \equiv (x+a)^2 \pmod r$ hence we have :

$1 = \left ( \frac {Q(x)}r \right) =\left(\prod_{i=1}^k \left( \frac {p_i}r \right )^{a_i} \right) \cdot \left( \prod_{i=1}^l \left( \frac {q_i}r \right)^{b_i} \right)$
This forces $\sum_{i=1}^l{b_i}$ is even. This implies $Q(x)= 1 \pmod 4$ . Hence we get $(x+a)^2\equiv Q(x)-b \equiv 3 \pmod 4$ . Absurd. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Mathematicsislovely

245 posts

Mathematicsislovely

#11 h Oct 28, 2020, 9:52 AM • 2 Y

Y by Kar-98k, amar_04

Take $n-1$ distinct primes $p_1,p_2,\dots p_{n-1}$ with none of them dividing $n$ .

Claim:There exist a integer $Q$ such that it is a quadratic residue of each $p_1,p_2\dots,p_{n-1}$ and $n$ .
proof.Take $c_1,c_2,\dots c_{n-1}$ and $r$ which are quadratic residue with $p_1,p_2,\dots p_{n-1}$ and $n$ respectively and $gcd(r,n)=1$ .
Take by CRT, $Q\equiv c_i\pmod{p_i}$ for all $i=1,2\dots{n-1}$ and $Q\equiv r\pmod{n}$ . $\blacksquare$

This means,we can find $r_1,r_2,\dots r_{n-1}$ and $g$ such that

$Q\equiv r_1^2\pmod{p_1}$
$Q\equiv r_2^2\pmod{p_2}$
$\dots$
$\dots$
$Q\equiv r_{n-1}^2\pmod{p_{n-1}}$ and
$Q\equiv g^2\pmod {n}$

and $gcd(g,n)=gcd(Q,n)=gcd(r,n)=1$ .

Take by CRT,

$a\equiv r_i-i \pmod {p_i}$ for all $i=1,2,\dots {n-1}$
$a\equiv g\pmod {n}$ .So $gcd(a,n)=gcd(g,n)=1$

And take $b\equiv -Q\pmod{p_i}$ for all $i=1,2\dots {n-1}$ and $b\equiv-Q\pmod{n}$ which again by CRT, exists.
Finally, observe that,
$Q(0)=(a)^2+b\equiv g^2+b\equiv Q+(-Q)=0\pmod{n}$ .So $gcd(b,n)=1$ as $gcd(a,n)=1$
and $Q(i)=(i+a)^2+b\equiv r_i^2+b\equiv Q+(-Q)=0\pmod{p_i}$ for all $i=1,2\dots{n-1}$
$\blacksquare$

This post has been edited 2 times. Last edited by Mathematicsislovely, Oct 28, 2020, 11:14 AM

Z K Y

The post below has been deleted. Click to close.

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

Loppukilpailija

155 posts

Loppukilpailija

#12 h Oct 28, 2020, 5:29 PM • 6 Y

Y by mira74, Nathanisme, spartacle, MarkBcc168, v_Enhance, Aryan-23

v_Enhance wrote:

Remark: [Author remarks on generalization] In general, if $b$ satisfies $\gcd(b,n) = 1$ , it seems like $Q(x)$ should have prime factors not dividing $n$ for sufficiently large $x$ (in other words, the first claim ``should'' always be true for $\gcd(b,n) = 1$ ). The author comments that this would be a statement of Kobayashi's theorem in the ring of integers of the quadratic field ${\mathbb Q}(\sqrt{-b})$ , but the organizers of the competition were not able to locate such a statement in the literature.

It is indeed true that if $\gcd(b, n) = 1$ , then $Q(x)$ has a prime factor not dividing $n$ for all sufficiently large $x$ . One way to show this is as follows: If there are infinitely many $x$ which do not have this property, by the pigeonhole principle there is some integer $c$ with $\text{rad}(c) \mid n$ and $v_p(c) \le 2$ for all primes $p$ such that the equation
$\begin{align*} Q(x) = cy^3 \end{align*}$ has infinitely many solutions. This rearranges to the polynomial $cy^3 - b$ attaining infinitely many square values. Since $b \neq 0$ , the roots of $cy^3 - b$ are simple. This contradicts Theorem 3 of the paper starting at page 381 here.

In general, the results presented in the linked article are, together with elementary arguments, enough to characterize all polynomials which attain infinitely many perfect powers as their values. (Exercise!)

I would also like to remark that while Kobayashi's theorem is quite well known in olympiad circles, there are substantially stronger results out there. Side note. For the interested reader we refer to this, especially to Corollary 1.3 in Section 5.

This post has been edited 2 times. Last edited by Loppukilpailija, Nov 20, 2020, 12:01 AM
Reason: Fix typo

Z K Y

The post below has been deleted. Click to close.

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

1350 posts

i3435

#13 h Nov 7, 2020, 2:13 AM

Y by

This problem is really nice, but I'm surprised that it was hard to solve for the testsolvers who had ample time. I actually didn't do 4 or 5 (I have no idea how to do FEs and just skipped 5 because it was n-gon geo, even though it was the easiest day 2 problem), so I spent all my time on 6. The solution, while it seems hard to find when reading it, for me was easier because there's not really much else you can do unless you're super pro. It's like infinite monkey theorem but the weirdness of the problem forces you not to do infinite things. Forcing the $e_i$ s to be even was the only natural way to deal with the third condition, because although solving individual cases might be simple, it's hard to make those cases generalize(I think I tried showing a bunch of mod things, but it didn't work at all). You can mess up pretty badly though
I'm wondering why the statement included $a$ , when it could have just said $x^2+b$ has a finite amount of $Q(0),Q(1),Q(2)\dots$ that don't have any prime factors $n$ doesn't have. Maybe I'm missing something though.

Z K Y

The post below has been deleted. Click to close.

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

110 posts

#14 h Dec 9, 2020, 7:53 AM • 2 Y

Y by centslordm, gvole

That feel when the one of the parameters you're asked to construct is completely useless, and is a red herring ...
We start with what I would consider magical and groundbreaking to the problem.
$\color{magenta} \rule{25cm}{4pt}$
$\textcolor{magenta}{\textbf{\text{Elimination of a, and the insignificance of Q(0).}}}$ Let $g(X) = X^2+b$ . Then, it is sufficient to prove the existence of $b$ so that $-b$ is a quadratic residue mod $X$ , with the terms of $g(X)$ not being completely $"\text{reliant}"$ on $n$ .
(Abuse of convenient wording: a $"\text{reliant}"$ sequence is a sequence that has arbitrarily large $\textit{pure}$ numbers; i.e. numbers that all its prime divisors are small and divides $n$ .)
$\color{magenta} \rule{25cm}{1pt}$
Chunk 1: -b QR = existence of arbitrarily high powers of special primes Call the primes which divide $n$ special. We will prove that when $-b$ is a QR of all special primes, then there exists $a$ so that
$n \mid Q(0) = {A}^2+b$ More specifically, if we have proven that $\exists \ x_1 \ \text{so that} \ p\mid x_1^2+b \Rightarrow \exists \ x_{\alpha} \ \text{so that} \ p^{\alpha} \mid x_{\alpha}^2+b,$ we are done, since we can take $A$ mod $x_{\alpha}$ for each $p^{\alpha} \mid n$ , and be done with the construction since we can ensure that $p^{\alpha} \mid {A}^2+b$ for each $p$ dividing $n$ .
To prove that statement, just use Hensel's or induct from $x_a$ to $x_{a+1}$ by setting the appropriate $k$ in $x_{a+1} = x_a + k\cdot p^{a}$ . This works because $p \ne 2$ . $\blacksquare$
Chunk 2: Constructing a from $\textcolor{magenta}{\text{"nonreliancy"}}$ Let $Q(x)$ nonreliant --- there exists a threshold $N$ so that $Q(x)$ has a non-special prime divisor for each $x > N$ . Then, pick a number $a>N$ and $a \equiv A \pmod{n}$ , and we are done with the construction of $a$ and $b$ . $\blacksquare$
$\color{yellow} \rule{25cm}{2pt}$
$\textcolor{yellow}{\textbf{\text{Constructing an actual nonreliant sequence.}}}$ Fix the special primes $\{p_1,p_2,\ldots,p_m\}$ dividing $n$ .
Pair each of the nonempty subsets of $[m]$ , from $s_1,s_2,\ldots,s_{2^m-1}$ to the numbers $\{1,2,\ldots,2^m-2\}$ . First, we construct first primes $q_1,\ldots,q_{c}$ , $c = 2^m-1$ so that
$\prod_{j \in s_i} p_j \ \text{is not QR} \pmod{q_i}$ This is easy, as we can let $q_i \equiv 1 \pmod 4$ , expand $\left( \dfrac{\prod_{j \in s_i} p_j}{q_i} \right)$ into $\prod_{j \in s_i} \left(\dfrac{q_i}{p_j} \right)$ using quadratic reciprocity Lemma, and picking $(-1,1,\ldots,1)$ in order to obtain $1$ on their product (This is somewhat a classic lemma in quadratic reciprocity.)
For size effects, pick the $q$ s larger than any of the $p$ s.
Now, what is quite nonstandard is the "PHP" we're about to do to ensure the equation $g(X)=X^2+C = p_1^{\alpha_1}\ldots p_{m}^{\alpha_m}$ has no arbitrarily large solutions. Now pick $q_1q_2\ldots q_c \mid b$ (at this point, it may seem that there has been $2$ constructions of $b$ , but bear with me.)
Suppose that the numbers $\{\alpha_1,\alpha_2,\ldots,\alpha_{m}\}$ are not all even. Then, there exists a nonempty set of indices $s= \{i_1,i_2,\ldots,i_l\} \subseteq [m]$ so that $a_{i_{k}}$ is odd for all $1 \leq k\leq l$ . Then, the RHS is in the form $P \cdot q^2$ .
Consider the equation mod $q_j$ , where $j$ is the number paired with $s$ initially. Since $q_j \mid b$ , then $X^2+ \text{(something)} \cdot q_j$ is a quadratic residue mod $q_j$ . This is immediately contradicted by the RHS, as $P$ is not a quadratic residue mod $q_j$ by the construction we just provided.
If indeed all the numbers are even, $X^2+C$ has a finite number of solutions, hence we can just pick a threshold $N$ so that for all $X > N$ , $g(X)$ has prime divisors which are outside $\{p_1,p_2,\ldots,p_m\}$ . $\blacksquare$ $\blacksquare$
$\color{green}\rule{25cm}{1pt}$
$\textcolor{green}{\textbf{\text{Putting it all together.}}}$ We construct $b$ using large amounts of modulo in CRT: we would need
$b \equiv -QR\pmod n, b \equiv 0\pmod{q_1q_2\ldots q_c}$ to have the requirements in the first section ( $-b$ must be QR-ey mod $n$ ) and also in the second section (elimination of small-primed sequences). After that, being sure that the sequence is indeed not completely reliant on $n$ , we can set $a$ accordingly to the algorithm in Chunk 2 , so $n \mid Q(0)$ , too. We are then truly done. $\blacksquare$ $\blacksquare$ $\blacksquare$
Section overview, final rating
Motivation: This is not a construction problem, this is a diophantine problem in disguise.

This post has been edited 5 times. Last edited by alexiaslexia, Dec 11, 2020, 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.

1065 posts

Eyed

#15 h Feb 16, 2021, 1:36 AM • 2 Y

Y by centslordm, Mango247

Hopefully this works

Let the prime factors of $n$ be $p_{1}, p_{2}, \ldots p_{k}$ . Now, consider two primes $p, q$ that satisfy the following properties:
1. $p,q\neq p_{i}$ for $1\leq i\leq k$
2. $p\equiv 1\mod 4$
3. $q\equiv 3\mod 4$ .
4. $q\equiv 1\mod n$
5. $\genfrac{(}{)}{}{}{-p}{p_{i}} = 1$
Observe that we can choose such primes, since by dirichlet, such a $q$ exists, and the QR condition can just be translated into a modular condition, which also means by dirichlet, $p$ must exist.

Now, let $b = pq$ . From the above properties, since $\genfrac{(}{)}{}{}{-p}{p_{i}} = 1$ , and $q\equiv 1\mod p_{i}$ , this means $\genfrac{(}{)}{}{}{-pq}{p_{i}} = 1$ . Thus, there must be some $a$ such that for all $p_{i}$ , we have $p_{i} | a^{2} + b$ (this is a consequence of CRT).

Observe that if an integer $r$ is a QR of $p_{i}$ such that $p_{i}$ does not divide $r$ , then it must also be a QR of $p_{i}^{2}$ . This is because if $a^{2}\equiv r\mod p_{i}$ , then consider $(a+p_{i})^{2}, (a+2p_{i})^{2},\ldots (a+(p_{i}-1)p_{i})^{2}\mod p_{i}^{2}$ , and observe that they must be a permutation of $r, r+p_{i},\ldots r+(p_{i}-1)p_{i}\mod p_{i}^{2}$ . Similarly, $r$ must also be a QR of $p_{i}^{3}, p_{i}^{4}$ , and so on. We can conclude by CRT that there must exist some $a$ such that $n | a^{2} + b$ .

Now we show that these two choices of $a,b$ work. First, observe that $b\equiv 3\mod 4$ . If $x+a$ was odd, then $2 | (x+a)^{2} + b$ , so we're done. Now, assume $x+a$ was even, and assume some $x+a$ existed such that
$(x+a)^{2} + b = p_{1}^{a_{1}}p_{2}^{a_{2}}\ldots p_{k}^{a_{k}} = M$ Assume the first $p_{1}, p_{2}, \ldots p_{l}\equiv 3\mod 4$ , and the rest of the primes are $1\mod 4$ .

By QR on $\mod p$ , we must have $\genfrac{(}{)}{}{}{M}{p} = 1$ . Observe that for $p_{i}\equiv 3\mod 4$ , we have
$\genfrac{(}{)}{}{}{p_{i}}{p} = \genfrac{(}{)}{}{}{p}{p_{i}} = -\genfrac{(}{)}{}{}{-p}{p_{i}}= -1$ and for $p_{i}\equiv 1\mod 4$ , we have
$\genfrac{(}{)}{}{}{p_{i}}{p} = \genfrac{(}{)}{}{}{p}{p_{i}} = \genfrac{(}{)}{}{}{-p}{p_{i}}= 1$ Now, we have
$1 = \genfrac{(}{)}{}{}{M}{p} = \prod_{i=1}^{k}\genfrac{(}{)}{}{}{p_{i}^{a_{i}}}{p}= \prod_{i=1}^{l}\genfrac{(}{)}{}{}{p_{i}}{p}^{a_{i}} \cdot \prod_{i=l+1}^{k}\genfrac{(}{)}{}{}{p_{i}}{p}^{a_{i}}= (-1)^{\sum_{i=1}^{l}a_{i}}$ This means the sum of the exponents of primes $p_{1}, p_{2},\ldots p_{l}$ is even. Since all of these primes are $3\mod 4$ , this also means $M$ must be $1\mod 4$ . However, this means we have $(x+a)^{2} + b\equiv 1\mod 4$ , a contradiction since $b\equiv 3\mod 4$ . We conclude that $Q(1), Q(2), \ldots$ all have prime factors not dividing $n$ .

This post has been edited 2 times. Last edited by Eyed, Feb 16, 2021, 1:53 AM

Z K Y

The post below has been deleted. Click to close.

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

272 posts

#16 h Apr 17, 2021, 5:56 AM • 1 Y

Y by Rg230403

Nice Problem !!

franzliszt wrote:

Prove that for every odd integer $n > 1$ , there exist integers $a, b > 0$ such that, if we let $Q(x) = (x + a)^ 2 + b$ , then the following conditions hold:
$\bullet$ we have $\gcd(a, n) = gcd(b, n) = 1$ ;
$\bullet$ the number $Q(0)$ is divisible by $n$ ; and
$\bullet$ the numbers $Q(1), Q(2), Q(3), \dots$ each have a prime factor not dividing $n$ .

Take $a=1$ !
Let primes dividing $n$ be $q_1,\cdots ,q_s , r_1,\cdots,r_t$ , where $q_i \equiv 1 (\text{mod} 4)$ and $r_j \equiv 3 (\text{mod} 4)$
By Drichlet find a prime $p$ congruent to $-1$ modulo each $r_i,q_j$ and $1$ modulo $4$ .
So we have $\left( \frac{q_i}{p}\right ) = 1$ and $\left( \frac{r_j}{p}\right ) = -1$

Now find a $k$ such that $kn \equiv 1 (\text{mod} p)$ and $4|k$ , which implies $kn = 1 +pl$ and define $b=pl$ so $Q(x) = (x+1)^2+pl$
So we have gcd $(1,n)=$ gcd $(b,n)=1$ and $Q(0) = kn$
$4|k \implies pl \equiv 3(\text{mod} 4)$ .
Now we will show that $Q(t)$ is divisible by some prime which does not divide $n$ for all $t$ .
If possible $Q(t) =(t+1)^2+pl = q_1^{\alpha_1}q_2^{\alpha_2}\cdots q_s^{\alpha_s} r_1^{\beta_1}r_2^{\beta_2}\cdots r_t^{\beta_t}$

Hence $\left( \frac{Q(t)}{p}\right ) = 1 \implies \beta_1+\beta_2+\cdots+\beta_t$ is even .

So $Q(t) \equiv 1 (\text{mod} 4) \implies (t+1)^2 \equiv 2 (\text{mod} 4)$
Which is a contradiction.
QED.

Z K Y

The post below has been deleted. Click to close.

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

966 posts

#17 h Jan 14, 2022, 3:45 AM • 3 Y

Y by Catsaway, centslordm, Maths_Girl

Solved with rama1728. Neat problem.

Let $\{p_1,p_2, \dots p_k\}$ be the primes dividing $n.$ It suffices to choose an odd $b$ where only finitely many integers of the form $x^2 + b,$ where $x$ is an integer, share all prime factors with $n.$ Then we could just choose a very large $a$ that fits the bill. For each $1\le i \le k,$ let $q_i$ be a prime where $p_j$ is a QR $\pmod{q_i}$ for any $j \ne i,$ but $p_i$ is a QNR.

Set $q_i \equiv 1 \pmod{4},$ so that it is sufficient that $q_i$ is a QR $\pmod{p_j}$ for any $j \ne i,$ but a QR $\pmod{p_i},$ using Quadratic Reciprocity. By CRT and Dirichlet's such a $q_i$ exists for each $i.$

Let $b=q_1q_2 \dots q_k$ (obviously odd) and suppose $x^2+b=N,$ where $N$ is a number sharing all prime factors with $n.$ Let $N$ have prime factorization $p_1^{a_1}p_2^{a_2} \dots p_k^{a_k}.$ For any $1 \le i \le k,$ we have $N$ is a QR $\pmod{q_i},$ so $p_i^{a_i}$ is a QR $\pmod{q_i}$ and $a_i$ is even. So $N$ is a perfect square. Since gaps between consecutive perfect squares become arbitrarily large, there can only be finitely such $N.$

This post has been edited 3 times. Last edited by squareman, Jan 14, 2022, 3:54 AM

Z K Y

The post below has been deleted. Click to close.

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

236 posts

#18 h Mar 28, 2025, 10:35 PM

Y by

Let $\operatorname{rad}(n)=p_1 \dots p_t$ where $p_i$ are primes.

Choose $b=Cq_1 \dots q_t$ where $q_i \equiv 1 \pmod 4$ , $p_i \nmid C$ , $q_i \nmid C$ and $\left(\frac{-c}{p_i} \right)=1; \qquad \left(\frac{q_i}{p_i} \right)=-1;\qquad \left(\frac{q_j}{p_i} \right)=1 \text{ for } i \ne j$ Which exists by CRT+Dirichlet. This also says $-b$ is a QR mod $n$ (by Hensel's lemma and CRT).

Claim: If for some $k$ , we have $\operatorname{rad}(k^2+b) \mid n$ then $k^2+b$ is a perfect square.
Proof: See that by QR we have $1=\left(\frac{k^2}{q_i} \right)=\left(\frac{k^2+b}{q_i} \right)=\left(\frac{p_i}{q_i} \right)^{\nu_{p_i}(k^2+b)}=(-1)^{\nu_{p_i}(k^2+b)} \iff 2 \mid \nu_{p_i}(k^2+b)$ For all $i$ and so done as $k^2+b$ has no other prime factors by assumption. $\square$

Obviously see that $k^2+b$ is not a perfect square for large $k$ so just choose $a$ to be very large (exists as $-b$ is a QR mod $n$ ) such that $(\ell+a)^2+b$ is never a perfect square for $\ell \ge 1$ .

Z K Y

The post below has been deleted. Click to close.

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

1536 posts

#19 h Apr 22, 2025, 5:47 AM

Y by

Suppose $n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ where $p_1< \cdots p_k$ then we make our pick in the following way:
Focus on a random $p_j$ prime term then we want to pick a set of primes $q_i$ (for $1 \le i \le k$ ) such that $\left(\frac{p_j}{q_i} \right)$ is $1$ unless $j=i$ in which case it is $-1$ . The way to do this is basically picking $q_{\ell} \equiv 1 \pmod 4$ for all $1 \le \ell \le k$ at first to use Law of Quadratic reciprocity and then the condition of being QR or NQR is entirely a modular condition so stacking over all $j$ 's and $i$ 's using CRT and Dirichlet it is in fact always possible to do this because $n$ is odd (so $p_1 \ne 2$ which is key for this to work, and also make sure to make them really large lol).
Now suppose that there existed some $l^2+b$ such that it has at most the prime factors of $n$ where our first pick is $b \equiv 0 \pmod{q_1 \cdots q_k}$ then $l$ is not large at all.
And the reason for this is that we have this thing being a QR $\pmod b$ always and therefore is QR $\pmod{q_{\ell}}$ for some random $\ell$ among the range and therefore it means that $1=(-1)^{\nu_{p_{\ell}}(l^2+b)} \pmod{q_{\ell}}$ and thus from here spamming it it turns out that $l^2+b$ is a square however by fixing some $b$ we can see this eventually just won't be true as $l$ becomes large.
In order to finish all we need is to set $a$ properly, so we want $n \mid a^2+b$ so write $b$ as $b' \cdot (q_1 \cdots q_k)$ but also we want $\gcd(a,n)=1$ so it remains to set $b'$ so that $-b$ is a QR $\pmod n$ and in a way that the square congruent to it is always coprime to $n$ which is easy by setting $b' \equiv -q_1 \cdots q_k \pmod n$ because then in fact $a \equiv \pm q_1 \cdots q_k \pmod n$ is a pick and either way $\gcd(a,n)=1$ must remain true by how large the primes chosen are for $n$ and thus we are done :cool:

:cool:

.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a