Fix a positive integer $a > 1$. Consider triples $(f(x), g(x), h(x))$ of polynomials with integer coefficients, such that 1. $f$ is a monic polynomial with $\deg f \ge 1$. 2. There exists a positive integer $N$ such that $g(x)>0$ for $x \ge N$ and for all positive integers $n \ge N$, we have $f(n) \mid a^{g(n)} + h(n)$. Find all such possible triples. Proposed by Mainak Ghosh and Rijul Saini
Problem
Source: India IMOTC Practice Test 2 Problem 2
Tags: Polynomials, number theory, algebra, polynomial
31.05.2024 09:24
07.06.2024 18:29
Nice problem,but standard idea anyway. Obviously the dominant coefficient of $g$ is positive. From Schur there exist infinitely many primes which divide $f(N),f(N+1),\dots $.Take one such huge prime $p$. Let $T$=deg $g$ and take $\alpha$ such that $p\mid f(\alpha)$ and take $n\equiv \alpha \pmod p$ and $n\equiv m \pmod {p-1}$(possible by CRT) where $m$ is integer arbitraly Then $p\mid f(n)$ and $a^{g(n)}\equiv a^{g(m)} \pmod p$ since $(p,a)=1 $.Thus we have: $p\mid a^{g(m)}+h(\alpha)$ so $a^{g(m)}$ is constant mod $p$ as $m$ varies through the integers. The key idea is to take $g(0),g(1),\dots g(T)$ and $p>>T$ We have that $g(0),g(1),\dots g(T)$ are congruent modulo $d$=the order of $a$ mod $p$.But if $g(i)\neq g(j)$ then $d$ is bounded and since $p\mid a^d-1$ we have $p$ is bounded contradiction ! So $g(0)=g(1)=\dots g(T)=c$ and so g is constant $c>0 $ Thus the problem becomes: $f(n)\mid a^c+h(n)$ and take arbitrary monic $f$ and $h=f(n)\cdot s(n)-a^c$ which works for arbitrary $s \in \mathbb{Z}[X]$
19.06.2024 22:35
It is known that $f(n)$ is divisible by infinitely many prime divisors. Take any, say $p$, big enough, and $p | f(x)$ Then $p | f(x+kp) | a^{g(x+kp)}+h(x+kp)$, but $h(x+kp) \equiv h(x)$ (mod $p$), so $a^{g(x+kp)} \equiv a^{g(x)}$. Because $a<p$, $g(x+kp)-g(x) \vdots d$, where $d=ord_p(a)<p$ Because $d$ and $p$ are coprime, $x+kp$ takes all residues mod $d$, and so $g(m+1) \equiv g(m)$ (mod $d$) for any $m$. But because $d$ can be arbitrarily large($d>log_a p$), $g(m+1)=g(m)$, and so $g$ is a constant Now $f(n)$ and $a^g(n)+h(n)$ are both polynomials with integer coefficients, it is known that then $f(n)r(n)=a^g(n)+h(n)$, and so $h(n)=f(n)r(n)-a^g(n)$, and thus our final answer is $(f(n),g,f(n)r(n)-a^g)$
27.06.2024 19:09
Nice probleme
09.08.2024 23:28
My solution is basically the same as the ones above.
22.09.2024 07:24
this same idea has come like trillion times before in stems , 2019 ind tst f(n) problem by anant mungdal and many more
11.12.2024 10:29
idkk wrote: this same idea has come like trillion times before in stems , 2019 ind tst f(n) problem by anant mungdal and many more I don't see how your idea is contributing much to this post. What is the aim of posting this? It certainly doesn't comment about difficulty, since there were plenty of people (me included) who hadn't solved it in contest. And of course ideas are bound to repeat; you can't just generate more ideas out of thin air. So please do enlighten us as to what the meaning and intention of this post is.
11.12.2024 15:56
Cool poly problem , idea sort of seen in some other problems but nice regardless. First from Schur theorem we have that there exists infinitely many primes with $p \mid f(n)$ for some $n$, so now we have that $p \mid a^{g(n+p\ell)}+h(n)$ therefore $g(n+p \ell) \equiv g(n) \pmod d$ where $\text{ord}_p(a)=d$, not clearly as $p \mid a^d-1$ we have that $a^d \ge p+1$ so $d \ge \log_a(p+1)$ which eventually grows as $p$ does, but since $d \mid p-1$ it happens that $\gcd(p,d)=1$ so if $d=1$ then just pick a prime large enough such that $p>a$ and then $d \ne 1$ so now we have that $p \ell$ make a complete residue system $\pmod d$ therefore $g(n)$ is constant $\pmod d$ but as we have seen we can eventually make $d$ as large as we want therefore $g(n)=c$ is a constant polynomial, and now from division algorithm we have that $h(n)=k(n) \cdot f(n)-a^c$ and cleaely any such triple works thus we are done .
16.12.2024 23:35
AshAuktober wrote: idkk wrote: this same idea has come like trillion times before in stems , 2019 ind tst f(n) problem by anant mungdal and many more I don't see how your idea is contributing much to this post. What is the aim of posting this? It certainly doesn't comment about difficulty, since there were plenty of people (me included) who hadn't solved it in contest. And of course ideas are bound to repeat; you can't just generate more ideas out of thin air. So please do enlighten us as to what the meaning and intention of this post is. I think what he was trying to say this is that this is a pretty standard idea and it is very true. The first time I tried it, I could relate it firstly to IMO Shortlist 2011/N6, which is basically exactly like this (my proofs are almost isomorphic for both). And I understand what you are saying is like say ideas might be repeated over and over again in different problems but sometimes problems like this might frustrate some candidates because people who have done that Shortlist problem (which is very popular imo) have a major major advantage. Obviously the proposer did not know about this and it is probably just a coincidence. But alas, atleast it was just a practice test.
16.12.2024 23:39
Since $\deg f \geq 1$, by Schur's Theorem; we get there exists infinitely many primes $p$ such that $p \mid f(x)$ for some $x \in \mathbb{N}$. Claim: $g$ is constant. Proof: Say $p \geq a$ is one such prime; and say $p \mid f(n_0)$ such that $n_0 \geq N$; and so \[p \mid f(n_0+kp) \mid a^{g(n_0+kp)}+h(n_0+kp) \iff p \mid a^{g(n_0+k)}+h(n_0)\]And now we basically get that \[g(n) \equiv g(m) \pmod {\text{ord}_p(a)}\]for all $n$, $m \in \mathbb{N}$; and see that due to size reasons we get that $\text{ord}_p(a)$ can be arbitrarily large which means $g$ is constant. $\square$ Say $g(x) \equiv C>0$; and we get that $f(n) \mid a^C+h(n)$ for large $n$ which means the divisibilty holds for them as polynomials. Hence the final solution set is just \[\boxed{\left(f(X),g(X),h(X)\right)=\left(F(X), \text{ }C, \text{ }F(X)T(X)-a^C \right)} \text{ (where $F,T \in \mathbb{Z}[X]$, $C \in \mathbb{N}$)}\]
30.12.2024 06:54
AshAuktober wrote: idkk wrote: this same idea has come like trillion times before in stems , 2019 ind tst f(n) problem by anant mungdal and many more I don't see how your idea is contributing much to this post. What is the aim of posting this? It certainly doesn't comment about difficulty, since there were plenty of people (me included) who hadn't solved it in contest. And of course ideas are bound to repeat; you can't just generate more ideas out of thin air. So please do enlighten us as to what the meaning and intention of this post is. As @2above explained the problem is unreasonably classical , and yes maths is about creating new things maybe in a olympiad setting not completely new things but shouldnt be like this where u can no brainer copy paste everything
19.01.2025 07:28
@above no offence but I think you are being overdramatic by saying copy-pasting everything. The problem is actually nice imo.