IMO Shortlist 2013, Number Theory #3

The post below has been deleted. Click to close.

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

127 posts

#1 h Jul 10, 2014, 6:12 AM • 14 Y

Y by mathuz, Davi-8191, tenplusten, myh2910, jhu08, TFIRSTMGMEDALIST, Infinityfun, Adventure10, Mango247, NicoN9, and 4 other users

Prove that there exist infinitely many positive integers $n$ such that the largest prime divisor of $n^4 + n^2 + 1$ is equal to the largest prime divisor of $(n+1)^4 + (n+1)^2 +1$ .

Z K Y

The post below has been deleted. Click to close.

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

mnbvmar

7 posts

mnbvmar

#2 h Jul 10, 2014, 10:24 AM • 7 Y

Y by bzh, blooker, Adventure10, Mango247, and 3 other users

my solution

Z K Y

The post below has been deleted. Click to close.

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

YESMAths

829 posts

YESMAths

#3 h Jul 10, 2014, 4:28 PM • 5 Y

Y by MNJ2357, A_Math_Lover, Adventure10, and 2 other users

I just wonder, but this problem had been posted earlier, without any mention of ISL 2013, but soon was deleted.
That time I wondered why it was deleted, as I had posted my solution there, but now I know why it might have been deleted!

[mod: indeed!]

Z K Y

The post below has been deleted. Click to close.

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

randomusername

1059 posts

randomusername

#4 h Jul 10, 2014, 4:58 PM • 6 Y

Y by adityaguharoy, Adventure10, Mango247, rafayaashary1, and 2 other users

Different solution

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6862 posts

v_Enhance

#5 h Jul 10, 2014, 5:43 PM • 28 Y

Y by mathuz, ZODIACORACLE, SidVicious, tenplusten, yayups, A_Math_Lover, meet18, myh2910, ks_789, TETris5, Jc426, TFIRSTMGMEDALIST, math31415926535, W.R.O.N.G, HamstPan38825, Mathlover_1, Goldenpigkhtn, Adventure10, Mango247, Bataw, Stuffybear, bin_sherlo, NicoN9, and 5 other users

Define $f(n) = n^2+n+1$ . Then $n^4 + n^2 + 1 = (n^2+n+1)(n^2-n+1) = f(n)f(n-1).$ So it suffices to show that $\textstyle\max_p f(n)$ is at least the larger of $\textstyle\max_p f(n-1)$ and $\textstyle\max_p f(n+1)$ infinitely often, where $\textstyle\max_p(n)$ is the largest prime dividing $n$ .

If not, either $\textstyle\max_p f(1), \textstyle\max_p f(2), \dots$ is eventually strictly increasing or strictly decreasing. Since the latter is impossible for integer sequences, we only need to show this sequence cannot decrease monotonically. But $f(n^2) = f(n)f(n-1)$ , so $\textstyle\max_p f(n)^2$ is at most $\textstyle\max \left( \textstyle\max_p f(n), \textstyle\max_p f(n-1) \right)$ , so the sequence cannot be strictly increasing at any time.

This is similar to a Russian 2010 problem, which asked to show infinitely many distinct $a$ , $b$ , $c$ satisfied $\textstyle\max_p (a^2+1) = \textstyle\max_p (b^2+1) = \textstyle\max_p (c^2+1)$ .

Z K Y

The post below has been deleted. Click to close.

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

Naysh

2134 posts

Naysh

#6 h Jul 10, 2014, 6:04 PM • 3 Y

Y by Adventure10 and 2 other users

Solution

Z K Y

The post below has been deleted. Click to close.

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

mathuz

1510 posts

mathuz

#7 h Jul 10, 2014, 10:40 PM • 4 Y

Y by Adventure10, Mango247, and 2 other users

I think it's very nice problem, but some easier.
You can use by: $n^4+n^2+1=(n^2+n+1)((n-1)^2+(n-1)+1)$ let $a_n=n^2+n+1$ and $a_{n^2}=a_{n}a_{n-1}$ . It means $max_p(a_{n^2})\le max(max_p(a_n),max_p(a_{n-1})) .$

Z K Y

The post below has been deleted. Click to close.

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

leminscate

109 posts

leminscate

