Fun.... polynomial divisors

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

Fun.... polynomial divisors

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: USEMO 2022/5

The post below has been deleted. Click to close.

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

DottedCaculator

7345 posts

DottedCaculator

#1 h Oct 23, 2022, 11:13 PM • 6 Y

Y by LLL2019, rama1728, Kingsbane2139, centslordm, Mango247, Mango247

Let $\tau(n)$ denote the number of positive integer divisors of a positive integer $n$ (for example, $\tau(2022) = 8$ ). Given a polynomial $P(X)$ with integer coefficients, we define a sequence $a_1, a_2,\ldots$ of nonnegative integers by setting
$a_n =\begin{cases}\gcd(P(n), \tau (P(n)))&\text{if }P(n) > 0\\0 &\text{if }P(n) \leq0\end{cases}$ for each positive integer $n$ . We then say the sequence has limit infinity if every integer occurs in this sequence only finitely many times (possibly not at all).

Does there exist a choice of $P(X)$ for which the sequence $a_1$ , $a_2$ , . . . has limit infinity?

Jovan Vuković

This post has been edited 8 times. Last edited by DottedCaculator, Oct 24, 2022, 12:29 AM

Z K Y

The post below has been deleted. Click to close.

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

1301 posts

#2 h Oct 23, 2022, 11:14 PM • 2 Y

Y by Sross314, LLL2019

Solution

This post has been edited 2 times. Last edited by CANBANKAN, Oct 24, 2022, 12:55 AM

Z K Y

The post below has been deleted. Click to close.

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

6877 posts

#4 h Oct 24, 2022, 12:31 AM • 6 Y

Y by ApraTrip, bjump, HamstPan38825, PROA200, levimpcbranco, Kingsbane2139

We claim the answer is no, such $P$ does not exist.

Clearly we may assume $P$ is nonconstant with positive leading coefficient. Fix $P$ and fix constants $n_0, c > 0$ such that $c = P(n_0) > 0$ . We are going to prove that infinitely many terms of the sequence are at most $c$ .

We start with the following lemma.
Claim: For each integer $n \ge 2$ , there exists an integer $r = r(n)$ such that

For any prime $p$ which is at most $n$ , we have $\nu_p(P(r)) = \nu_p(c)$ .
We have $c \cdot \prod_{\text{prime }p \le n} \le r \le 2c \cdot \prod_{\text{prime }p \le n} p.$

Proof. This follows by the Chinese remainder theorem: for each $p \le n$ we require $r \equiv n_0 \pmod{p^{\nu_p(c)+1}}$ , which guarantees $\nu_p(P(r)) = \nu_p(P(n_0)) = \nu_p(c)$ . Then there exists such an $r$ modulo $\prod_{p \le n} p^{\nu_p(c)+1}$ as needed. $\blacksquare$
Assume for contradiction that all $a_i$ are eventually larger than $c$ . Take $n$ large enough that $n > c$ and $r = r(n)$ has $a_r > c$ . Then consider the term $a_r$ :

Using the conditions in the lemma it follows there exists a prime $p_n > n$ which divides $a_r = \gcd(P(r), \tau(P(r)))$ (otherwise $a_r$ , which divides $P(r)$ , is at most $c$ ).
As $p_n$ divides $\tau(P(r))$ , this forces $P(r)$ to be divisible by (at least) $q_n^{p_n-1}$ for some prime $q_n$ .
For the small primes $p$ at most $n$ , we have $\nu_p(P(r)) = \nu_p(c) < c < n \le p_n - 1$ . It follows that $q_n > n$ .
Ergo, $P(r) \ge q_r^{p_r-1} > n^n.$

In other words, for large enough $n$ , we have the asymptotic estimate $\begin{align*} n^n &< P(r) = O(1) \cdot r^{\deg P} \\ &= O(1) \cdot c^{\deg P} \cdot \prod_{\text{prime } p \le n} p^{\deg p} \\ &< O(1) \cdot n^{\deg P \cdot \pi(n)} \end{align*}$ where $\pi(n)$ denotes the number of primes less than $n$ . For large enough $n$ this is impossible since the primes have zero density: $\lim_{n \to \infty} \frac{\pi(n)}{n} = 0.$
Remark: For completeness, we outline a short elementary proof that $\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$ . For integers $M > 0$ define $\delta(M) \coloneqq \prod_{p \le M} \left( 1 - \frac 1p \right).$ Then $\pi(n) < \delta(M)n + O(M)$ , so it suffices to check that $\lim_{M \to \infty} \delta(M) = 0$ . But $\frac{1}{\delta(M)} = \prod_{p \le M} \left( 1 - \frac 1p \right)^{-1} = \prod_{p \le M} \left( 1 + \frac1p + \frac{1}{p^2} + \dots \right) \ge 1 + \frac 12 + \dots + \frac 1M$ which diverges for large $M$ .

