Let $F$ be a subset of the set of positive integers with at least two elements and $P(x)$ be a polynomial with integer coefficients such that for any two distinct elements of $F$ like $a$ and $b$, the following two conditions hold $a+b \in F$, and $\gcd(P(a),P(b))=1$. Prove that $P(x)$ is a constant polynomial.
Problem
Source: Iran MO 3rd round 2016 mid-terms - Number Theory P1
Tags: number theory, algebra, polynomial, Iran
06.09.2016 19:23
06.09.2016 19:24
rafayaashary1 wrote:
Yes, just that simple
07.09.2016 22:01
You don't even need Bezout's Lemma. (It's still cool to do it with Bezout, though!) Consider this. By (i), $k(a+b)$ for all $k \in \mathbb{Z}_{>0}$ is in $F$. Assume $P(x)$ wasn't constant, then \[ P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0 \]with $n \geq 1$ and $a_n \neq 0$. Then for a sufficiently large $h \in \mathbb{Z}_{>0}$, we have $|P(h(a+b))| > 1$, thus there is a prime $p$, such that $p \mid P(h(a+b))$. But \[ P((p+1)h(a+b)) = a_n ((p+1)h(a+b))^n+\dots+a_1((p+1)h(a+b)) +a_0 \equiv a_n (h(a+b))^n + \dots+a_1 h(a+b)+a_0 = P(h(a+b)) \equiv 0 \pmod p. \]Basically, what we have up there is just $P((p+1)h(a+b)) \equiv P(h(a+b)) \pmod p$. So therefore $\gcd(P(h(a+b)),P((p+1)h(a+b))) \geq p > 1$, contradiction. So $P(x)=a_0$ and thus in specific $P(x) = \pm 1$. $\hfill \blacksquare$
01.01.2017 18:55
rafayaashary1 wrote:
Can you explain this theorem or attack article?)
01.01.2017 19:26
@above It's Chicken McNugget Theorem
24.12.2017 21:29
Also you could let P(0) = c, and then work your way up by getting elements in F of the form ck(a+b), for all positive integers k. It follows that c divides all P(kc(a+b)). But the second rule says that c = $\pm$ 1. Then you get that P(x) = $\pm$ 1 for an infinite number of X in F, so P(X) must be constant at any one of those two values.
26.07.2018 09:00
lemma: $a-b|p(a)-p(b)$ for $a$ if $p(a)$ has any prime divisor $q$ then $q$ $|$ $p(a)$ $\implies$ $\gcd(P(a),P(a+qb))=q$ according to the lemma is which a contradiction so $p(a)=+1$ or $-1$
26.07.2018 10:15
rafayaashary1 wrote: From definition, $a,b\in F\implies\alpha\cdot a+\beta\cdot b\in F\text{ for any }\alpha ,\beta\in\mathbb Z^{+}$ But it is true by a well-known theorem that any $c\geq ab-a-b+1$ can be written as $\alpha\cdot a+\beta\cdot b\text{ with }\alpha ,\beta\in\mathbb Z^{+}$ I think this statement wrong, because Chicken McNugget Theorem holds for coprime numbers $a$ and $b$ (see link above).
26.07.2018 16:33
Huh, you're right. Fortunately the 'fix' is easy
22.05.2021 21:00
,every $ak$+$bs$ are in $F$ just take if for prime $Q$, $Q$ divide p(a) just chosse a and a+Q(a+b)
22.05.2021 21:04
and i forgot to add that you need to use this theorem that if gcd (a,b)=1 there are x and y that ax+by=dk for k>M
01.09.2021 23:48
bgn wrote: Let $F$ be a subset of the set of positive integers with at least two elements and $P(x)$ be a polynomial with integer coefficients such that for any two distinct elements of $F$ like $a$ and $b$, the following two conditions hold $a+b \in F$, and $\gcd(P(a),P(b))=1$. Prove that $P(x)$ is a constant polynomial. $ax+by$ is an element of $F$ from all positive integers. Suppose that $P$ is not constant. This means that there exists$p$ prime divisor of $P(ax+by)$(from some $x,y$) then $p$ also divesi $P(ax+by+p(a+b))$ contradiction.
28.05.2022 18:43
Assume $P$ is non constant, by Schur we can pick a large prime $q > \max\{a,b\}$ such that $q \mid P(x)$ for some $x$. The first condition of the problem says that any number of the form $ma + nb \in F$ for $m,n \in \mathbb{Z}^+$, now fixing $m$ with $m_1 \equiv m_2$ and ($m_1 \neq m_2$) we pick $n_1 \neq n_2$ such that $$n_1 \equiv n_2 \equiv n \equiv (x-ma)\cdot b^{-1} \pmod q \iff ma+nb \equiv x \pmod q$$meaning $q \mid P(m_1a+n_1b)$ and $q \mid P(m_2a + n_2b)$ which is a contradiction.
03.12.2022 17:41
Assume otherwise that $P$ is not constant. We divide the proof into three parts. Claim: $a,b,ma+nb\in F$ where $m,n$ are any positive integers. Proof. WLOG $m\leq n$. First, note that $a+b\in F$. Thus, $2(a+b)=((a+b)+(a))+(b)\in F$. Now, easy induction gives $m(a+b)\in F$ where $m$ is any positive integers. Then $ma+(m+1)b=m(a+b)+b\in F$. Do this repeatedly until we get $ma+nb\in F$. Let $\gcd(a,b)=d,a=dx,b=dy$. By Chicken McNugget's Theorem, any number greater than $xy-x-y$ can be expressed as $mx+ny$ where $m,n\geq 0$. But $(m+1)x+(n+1)y$ has $m+1,n+1\geq 1$. So any number greater than $xy$ can be expressed as $mx+ny$ where $m,n\geq 1$. Hence, all multiples of $d$ greater than $dxy$ are elements of $F$. Suppose that $kd,(k+1)d,(k+2)d, \dots \in F$. Obviously, there must be at least one number $td$ among them such that $P(td)\neq 1$; otherwise, $P$ will be constant. Let $p$ be a prime factor of $P(td)$. Recalling the integers polynomial property, we have $$(t+p)d-td\mid P((t+p)d)-P(td)\implies p\mid P((t+p)d)$$which is a contradiction because $\gcd(P(td),P((t+p)d)\geq p>1$.
03.12.2022 17:48
If $a, b \in F$, then $a+b \in F$, but then also $b + (a+b) \in F$. So in general, $a + kb \in F$. Now, suppose for $a$, we have $q|P(a)$. Now, well known lemma tells us that for polynomials, we have $x-y|P(x) - P(y)$. If we substitute $x = a+qb$ and $y = a$, we get $qb|P(a+qb) - P(a)$, and as $q|P(a)$, we have $q|P(a+qb)$, so gcd$(P(a),P(a+qb)) = q \ge 1$. Therefore, $P \equiv \pm 1$.
12.10.2024 02:22
Note for any positive integers $m,n$, we have $m \cdot a + n \cdot b \in F$, where $a,b$ are two distinct elements in $F$. Now, by Schur, there exists a prime $p$ that divides $P(r)$ for some $r$ and $p > \max(a,b)$. Then choose $m,n$ so that $m\cdot a + n \cdot b \equiv r \pmod p$ (this is clearly possible as $a,b$ are relatively prime to $p$). Now this means that $P(m\cdot a + n \cdot b)$ and $P(m\cdot a + (n+p) \cdot b) $ are multiples of $p$, a contradiction as both $m \cdot a + n \cdot b$ and $m \cdot a + (n+p) \cdot b$ are in $F$.