#8 h Jul 11, 2014, 11:07 AM • 4 Y

Y by MathbugAOPS, Adventure10, and 2 other users

Quite a nice problem. Let $f(n)=n^2+n+1$ , and $g(n)$ be the greatest prime dividing $f(n)$ . The key observation is that $f(n^2)=n^4+n^2+1=f(n)f(n-1)$ .
So we are done if we can show that there are infinitely many positive integers $n$ such that $g(n) < g(n+1) > g(n+2)$ . Assume this is not the case. Then after some stage the sequence $g(1), g(2), ...$ must be strictly increasing or decreasing (note consecutive $g(i)$ can never be equal as $(i^2+i+1, (i+1)^2+(i+1)+1)=1$ for positive integers $i$ ). If eventually it is strictly decreasing, we have a contradiction as primes are discrete with a lower bound. But it cannot eventually be always strictly increasing since $f(n^2)=f(n)f(n-1) \implies g(n^2)=g(n)$ or $g(n-1)$ for all n.

Z K Y

The post below has been deleted. Click to close.

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

JuanOrtiz

366 posts

JuanOrtiz

#9 h Feb 8, 2015, 2:13 AM • 2 Y

Y by Adventure10, Mango247

After finding the factorization this problem is relatively easy, one must simply consider the function $g$ that takes the greatest prime divisor of $n^2+n+1$ . However, finding the factorization is not so easy! :/ Took me some time...

Z K Y

The post below has been deleted. Click to close.

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

DrMath

2130 posts

DrMath

#10 h Sep 23, 2015, 1:30 AM • 2 Y

Y by Adventure10, Mango247

Let $f(n)$ be the greatest prime factor of $n^2+n+1$ . Then note $f(n)\neq f(n+1)$ as they are relatively prime. Moreover, we want to show that $f(n)>f(n-1), f(n+1)$ for infinitely many $n$ . But this is equivalent to showing that $f$ is not monotone strictly increasing or decreasing, which is easy to show since $\text{max}(f(n-1), f(n))=f(n^2)$ , so we cannot be infinitely increasing.

Z K Y

The post below has been deleted. Click to close.

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

AMN300

563 posts

AMN300

#11 h Jul 14, 2016, 12:11 AM • 2 Y

Y by Adventure10, Mango247

Beautiful problem!

Solution

Z K Y

The post below has been deleted. Click to close.

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

test20

988 posts

test20

#12 h Oct 3, 2017, 3:10 PM • 2 Y

Y by Adventure10, Mango247

This problem badly overlaps with ARO 2011 11-7:
https://artofproblemsolving.com/community/c6h404321_aro_2011_117