This post has been edited 1 time. Last edited by v_Enhance, Oct 24, 2022, 12:31 AM

Z K Y

The post below has been deleted. Click to close.

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

20 posts

Remon

#5 h Oct 24, 2022, 7:43 AM • 1 Y

Y by Mango247

https://artofproblemsolving.com/community/c6h539544p3104308 6floor ,this method can help us find n such that almost all the prime factors of P(n) are large.

Z K Y

The post below has been deleted. Click to close.

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

186 posts

#6 h Oct 24, 2022, 12:01 PM

Y by

Solution

This post has been edited 1 time. Last edited by SnowPanda, Oct 24, 2022, 12:02 PM

Z K Y

The post below has been deleted. Click to close.

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

primesarespecial

364 posts

primesarespecial

#8 h Nov 7, 2022, 5:53 AM • 1 Y

Y by PRMOisTheHardestExam

Solution attached below..(The second pic is useless basically, I don't know why I even wrote bezout,the existence for (M+1) is obvious anyways and for primes greater than p_n,the existence of non roots mod p,is obvious by lagrange.

Attachments:

This post has been edited 3 times. Last edited by primesarespecial, Nov 7, 2022, 12:23 PM

Z K Y

The post below has been deleted. Click to close.

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

80 posts

#9 h Nov 7, 2022, 1:03 PM

Y by

Please someone can check my solution?

Attachments:

USEMO 2022 P5.pdf (87kb)

Z K Y

The post below has been deleted. Click to close.

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

302 posts

#10 h Nov 12, 2022, 5:42 AM • 1 Y

Y by IAmTheHazard

We will prove the general result for any $P \colon \mathbb{Z} \to \mathbb{Z}$ but not necessarily $P \in \mathbb{Z}[X]$

Suppose $d$ divides $P(n)$ for all $n \in \mathbb{Z}$ . Thus, we let $P(x) = d \cdot Q(x)$ where $Q \colon \mathbb{Z} \to \mathbb{Z}$ . By CRT on the prime divisors of $d$ there exists a positive integer $a$ where $\gcd(d, Q(dn+a))=1$ for every $n \in \mathbb{Z}$ . So, we will let $f(x)=Q(dx+a)$ .

So, there is no number $>1$ dividing every $f(n)$ . Let $p_1<p_2< \cdots$ be all the primes dividing at least one $f(n)$ . If we let $N$ be a sufficiently large positive integer, then by CRT there is an $M<p_1p_2 \cdots p_N$ where $p_i$ does not divide $f(M)$ for any $i \leq N$ . Thus, let $f(M)=q_1^{\alpha_1}q_2^{\alpha_2} \cdots q_k^{\alpha_k}$ . We should see that $\gcd(q_1^{\alpha_1}q_2^{\alpha_2} \cdots q_k^{\alpha_k},(\alpha_1+1)(\alpha_2+1) \cdots (\alpha_k+1))$ becomes unbounded. So, there must be some $\alpha_i$ and $q_j$ where $\alpha_1 > q_j$ . This clearly implies that $f(M) > q_1^{q_1} > p_N^{p_N}$ but this gets too big by prime number theorem. We look back at $d \cdot f$ by realizing $\tau(d \cdot f(n)) = \tau(d) \cdot \tau(f(n))$ so $\gcd(n,\tau(d) \cdot f(n))<\tau(d) \cdot \gcd(n,f(n))$ Which we proved cannot grow at a sufficient speed. Done.

This post has been edited 1 time. Last edited by blackbluecar, Apr 4, 2023, 11:46 PM

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#11 h Aug 19, 2023, 12:01 AM • 1 Y

Y by centslordm

Here is a... suboptimal solution in terms of elegance

The answer is no. Suppose otherwise; clearly $P$ is nonconstant, so let $\deg P=d>0$ .

Write
$P=f_1^{e_1}\ldots f_k^{e_k}$ where for all $1 \leq i \leq k$ , $f_i$ is an irreducible integer polynomial, $e_i\geq 1$ , and all the $f_i$ are pairwise distinct (hence coprime). We will construct (by CRT) a positive integer $m$ satisfying a number of desirable properties. Consider massive positive integers $A<B<C$ with $B$ and $C$ to be selected later, such that

For all $n\geq A$ , $P(A)>0$ ,
For all (finitely many) primes $p$ dividing every value of $P(n)$ , $p<A$ ,
By Bezout's, for all $n \geq A$ and all $i$ , we have $\gcd(f_i(n),f_i'(n))<A$ , since $f_i$ and $f_i'$ are coprime,
By Bezout's, for all $n \geq A$ and all $i \neq j$ , we have $\gcd(f_i(n),f_j(n))<A$ ,
By Dirichlet, there exists some prime $Q \equiv 1 \pmod{e_1\ldots e_k}$ such that $Q<A$ and $Q$ does not divide every value of $P(n)$ .

Let the primes (less than $A$ ) be $r_1,\ldots,r_a$ (this includes $Q$ ) and let $g_1,\ldots,g_a$ be nonnegative integers such that for all $i$ , $r_i^{g_i}$ divides $P(n)$ for all $n$ , but $r_i^{g_i+1}$ doesn't always divide $P(n)$ . Therefore, for each $i$ , we can impose a modulo- $r_i^{g_i+1}$ condition on $m$ to ensure that $\nu_{r_i}(P(m))=g_i$ .

Now let $q_1,\ldots,q_b$ be the primes in $[A,B)$ . Since none of these divide every value of $P(n)$ , for each $i$ we can impose a modulo- $q_i$ condition on $m$ to ensure that $q_i \nmid P(m)$ .

Finally let $p_1,\ldots,p_c$ be the primes in $[B,C)$ which divide some value of $P(n)$ . For any $i,j$ , we have $p_i \mid f_j(n) \implies p_i \nmid f_j'(n)$ , so for Hensel lifting-related reasons, for any $k$ we can impose a modulo- $p_i^{k+1}$ condition on $m$ so that $\nu_{p_i}(f_i(m))=k$ . Therefore, for each $i$ , pick some $j$ such that $p_i$ divides some value of $f_j(n)$ , and impose a modulo- $p_i^{\frac{Q-1}{e_j}+1}$ condition on $m$ such that $\nu_{p_i}(f_j(m))=\tfrac{Q-1}{e_j}$ . Since $p_i$ won't divide $f_h(n)$ for any $h \neq j$ since $p_i>A$ , it follows that $\nu_{p_i}(P(m))=Q-1$ .

Observe that we can evidently find some $m$ satisfying these conditions which is $O((q_1\ldots q_b)(p_1\ldots p_c)^Q)$ but also arbitrarily large (by taking $B$ large and selecting the second-smallest possibility for $m$ ), since the product of $r_i^{g_i+1}$ is a constant. Then $P(m)$ is $O((q_1\ldots q_b)^d(p_1\ldots p_c)^{Qd})$ . Separate $P(m)$ into the product of two "parts": one consisting of the product of primes less than $C$ , which equals
$\left(\prod_{i=1}^a r_i^{g_i}\right)\left(\prod_{i=1}^c p_i^{Q-1}\right),$ and the other, which is the product of primes at least $C$ . Hence the "other part" of $P(m)$ is $O((q_1\ldots q_b)^d(p_1\ldots p_c)^{Q(d-1)+1})$ . Now consider the contribution of each part to $\gcd(P(m),\tau(P(m)))$ : specifically, for the first part, the contribution from $\tau(r_i^{g_i})=g_i+1$ is bounded for each $i$ , so we can ignore it, and the contribution from $\tau(p_i^{Q-1})=Q$ is zero, since $Q \nmid P(m)$ . Therefore, if $\gcd(P(m),\tau(P(m)))$ is unbounded as $m$ grows large (by making $B$ large), we will need some prime $p \geq C$ such that $\tau(p^{\nu_p(P(m))})$ contributes arbitrarily large quantities to $\gcd(P(m),\tau(P(m)))$ . This means that we must be able to find some $p$ with $p_i \mid \nu_p(P(m))$ for some $i$ , since if $\nu_p(P(m))$ has prime factors in $[A,B)$ they don't matter, and the contribution of any primes smaller than $A$ is bounded by the product of $r_i^{g_i}$ (i.e. the " $<A$ part" of $P(m)$ ), which is finite.