(Note in particular the solution by "yugrey" in post #10.)

Z K Y

The post below has been deleted. Click to close.

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

mastermind.hk16

143 posts

mastermind.hk16

#13 h Dec 18, 2018, 2:04 PM • 2 Y

Y by Adventure10, Mango247

Solution

This post has been edited 1 time. Last edited by mastermind.hk16, Jul 29, 2021, 5:02 AM

Z K Y

The post below has been deleted. Click to close.

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

pad

1671 posts

pad

#14 h Aug 5, 2019, 7:08 PM • 3 Y

Y by Adventure10, Mango247, nbsplv

Let $f(n)$ be the greatest prime factor of $n$ . Since
$\begin{align*} n^4+n^2+1 &=(n^2+n+1)(n^2-n+1)\\ (n+1)^4+(n+1)^2+1 &= (n^2+n+1)(n^2+3n+3) \end{align*}$ we want to show that there are infinitely many $n$ such that $f(n^2+n+1) > f(n^2-n+1)$ and $f(n^2+n+1)>f(n^2+3n+3)$ . Let $g(n)=n^2+n+1$ . We want to show there are infinitely many $n$ such that $f(g(n)) > f(g(n-1)), f(g(n+1))$ . This is only impossible if the sequence $\{ f(g(n)) \}$ becomes monotonic starting at some point. Note that we cannot have $f(g(n)) = f(g(n+1))$ since $\text{gcd}(g(n),g(n+1))=1$ by Euclidean Algorithm. It cannot be monotonically decreasing, so it must be increasing.

Now, note that $g(n)g(n-1)=g(n^2)$ . This means $f(g(n)g(n-1)) = f(g(n^2))$ . But
$f(g(n)g(n-1)) = \max(f(g(n)), f(g(n-1))),$ which is a contradiction.

Remarks

This post has been edited 1 time. Last edited by pad, Aug 5, 2019, 7:24 PM

Z K Y

The post below has been deleted. Click to close.

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

Edgylength

2 posts

Edgylength

#15 h Aug 5, 2019, 11:18 PM • 1 Y

Y by Adventure10

Well, I guess it was just too simply easy

Z K Y

The post below has been deleted. Click to close.

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

asdf334

7586 posts

asdf334

#35 h Nov 23, 2022, 5:12 PM

Y by

Let $f(x)$ be the largest prime divisor of $x^2+x+1$ . Since
$n^4+n^2+1=((n-1)^2+(n-1)+1)(n^2+n+1)$ $(n+1)^4+(n+1)^2+1=(n^2+n+1)((n+1)^2+(n+1)+1)$ we just want to find values of $n$ such that
$f(n)\ge f(n-1),f(n+1).$ Therefore, it is enough to show that $f$ cannot eventually only increase. Since $f(n^2)=\text{max}(f(n-1),f(n))$ this is true, and we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

cj13609517288

1868 posts

cj13609517288

#36 h Apr 14, 2023, 1:28 PM

Y by

Let $f(x)=x^2+x+1$ and $g(x)$ be the largest prime divisor of $x$ . Note that $f(x-1)f(x)=f(x^2)$ and $g(xy)=\text{max}(g(x),g(y))$ . Then we want to prove that there exist infinitely many positive integers $n$ such that $g(f(n^2))=g(f((n+1))^2)$

Claim. For any positive integer $N$ , there exists a positive integer $n>N$ such that $g(f(n))=g(f(n^2))$ .
Proof. We will prove that there exists an increasing sequence of such $n$ . Firstly, manually check that
$g(f(36))=\text{max}(g(f(5)),g(f(6)))=g(f(6)).$ Now note that there must be some positive integer $6\le k < 36$ such that $g(f(k))\le g(f(k+1))$ . Then
$g(f((k+1)^2))=\text{max}(g(f(k)),g(f(k+1)))=g(f(k+1)).\;\blacksquare$
Claim. There exists infinitely many positive integers $n\ge 2$ such that $g(f(n))\ge g(f(n+1))$ and $g(f(n))\ge g(f(n-1))$ .
Proof. Suppose not. Then $g(f(x))$ is strictly increasing or strictly decreasing past one point, which is impossible due to the previous claim.

Now simply note that such $n$ satisfy the given constraint. QED.

Z K Y

The post below has been deleted. Click to close.

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

starchan

1601 posts

starchan

#37 h Jun 2, 2023, 8:05 AM

Y by

nice
solution

Z K Y

The post below has been deleted. Click to close.

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

pikapika007

294 posts

pikapika007

#38 h Jun 24, 2023, 2:13 AM

Y by

Let $f(x) = x^2 + x + 1$ and $P(x)$ be the largest prime divisor of $x$ . Then we wish to show that
$P(f(n^2)) = P(f((n+1)^2).$ However, $f(x^2) = f(x)f(x-1)$ , so this is equivalent to
$\max(P(f(n), P(f(n-1)) = \max(P(f(n), P(f(n+1)).$ We will show that there exist infinitely many $n$ so that $P(f(n)) \ge \max(P(f(n-1)), P(f(n+1))$ ; this clearly finishes. Note that this is equivalent to showing that the sequence $a_n = P(f(n))$ cannot be strictly increasing; however, since $a_{n^2} = \max(a_n, a_{n-1})$ this is impossible and we are done. $\square$

This post has been edited 1 time. Last edited by pikapika007, Jun 24, 2023, 2:15 AM

Z K Y

The post below has been deleted. Click to close.

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

john0512

4170 posts

john0512

#39 h Aug 1, 2023, 9:39 PM

Y by

Let $a_n$ denote the largest prime factor of $n^2+n+1$ . The largest prime factor of $n^4+n^2+1$ is just $\max(a_n,a_{n-1})$ because $n^4+n^2+1=(n^2+n+1)(n^2-n+1).$

Claim 1: There are infinitely many $n$ such that $a_{n+1}\geq a_n$ . Note that given any prime $p$ , there is a value of $n\pmod p$ such that $n^2+n+1$ is not divisible by $p$ . Thus, given any finite list of primes, by Chinese Remainder Theorem we can pick $n$ to avoid all of them. Thus, the sequence $a_i$ is unbounded, which clearly shows the claim.

Claim 2: There are infinitely many $n$ such that $a_{n+1}\leq a_n$ . Suppose for the sake of contradiction that after some point, the sequence is strictly increasing. Then, after a certain point, the largest prime divisor keeps increasing. The slowest that the "largest prime divisor" sequence is allowed to increase is by going to the next prime, and counting primes grows at a faster than linear rate by PNT, so for sufficiently large $n$ , all $n^2+n+1$ has a prime factor greater than say $1434n$ . However, when $n$ is a perfect square, we have that $n^2+n+1=(n+\sqrt{n}+1)(n-\sqrt{n}+1).$ Both of these factors are less than $1434n$ , hence contradiction as we know that there is a prime factor at least $1434n$ for all sufficiently large $n$ .

Thus, there are infinitely many nonincreasing steps, and infinitely many nondecreasing steps. Thus, there must be infinitely many transitions between the two, and thus infinitely many turns where a nondecreasing step is followed by a nonincreasing step. Thus, there are infinitely many runs of 3 numbers such that the middle number is equal to the max of the 3 numbers, hence done as if $a_n\geq a_{n-1}$ and $a_n\geq a_{n+1}$ , then $\max(a_{n-1},a_n)=\max(a_n,a_{n+1}).$

This post has been edited 2 times. Last edited by john0512, Sep 8, 2023, 4:07 PM

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8855 posts

HamstPan38825

#40 h Dec 31, 2023, 1:34 AM

Y by

Talk about being nonstandard!

Let $f(n) = n^2+n+1$ . Notice that if we can find infinitely many $n$ such that $f(n-1), f(n+1) \leq f(n)$ , then all these $n$ will satisfy the problem statement. It just suffices to show that there cannot exist an $N$ such that $f(n)$ is strictly increasing for all $n \geq N$ .

To see this, construct a sequence $\{p_i\}$ where $p_0 = f(N)$ and $p_i > p_{i-1} = f\left(N +\prod_{j=1}^{i-1} p_i\right)$ . It follows that for every $m$ , $p_0p_1 \cdots p_m \mid f(N + p_0p_1 \cdots p_{m-1}) = (p_0p_1 \cdots p_{m-1})^2 + (2N+1)(p_0p_1 \cdots p_{m-1}) + N^2+N+1.$ By picking $m$ large enough we have $p_0p_1 \cdots p_{m-1} > N^2+N+1$ , hence contradiction.

It follows that $f(n)$ switches from increasing to decreasing and vice versa infinitely many times. Picking these maximum critical points $n$ yields the desired solutions.

This post has been edited 4 times. Last edited by HamstPan38825, Dec 31, 2023, 1:42 AM

Z K Y

The post below has been deleted. Click to close.

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

math_comb01

659 posts

math_comb01

#41 h Jan 5, 2024, 10:11 PM

Y by

Very intuitive NT!
Let $f(n)=n^2+n+1$ and let $F(x)$ denote the largest prime factor of $x$ . Note that $F(f(n))$ is clearly unbounded. Also it cannot be increasing or decreasing due to obvious reasons. Therefore it must have infinitely many "peaks". Hence we're done.

Z K Y

The post below has been deleted. Click to close.

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

alsk

28 posts

alsk

#42 h Mar 9, 2024, 9:40 PM

Y by

Notice that $n^4+n^2+1 = (n^2+n+1)(n^2-n+1)$ and $(n+1)^4+(n+1)^2+1 = (n^2+2n+3)(n^2+n+1)$ . Define $f(x)$ as the largest prime divisor of $x^2+x+1$ . Then, we have that $f(x^2) = f(x)f(x-1)$ .

We would like to show there exist infinitely many $n$ such that $f(n^2) = f((n+1)^2)$ . Since $f(n^2) = \max(f(n), f(n-1))$ , this is equivalent to showing that $f(x)$ has infinitely many ``local maxima.''

FTSoC assume that $f(x)$ has finitely many ``local maxima.'' Then, this implies that for big enough $N$ , $f(x)$ is either strictly increasing or strictly decreasing for $x > N$ . Since $f(x)$ always outputs a positive number, it is impossible for it to be always strictly decreasing, so we would like to show that $f$ cannot be strictly increasing forever.

This is easy to show since $f(n^2) = \max(f(n), f(n-1))$ and $n^2 > n$ , so clearly it cannot be strictly increasing, done.

Z K Y

The post below has been deleted. Click to close.

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

shendrew7

792 posts

shendrew7

#43 h Jun 11, 2024, 1:58 AM

Y by

Define the function $f(x)=x^2+x+1$ , and notice that our desired expressions factor as $f(n-1) \cdot f(n)$ and $f(n) \cdot f(n-1)$ .

It remains to show that there exists infinitely many $n$ for which the largest prime factor of $f(n)$ is greater than or equal to the largest prime factor of $f(n-1)$ or $f(n)$ . In other words, the largest prime factor of $f(n)$ is neither always increasing or decreasing for large $n$ .

The decreasing claim is trivial. For the increasing portion, assume FTSOC there exists some $m$ for which the largest prime factors of each term in $f(m), f(m+1), f(m+2), \ldots$ is always strictly increasing. However, we simply note that
$f((m+1)^2) = f(m) \cdot f(m+1),$
so the greatest prime factor of $f((m+1)^2)$ is the greatest prime factor of $f(m+1)$ , contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

mathematical717

34 posts

mathematical717

#44 h Nov 13, 2024, 1:44 PM

Y by

Time For Another Unnecessary Long And Motivated Solution

Posting after a long while.....

Let $W(n)$ denote the largest prime factor of some $n$ and $f(n)=n^2+n+1$ . We basically want that $W(n^4+n^2+1)=W((n+1)^4+(n+1)^2+1)$ however notice the factorizations, $n^4+n^2+1=f(n)f(n-1) \ \land \ (n+1)^4+(n+1)^2+1=f(n)f(n+1)$ which gets us to $max\{W(f(n)),W(f(n-1))\}=max\{W(f(n)),W(f(n+1))\}$ although, there are a few cases to deal with. We check a few $W(f(n))$ points by hand and want that $max$ on both points are $W(f(n))$ as then we are automatically done. We just want, $W(f(n)) \ge max\{W(f(n+1)),W(f(n-1))\}$ to hold and call all such pairs as "good tuples".
Now, first assume that there are only finitely many points such that $W(f(n)) \ge W(f(n-1))$ then, obviously $\exists \ C$ such that $\forall x \ge C$ we have, $W(f(x)) \le W(f(x-1))$ as in this function becomes decreasing after a finite point. However this means that the primes dividing $n^2+n+1$ are bounded above. We shall prove the opposite. Basically $\exists$ arbitrarily large $n$ divisble by arbitrarily large primes $p$ . Consider a large prime of the form $1 \ (mod \ 3)$ by dirichlet's theorem now by a bit of trivial quadratic residue check, one realizes that $(-3)$ is a quadratic residue and for any such $p$ we have some $\sqrt{-3} \equiv d \ (mod \ p)$ . Now we have that, $n^2+n+1 \equiv 0 \ (mod \ p) \iff (2n+1)^2 \equiv (-3) \ (mod \ p) \iff (2n+1) \equiv d \ (mod \ p) \iff n \equiv \frac{d-1}{2} \ (mod \ p)$ so arbitrarily large $n$ exist. Also modular inverse of $2$ exists due to $(2,p)=1$ .
Thus we have infinitely many points where this sign flip occurs (or perhaps not a flip but this thing entirely as a chain), in any case if infinitely many such points also had $W(f(n)) \ge W(f(n+1))$ then we would be done. Hence assuming the opposite we have only finite such points where our original condition holds. So there is some finite constant $G'$ above which whenever there is a $W(f(n)) \ge W(f(n-1)) \implies W(f(n))<W(f(n+1))$ and hence pick the first such point and on the next point if $W(f(n+2)) \le W(f(n+1))$ then this pair is a "good tuple" but we have already assumed that we have exceeded the finite set (Euclid's Infinitude Style Argument) and thus we must have a strict increasing $W$ after that point. We shall prove this is not the case as arbitrary points have, what we called "sign-flips" earlier.

Herein the idea comes after a while of playing around with say $n^2+n+1=p^a, k^2, k^{2a}$ and so on. All these forms have some conclusion which is not something we like. Generalizing to a general power seems too wanky to work with, but testing $n=1,2,\dots,10$ turns out we can wish for $a^2+a+1 \mid b^2+b+1$ and thus, $a^2+a+1 \mid b^2+b-a^2-a \iff a^2+a+1 \mid (b-a)(b+a+1)$ again by a bit of Evan's "Blackjack Analogy" we have that, $a^2+a+1=b-a \implies b=(a+1)^2$ when we suddenly realize $f((n+1)^2)=f(n)f(n+1)$ and thus, $W(f(n+1)^2))=max\{W(f(n)),W(f(n+1))\}$ when we let $n>G'$ arbitrary so that $f(n)<f(n+1)$ and hence $W(f(n+1)^2)=W(f(n+1))$ however, $(n+1)^2>(n+1)$ and thus $W(f((n+1)^2))>W(f(n+1))$ due to condition which creates an obvious contradiction!

Therefore we are done! Q.E.D :showoff:

Remark : I might have missed out on an equality somewhere, but I'm pretty sure it can be easily corrected if so. Also, kindly spot out major errors (if any). Secondly I know there are a lot of optimizations say for example, the problem statement itself points out $f((n+1)^2)$ observation but whatever. :rotfl:

This post has been edited 2 times. Last edited by mathematical717, Nov 13, 2024, 1:47 PM

Z K Y

The post below has been deleted. Click to close.

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

Krave37

46 posts

Krave37

#45 h Dec 18, 2024, 5:46 AM

Y by

Factorizing $n^4+n^2+1$ and $(n+1)^4+(n+1)^2+1$ gives $(n^2+n+1)(n^2-n+1)$ and $(n^2+n+1)(n^2+3n+3)$ respectively.
Now, if we show that the largest prime diving both the equation comes from $(n^2+n+1)$ infinitely many times, we are done.
Claim: Above statement

Proof: Assume this happens finitely, then we will get a chain of increasing numbers having their largest prime coming from $(n^2+3n+3)$ and the other factor. Take the successive number, we see they share a factor Eg; take $n+2$ , we see that it factorizes to $(n^2+3n+3)(n^2+5n+7)$ , the larger polynomial becomes the smaller one. So, if after some $n$ , the largest prime always comes from the larger polynomial, this means that the largest prime will always increase in $n^2+n+1$ form (in $n^2+3n+3$ is just $n=n+1$ ). This is obviously false as the largest prime of $n=n^2$ (n^4+n^2+1) equals that of $n^2+n+1$ , so all the numbers in between $n$ and $n^2$ will either have equal or smaller largest prime than $n^2+n+1$ , this solves our problem by contradiction. As there should be some $n$ for which the largest prime belongs to the smaller polynomial, in a chain of numbers where it belongs to the larger one. So, we can find two consecutive numbers.

For the largest prime coming from the smaller polynomial always, we can show that this means the largest prime decreases with $n$ but this can not happen due to the same above argument.

This post has been edited 1 time. Last edited by Krave37, Dec 18, 2024, 5:48 AM

Z K Y

The post below has been deleted. Click to close.

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

sansgankrsngupta

127 posts

sansgankrsngupta

#46 h Feb 16, 2025, 5:56 AM

Y by

OG! Same as v_enhance

Z K Y

The post below has been deleted. Click to close.

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

OronSH

1724 posts

OronSH

#47 h Mar 2, 2025, 10:51 PM

Y by

Pick $p\equiv 1\pmod 3$ and let $n\ne 1$ satisfy $p\mid n^2+n+1$ . Then the two possible values of $n$ sum to $p-1$ so one of them is $\le\tfrac{p-1}2$ . Let this be $n$ . Then choose $m$ minimized such that $m^2>n$ . Then $(m-2)^2<n<m^2$ . Fron $n\le\tfrac{p-1}2$ we get $m^2<c(p-1)$ for $\tfrac12<c<1$ and $p$ large enough. Now if $f(x)$ is the largest prime factor of $x$ then from the identity $x^4+x^2+1=(x^2+x+1)(x^2-x+1)$ we have $f((m-2)^4+(m-2)^2+1)<m^2-3m+3<m^2<p,f(m^4+m^2+1)<m^2+m+1<cp+\sqrt{c(p-1)}<p$ for large $p$ and $f(n)>p$ . Thus the values of $f$ from $(m-2)^2$ to $m^2$ have some maximum $k\ne(m-2)^2,m^2$ . Then $f(k^4+k^2+1)=\max(f((k-1)^2+(k-1)+1),f(k^2+k+1))=f(k^2+k+1)=\max(f((k+1)^2+(k+1)+1),f(k^2+k+1))=f((k+1)^4+(k+1)^2+1)$ , so for arbitrarily large $p$ we generate arbitrarily many values of $k$ as desired.

This post has been edited 1 time. Last edited by OronSH, Mar 2, 2025, 10:52 PM

Z K Y

The post below has been deleted. Click to close.

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

kotmhn

56 posts

kotmhn

#48 h Mar 13, 2025, 7:26 PM

Y by

A post after ages here it is.

Let $f(n) = n^2+n+1$ and $P(N)$ be the largest divisor of $N$ .
Obs that $f(n^2) = f(n-1)f(n+1)$ and hence $P(f(n^2)) = \max\{P(f(n-1)),P(f(n+1))\}$ .
Now the condition in the question turns out to be equivalent to showing that $P$ never becomes monotonous.
For this we do the following:
Case 1: it becomes constant after a certain $N$ .
This cannot happen, as it would imply that the set of prime divisors of $f(n)$ is bounded. To see other wise obs that $-3$ is a $QR$ when $p\equiv 1 \pmod{12}$ which, by dirichlet, shows that infinite primes divide some value of $f$ .

Case 2: It becomes strictly increasing after a certain $N-2$ .
Well,
$P(f(N+1))< P(f(N+2))<\cdots < P(f(N^2)) = \max\{P(f(N-1)),P(f(N+1))\} = P(f(N+1))$ a contradiction.

And voila! 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.

hgomamogh

34 posts

hgomamogh

#49 h Mar 17, 2025, 5:56 PM • 1 Y

Y by OronSH

For $n > 0$ , let $f(n) = n^2 + n + 1$ , and let $g(n)$ be the maximum prime divisor of $f(n)$ . Observe that $g(n + 1)$ can clearly not equal $g(n)$ .

Lemma 1: There exist infinitely many positive integers $n$ such that $g(n + 1) > g(n)$ .

Assume the contrary. Then, for some $N$ , when $n > N$ , $g(n + 1)$ is always less than $g(n)$ , which is absurd because this sequence obviously reaches $0$ .

Lemma 2: There exist infinitely many positive integers $n$ such that $g(n + 1) < g(n)$ .

We assume the contrary again, noting that there exists some large positive integer $N$ for which $g(n + 1) > g(n)$ whenever $n \geq N$ . However, we have an easy contradiction here because $g((n+1)^2)$ is either $g(n)$ or $g(n + 1)$ because of the identity $f(n^2) = f(n)f(n - 1)$ .

Lemma 3: There exist infinitely many positive integers $n$ such that $g(n - 1) < g(n)$ and $g(n) > g(n + 1)$ .

This follows easily from Lemmas 1 and 2.

We are now ready to tackle the main problem. Take any integer $n$ satisfying Lemma 3, and observe that $f(n^2) = n^4 + n^2 + 1 = (n^2 + n + 1)(n^2 - n + 1) = f(n)f(n - 1)$ and hence $g(n^2) = \max(g(n), g(n - 1))$ . Similarly, $g((n + 1)^2) = \max(g(n), g(n + 1))$ . By the statement of Lemma 3, we conclude that $g(n^2) = g(n) = g((n + 1)^2)$ , and we are done.

Z K Y