On the other hand, if we take $C \approx B\sqrt{\log B}$ , then by PNT the the "other part" of $P(m)$ is $O\left(B^{\frac{B}{\log B}d}(B\sqrt{\log B})^{\frac{B}{\sqrt{\log B}}(Q(d-1)+1)}\right)$ , since $\frac{B\sqrt{\log B}}{\log(B\sqrt{\log B})} \leq \frac{B\sqrt{\log B}}{\log B}$ , but if $p_i \mid \nu_p(P(m))$ for some $i$ , then we need $P(m) \geq p^{p_i}$ which is $\Omega((B\sqrt{\log B})^B)$ , which dominates as $B \to \infty$ : contradiction. $\blacksquare$

Edit: Wait shoot $C$ (and everything related to it) isn't necessary lmao. If we drop everything related to $C$ then $P(m)$ will be $O(B^{\frac{B}{\log B}d})$ , but we will need some prime $p \geq B$ such that $\nu_p(P(m))$ is divisible by a prime at least $B$ , hence we need $P(m) \geq B^B$ , which is a contradiction. This is the same as the other solutions

This post has been edited 3 times. Last edited by IAmTheHazard, Aug 19, 2023, 12:17 AM

Z K Y

The post below has been deleted. Click to close.

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

109 posts

#12 h Aug 19, 2023, 5:09 PM

Y by

I don't know whether this is correct or not. Can someone please check.

We claim that the answer is no.
Let $\deg P(n)=t$ Then, $P(n)=\sum_{i=1}^t a_i x^i$ Evaluate $P(\alpha)$ for $n=p_1p_2\dots p_k$ where $p_1,p_2, \dots p_k$ are the smallest $n$ primes. For large enough $k$ , we have that $P(\alpha) < (a_t+1)\alpha^t$ . Also, note that $P(n)$ doesn't have any prime divisors $< p_k$ except finitely many. Hence, $p^{kn} > P(\alpha)$ for any $p \vert P(n)$ . From this, we can conclude that $\nu_p(P(n)) < kn$ for any $p$ . We denote $\nu_p(P(n))$ by $e$

$\tau (P(n))$ is given by $\prod_{i=1}^n (e_i+1)$ where $e_i$ are the coefficients of the primes dividing $P(n)$ . So, $\tau (P(n))$ is not divisible by any $p$ if $p>kn$ due to the fact proved earlier. So, $P(n)$ has prime factors $p>p_k$ (except finitely many) and $\tau (P(n))$ has prime factors $p<kn$ . This forces that $\gcd(P(n), \tau (P(n)))$ is small for infinitely many $n$ .

Z K Y

The post below has been deleted. Click to close.

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

1535 posts

#13 h Aug 22, 2023, 6:47 AM

Y by

Fix a polynomial $P = c_0x^d + c_1x^{d-1} + \dots + c_{b}x^b$ with positive leading coefficient, as the result is immediately no for negative coefficients. Let $M = \operatorname{lcm}(c_0, c_1, \dots, c_d)$ and $m = \gcd(c_0, c_1, \dots, c_d)$ . over nonzero coefficients. Let $c_b$ be the minimal nonzero coefficient.
FTSOC assume that $a_n$ steadily increases with $n$ .

Define by CRT $\begin{align*} &N \equiv a_p \pmod{p}, d < p < n \\ &N \equiv 0 \pmod{p^{\nu_p(M) + 1}}, p \le d \end{align*}$ Choose $a_p$ such that $p \nmid \frac{P(a_p)}{m}$ , which is possible by Lagrange's theorem.

Take $N$ sufficiently large such that $P(N) < n^n$ which is possible by the prime number theorem and primorial growth rate.

Claim: For $p < n$ and some fixed $K$ independent of $N$ , either $b = 0$ and $\nu_p(P(N))$ is fixed over $N$ , or $b \ge 1$ and $\nu_p(P(N)) = b \cdot \nu_p(N) = b \cdot (\nu_p(M) + 1)$ .
Proof. Follows by construction. $\blacksquare$
Hence, since primes $p \le d$ are bounded in $P(N)$ , primes $d < p < n$ aren't present in $P(N)$ , and primes $p > n$ aren't present in $\tau(P(N))$ , the result follows.

This post has been edited 10 times. Last edited by YaoAOPS, Aug 22, 2023, 6:56 PM

Z K Y

The post below has been deleted. Click to close.

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

2463 posts

#14 h Sep 1, 2023, 2:00 PM • 3 Y

Y by PRMOisTheHardestExam, YaoAOPS, MS_asdfgzxcvb

The answer is NO. The plan is the same as in #2 with different realization. We will show that for infinitely many $n\in\mathbb{N}$ the prime factorization of $P(n)$ consists of primes with small exponents. We prove it by counting the number of $n$ 's for which $p^s\mid P(n)$ for a prime $p$ and sufficiently large $s$ . Here the Hensel's lemma will do the job. This allows us to show existence of a bounded subsequence of $(a_n)$ .

Proposition 1. For each polynomial $P(x)$ with integer coefficients there exists a constant $M>0$ such that for infinitely many $n\in\mathbb{N}$ all the exponents of the prime factoring of $P(n)$ are less than $M$ .

Let us first see how this claim helps. Indeed, suppose
$\displaystyle P(n)=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} \text{ and } \alpha_i< M,i=1,2,\dots,k.$ Then $\tau(P(n))=(\alpha_1+1)\cdots(\alpha_k+1)$ and the prime factors of it are less or equal to $M$ . Each of them can participate in the factoring of $P(n)$ with degree at most $M$ , hence $a_n\le M^M$ and it holds for infinitely many $n$ .

The proof of Proposition 1. is based on an interesting and important fact (Korea 2016 TST ), so we formulate it as a standalone claim.

Proposition 2. Let $P(x)$ be an irreducible polynomial with integer coefficients and $p$ be a prime number. Then there exists a constant $M>0$ such that for sufficiently large $m$ the number of the solutions of the congruence
$\displaystyle P(x)\equiv 0\pmod {p^m}$ is exactly $M$ .

Proof (of Proposition 2). The proof is based on Hensel's lemma. First, let us see that for sufficiently large $N$ if
$\displaystyle P(x_0)\equiv 0\pmod{p^N}$ then
$\displaystyle P'(x_0)\not\equiv 0\pmod{p^N}.$ Indeed, since $P$ is irreducible, $P(x)$ and $P'(x)$ are coprime as polynomials, hence
$\displaystyle a(x)P(x)+b(x)P'(x)=c$ where $a(x),b(x)\in \mathbb{Z}[X], c\in\mathbb{Z}, c\neq 0.$ We take $N$ so that $2^N>c.$ So, if $p^N\mid P(x_0)$ it follows $p^N\nmid P'(x_0).$
Now, let $x_1,x_2,\dots,x_M$ be the roots of
$\displaystyle P(x)\equiv 0\pmod{p^N}.$ It follows by Hensel's lemma that for any $m\ge N$ each of $x_i, i=1,2,\dots,x_M$ is "lifted" uniquely to a root $x'_i$ modulo $p^m$ with $x'_i\equiv x_i\pmod {p^N}$ and these are the only roots of $P(x)\equiv\pmod {p^m}$ . $\square$

Remark. Note that we actually proved as a bonus that there is a constant $N$ which depends only on the polynomial $P$ such that for any prime $p$ and any $m>N$ the number of solutions of
$\displaystyle P(x)\equiv 0\pmod{p^m}$ is at most $p^N$ . We are ready to prove Proposition 1.

Proof (of Proposition 1). Let us first consider the case when $P(x)$ is an irreducible polynomial. Let $p_1,p_2,\dots,p_k$ be the first $k$ prime numbers, where $k\in \mathbb{N}$ . According to the remark after the Proposition 1.2, for any $s\in\mathbb{N}, s\ge N$ each congruence
$\displaystyle P(x)\equiv 0 \pmod{p^s}\,,\,i=1,2,\dots, k$ has at most $p^N$ solutions. Let us now count the numbers of $n$ 's $1\le n\le p_k$ for which $P(n)$ is multiple of $p_i^s$ for some $i, 1\le i\le k$ . This number is at most $\varepsilon\cdot p_k$ where
$\begin{align*}\varepsilon&:= \frac{p_1^N}{p_1^s}+\frac{p_2^N}{p_2^s}+\dots+\frac{p_k^N}{p_k^s} \\ &= \frac{1}{p_1^{s-N}}+\frac{1}{p_2^{s-N}}+\dots+\frac{1}{p_k^{s-N}}\\ &< \sum_{j=1}^{\infty}\frac{1}{p_j^{s-N}}\qquad(1). \end{align*}$ Since $N$ depends only on the polynomial $P(x)$ , we can take $M$ sufficiently large such that $\varepsilon<1/2$ for $s\ge M$ and all $k\in \mathbb{N}$ . It means that there is $n\in[p_k/2, p_k]$ such that $P(n)$ is not multiple of $p_i^M, i=1,2,\dots, k$ . But in this case $P(n)$ is also not multiple of any $p^M$ for a prime $p>p_k$ since $P(n)<n^M<p^M$ if we choose $M$ be larger than $\deg(P)$ and $p_k$ is large enough.
Thus, we found $n\ge p_k/2$ that satisfies the requirements of Proposition 1 for some $M>0$ (not depending on $k$ ). We can consecutively choose $k$ bigger and bigger thus finding infinitely many $n$ satisfying the statement of Proposition 1.

Let us now consider the case when $P(x)$ is reducible polynomial with integer coefficients. It can be represented as
$\displaystyle P(x)=P_1(x)P_2(x)\cdots P_{\ell}(x)$ where $P_i(x), i=1,2,\dots,\ell$ are irreducible polynomials with integer coefficients. We apply the same argument to each of these polynomials, but with $\displaystyle \varepsilon<\frac{1}{2\ell},$ and conclude that there is $n\in [p_k/2,p_k]$ such that $p_j^M\nmid P_i(n), j=1,2,\dots,k;i=1,2,\dots,\ell$ . Hence $p_j^{\ell M}\nmid P(n)$ .

This post has been edited 1 time. Last edited by dgrozev, Sep 1, 2023, 7:37 PM

Z K Y

The post below has been deleted. Click to close.

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

716 posts

#16 h Apr 29, 2025, 5:50 AM

Y by

Hope this is true :blush:

:blush:

There does not exist such polynomial. Suppose that the leading coefficient of $P$ is positive. Let $\deg P=d$ . Call a prime special iff it divides $P(x)$ for some integer $x$ . Let $p_1<p_2<\dots<p_m<\dots$ be all special primes. By Chinese Remainder Theorem we can pick $P(t)=p_1^{a_1}\dots p_m^{a_m}r_1^{b_1}\dots r_x^{b_x}$ where $t,m$ are sufficiently large. Suppose that $x\geq C$ implies $(P(x),\tau(P(x)))>P(t)$ . For a sufficiently large $k>C$ that we will choose later, pick
$a\equiv t(mod \ p_i^{a_i+1}) \forall i\leq m, \ \ a\equiv t(mod \ r_i^{b_i+1}),\ \ a\equiv w(mod \ \frac{p_{m+1}\dots p_k}{r_1\dots r_x})$ Where $p_k>P(w)>0$ . Let $a$ be the second smallest positive integer holding these modulo restrictions. This yields $a<2P(t).rad P(t)p_{m+1}\dots p_k$ .
$P(t)|P(a)$ and any prime divisor of $\frac{P(a)}{P(t)}$ is larger than $p_k$ . Notice that $a>p_k>C$ hence $(P(a),\tau(P(a)))>P(t)$ . Let $P(a)=p_1^{a_1}\dots p_m^{a_m}r_1^{b_1}\dots r_x^{b_x}p_{k+1}^{c_{k+1}}\dots p_l^{c_l}$ where $c_i$ are nonnegative. $k$ is sufficiently large such that $p_k>(a_1+1)\dots (b_x+1)$ hence $(p_i, (a_j+1)(b_j+1))=1$ for $i\geq k+1$ . Since $(x,yz)\leq z(x,y)$ we have
$\begin{align*} P(t)< (P(a),(\tau(P(a)) &= (p_1^{a_1}\dots r_x^{b_x}\dots p_l^{c_l},(a_1+1)\dots (b_x+1)\dots (c_l+1)) \\ &\leq p_1^{a_1}\dots p_m^{a_m}r_1^{b_1}\dots r_x^{b_x}(p_{k+1}^{c_{k+1}}\dots p_l^{c_l},(a_1+1)\dots (b_x+1)\dots (c_l+1)) \\ & =P(t) (p_{k+1}^{c_{k+1}}\dots p_l^{c_l},(c_{k+1}+1)\dots (c_l+1)) \end{align*}$ Thus, $(p_{k+1}^{c_{k+1}}\dots p_l^{c_l},(c_{k+1}+1)\dots (c_l+1))>1$ which implies $p_i|c_j+1$ for some $i,j\geq k+1$ .
$(2P(t)^2)^{d+1}.(p_k)^{(k-m)(d+1)}>(2P(t)^2p_{m+1}\dots p_k)^{d+1}>a^{d+1}>P(a)>P(t)p_{k+1}^{p_k}>p_k^{p_k}$ Since $(2P(t)^2)^{d+1}=\ell$ is a constant, this requires $\ell>(p_k)^{p_k-(k-m)(d+1)}$ or $p_k<(k-m)(d+1)$ however this is not true since primes have density zero as desired. $\blacksquare$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a