Let $a_1,a_2,\dots, a_n$ be positive integers with product $P,$ where $n$ is an odd positive integer. Prove that $$\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\le 2\gcd(a_1,\dots, a_n)^n.$$ Proposed by Daniel Liu
Problem
Source: 2017 ELMO #1
Tags: number theory, greatest common divisor, ELMO 2017, Elmo, Hi
26.06.2017 10:11
Let $\gcd (a_1,a_2, \ldots, a_n)=d$ then $a_i=db_i$ for all $1 \le i \le n$ and $\gcd (b_1, \ldots, b_n) =1$. Let $Q= b_1 \cdots b_n$ then it suffices to prove $$\gcd (b_1^n+Q,b_2^n+Q, \ldots, b_n^n+Q) \le 2.$$ If there is a prime $p \mid \gcd (b_1^n+Q,b_2^n+Q, \ldots, b_n^n+Q)$ then $p \nmid b_i \; \forall 1 \le i \le n$, otherwise WLOG $p \mid b_1$ then $p \mid Q$ so $p \mid b_i^n$ \for all $2 \le i \le n$, a contradiction to $\gcd (b_1,b_2, \ldots, b_n)=1$. Since $p \nmid b_i$ so $p \mid b_i^{n-1}+ \frac{Q}{b_i}$ or $b_i^{n-1} \equiv (-1)\frac{Q}{b_i} \pmod{p}$. Thus, $$\prod_{i=1}^n b_i^{n-1} \equiv (-1)^n \frac{Q^n}{b_1 \cdots b_n}=-(b_1 \cdots b_n)^{n-1} \pmod{p}.$$This follows $p \mid 2(b_1 \cdots b_n)^{n-1}$ or $p \mid 2$. Thus, the only possible prime divisor of $\gcd (b_1^n+Q,b_2^n+Q, \ldots, b_n^n+Q)$ is $2$. Next, we will go and prove $\nu_2 \left( \gcd (b_1^n+Q,b_2^n+Q, \ldots, b_n^n+Q) \right) \le 1$. Indeed, if $2 \mid \gcd (b_1^n+Q,b_2^n+Q, \ldots, b_n^n+Q)$ then $2 \nmid b_i$ and $2 \mid b_i^{n-1}+ \frac{Q}{b_i}$. Since $2 \nmid b_i$ and $2 \mid n-1$ so $b_i^{n-1} \equiv 1 \pmod{4}$. If $Q=b_1 \cdots b_n \equiv 1 \pmod{4}$. Since $n$ is odd so there exists $b_i \equiv 1 \pmod{4}$. Hence $b_i^{n-1}+\frac{Q}{b_i} \equiv 2 \pmod{4}$. If $Q \equiv 3 \pmod{4}$ then there exists $b_i \equiv 3 \pmod{4}$. Hence, $b_i^{n-1}+\frac{Q}{b_i} \equiv 2 \pmod{4}$. Thus, $\nu_2 \left( \gcd (b_1^n+Q,b_2^n+Q, \ldots, b_n^n+Q) \right) \le 2$. We follow $\gcd (b_1^n+Q,b_2^n+Q, \ldots, b_n^n+Q) \le 2$, as desired.
26.06.2017 10:46
Let the $\gcd(a_1,a_2,..,a_n) = d$. So, we can replace the $a_i's$ as $a_i = db_i$ for all $i's$. Let $Q = b_1b_2... b_n$. Also, $\gcd(b_1,b_2,..,b_n)=1$. $\gcd(a_1^n+P,a_2^n+P,..,a_n^n+P) = \gcd(d^nb_1^n+d^nQ,d^nb_2^n+d^nQ,..,d^nb_n^n + d^nQ) = d^n\gcd(b_1^n+Q,b_2^n+Q,..,b_n^n+Q)$. $2\gcd(a_1,a_2,...,a_n)^n = 2\gcd(db_1, db_2, ...,db_n)^n = 2d^n\gcd(b_1,b_2,..,b_n)=2d^n$. We had to show $\gcd(a_1^n+P,a_2^n+P,..,a_n^n+P)\leq 2\gcd(a_1,a_2,...,a_n)^n$ or $d^n\gcd(b_1^n+Q,b_2^n+Q,..,b_n^n+Q)\leq 2d^n$ or it suffices to show $$\gcd(b_1^n+Q,b_2^n+Q,..,b_n^n+Q)\leq 2$$. For the sake of contradiction, let there be a prime $p\geq 3$ such that $p|\gcd(b_1^n+Q,b_2^n+Q,..,b_n^n+Q)$. If there is a $b_k$ such that $p|b_k$, then $p|Q$. So, for every $1\leq i\leq n$, $0\equiv b_i^n + Q \equiv b_i^n (\bmod p)$. So, $p|b_i$ for all $i$. But we had $\gcd(b_1,b_2,..,b_n) = 1$, so there is no such $k$ such that $p|b_k$. $\Rightarrow \gcd(Q,p) = 1$. We know for $1\leq i \leq n$, $b_i^n + b_1b_2..b_n \equiv 0 (\bmod p)$. So, $b_i^n \equiv -1 (b_1b_2...b_n)$. If we take the product over all $i's$, we get $(b_1b_2..b_n)^n \equiv (-1)^n (b_1b_2...b_n)^n (\bmod p)$ So, $$Q^n \equiv (-1)^n Q^n \bmod p$$As $\gcd(Q,p) = 1$, $1\equiv (-1)^n \bmod p$. Now as $p\geq 3$,we get $n$ is even. But we were given that $n$ is odd which gives us a contradiction. So there is no $p \geq 3$ such that $p|\gcd(b_1^n+Q,b_2^n+Q,..,b_n^n+Q)$. So, $p = 2$ or $\gcd(b_1^n+Q,b_2^n+Q,..,b_n^n+Q) = 1$. When the $gcd(b_1^n+Q,b_2^n+Q,..,b_n^n+Q) = 1$, we are done, so we need to consider the case in which $p=2$ that implies $gcd(b_1^n+Q,b_2^n+Q,..,b_n^n+Q) = 2^m$ for $m\geq 1$. If there is a $b_j$ such that $b_j$ is even, then $Q$ is also even. So, $0\equiv b_i^n + Q \equiv b_i^n \bmod 2$, which would make all other $b_i's$ also to be even which contradicts the fact that $\gcd(b_1,b_2,..,b_n) = 1$. So, we get all $b_i$ are odd. So, $\gcd(Q,2^m) = 1$. We know for all $1\leq i\leq n$, $b_i^n + Q \equiv 0 \bmod 2^m$. So, $b_i^n \equiv -1(b_1b_2..b_n) \bmod 2^m$. Taking the product over all $i's$ we get $(b_1b_2..b_n)^n \equiv (-1)^n (b_1b_2..b_n)^n \bmod 2^m$. As, $\gcd(Q,2^m) = 1$ and as $n$ is odd, $1 \equiv (-1)^n \equiv -1 \bmod 2^m$. So, $2 \equiv 0 \bmod 2^m$. So, $m = 1$ So, we get $\gcd(b_1^n+Q,b_2^n+Q,..,b_n^n + Q) \leq 2$ where $\gcd(b_1^n+Q,b_2^n+Q,..,b_n^n + Q) = 2$ for all $b_i$ to be odd. Proved.
26.06.2017 10:53
Let $gcd(a_1,a_2, \cdots ,a_n) = d$ So $\exists b_1,b_2, \cdots ,b_n \in N $ such that $a_1 = db_1, a_2 = db_2 , \cdots , a_n = db_n$ and $gcd(b_1,b_2,\cdots ,b_n) = 1$ Let $P' = b_1b_2 \cdots b_n$ See that , $gcd(a_1^n -P , \cdots , a_n^n -P) = gcd(b_1^n -P', \cdots , b_n^n -P').d^n$ Let $q = gcd(b_1^n -P', \cdots , b_n^n -P')$ , it suffices to prove that $q \le 2$. Claim 1. $gcd(q,b_i) = 1 \forall i = \overline{1,n}$ Proof: Assume the contrary.So $\exists d >1$ such that $d|q$ and $d|b_i$. As $gcd(b_1,b_2,\cdots ,b_n) =1 => \exists j \neq i$ such that $gcd(d,b_j) =1$ But $d|b_j^n - P' => d|b_j^n$ , contradiction! Claim 2. $q|2$ and this shows that $q \le 2$ Proof: (here we will use the fact that $n$ is odd!) See that $b_i^n \equiv -P' (mod q) , \forall i = \overline{1,n} => {(b_1^n)}^n \equiv - {(P')}^n (mod q)$ So , $b_1^n \equiv b_i^n (mod q) => {(b_1^n)}^n \equiv b_1^nb_2^n \cdots b_n^n \equiv {(P')}^n (mod q)$ So , $q | 2{(P')}^n$ as $gcd(q,P') =1 => q|2$ Hence proved
26.06.2017 11:07
Mostly similar to above solutions, but anyways... Suppose $\text{gcd}(a_1,a_2,\cdots ,a_n)=x$, and set $b_1=\frac{a_1}{x},b_2=\frac{a_2}{x},\cdots ,b_n=\frac{a_n}{x}.$ Clearly $\text{gcd}(b_1,\cdots ,b_n)=1$. Note that this means $a_i^n+P=a_i^n+a_1a_2\cdots a_n=x^n(b_i^n+b_1b_2\cdots b_n)$, so $$\text{gcd}(a_1^n+P,\cdots ,a_n^n+P)=x^n\text{gcd}(b_1^n+b_1b_2\cdots b_n,\cdots ,b_n^n+b_1b_2\cdots b_n).$$To prove the given inequality, we need to show $$\text{gcd}(b_1^n+b_1b_2\cdots b_n,\cdots ,b_n^n+b_1b_2\cdots b_n)\le 2.$$ Let $d:=\text{gcd}(b_1^n+b_1b_2\cdots b_n,\cdots ,b_n^n+b_1b_2\cdots b_n)$; we claim that $d$ is relatively prime of each of the $b_i$'s. To see this, note that if there a $b_i$ and a prime $p$ so that $p|b_i$ and $p|d$, then $p|b_1b_2\cdots b_n$, and since $p|d|b_j^n+b_1\cdots b_n$, we have $p|b_j^n\implies p|b_j$, implying that $p$ divides each of the $b_i$'s. This contradicts $\text{gcd}(b_1,\cdots ,b_n)=1$. Now for $1\le i\le n$, we have $$d|b_i^n+b_1b_2\cdots b_n\implies b_i^n\equiv -b_1b_2\cdots b_n\pmod{d}.$$Multiplying these congruences for $1\le i\le n$, and noting that $n$ is odd we have $$(b_1b_2\cdots b_n)^n\equiv -(b_1b_2\cdots b_n)^n\pmod{d}\implies d|2(b_1b_2\cdots b_n)^n.$$But since $d$ is relatively prime to $b_1,\cdots ,b_n$, this implies $d|2\implies d\le 2$, as required. $\blacksquare$
26.06.2017 11:11
26.06.2017 23:36
Let $d = \gcd(a_1, \ldots, a_n)$, and write $a_k = db_k$ for positive integers $b_1, \ldots, b_n$ with $\gcd(b_1, \ldots, b_n) = 1$. Then \[\gcd(a_1^n + P, \ldots, a_n^n + P) = d^n \gcd(b_1^n + Q, \ldots, b_n^n + Q)\]where $Q = b_1b_2 \dotsm b_n$. Hence it suffices to show \[D := \gcd(b_1^n + Q, \ldots, b_n^n + Q) \le 2.\]To do this, write \[b_1^n \equiv b_2^n \equiv \ldots \equiv b_n^n \equiv -Q \pmod{D}.\]Suppose some prime $p$ divides both $D$ and $Q$. Then \[b_1^n \equiv b_2^n \equiv \ldots \equiv b_n^n \equiv -Q \equiv 0 \pmod{p}\]so $p \mid b_1, b_2, \ldots, b_n$, contradicting $\gcd(b_1, \ldots, b_n) = 1$. Thus $\gcd(D, Q) = 1$. But \[Q^n = b_1^nb_2^n\ldots b_n^n \equiv (-Q)^n \pmod{D}\]so $D \mid 2Q^n$ (since $n$ is odd). This is enough to force $D \mid 2$, i.e. $D \le 2$, as desired.
10.12.2019 11:53
If $\gcd(a_1,\ldots,a_n) > 1$, we can divide out by $\gcd(a_1,\ldots,a_n)^n$ from both sides since every term in the LHS is of degree $n$. So assume $\gcd(a_1,\ldots,a_n)=1$, then we want to show \[ d:=\gcd(a_1^n + P, a_2^n+P, \ldots, a_n^n + P) \le 2. \]We have $d=\gcd(a_1^n+P, a_2^n-a_1^n, a_3^n-a_1^n,\ldots,a_n^n-a_1^n)$ by Euclid, so \[ -a_1a_2\cdots a_n \equiv a_1^n \equiv a_2^n \equiv \cdots \equiv a_n^n \pmod{d}. \]Multiplying together each of the above $n$ relations containing $-a_1a_2\cdots a_n \mod d$, we get \[ (-a_1a_2\cdots a_n)^n \equiv a_1^na_2^n\cdots a_n^n \pmod{d} \implies 2(a_1a_2\cdots a_n)^n \equiv 0 \pmod{d} \]since $n$ is odd. Suppose some prime $p$ existed s.t. $p\mid a_1$ and $p\mid d$. Then there must exist some $a_i$ such that $p\nmid a_i$, otherwise $p\mid \gcd(a_1,\ldots,a_n)=1$. We know $a_1^n\equiv a_i^n \pmod{d}$, so $a_1^n\equiv a_i^n \pmod{p}$. But $a_1\equiv 0 \pmod{p}$, so $a_i^n\equiv 0 \pmod{p}$, so $a_i\equiv 0 \pmod{p}$, which is a contradiction since we assumed $p \nmid a_i$. There was nothing special about $a_1$, so $\gcd(a_k,d)=1$ for all $k=1,\ldots,n$. In particular, $\gcd(a_1a_2\cdots a_n, d)=1$. So we can divide by $(a_1a_2\cdots a_n)^n$ on both sides to get $2\equiv 0 \pmod{d}$, so $d\le 2$.
10.12.2019 14:05
Easy for a #1 whatshisbucket wrote: Let $a_1,a_2,\dots, a_n$ be positive integers with product $P,$ where $n$ is an odd positive integer. Prove that $$\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\le 2\gcd(a_1,\dots, a_n)^n.$$ Proposed by Daniel Liu Let $d=\gcd(a_1,a_2,\cdots a_n)$.Hence $a_i=d\cdot b_i$ for some $b_i's$.Hence $P=d^n\cdot Q$ where $Q=b_1b_2\cdots b_n$.Thus we have to show \[d^n\cdot \gcd(b_1^n+Q,b_2^n+Q,\dots, b_n^n+Q)=\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\leq \gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\leq 2\gcd(a_1,\dots, a_n)^n=2d^n\cdot \gcd(b_1,\dots, b_n)^n\]\[\implies \gcd(b_1^n+Q,b_2^n+Q,\dots, b_n^n+Q)\leq 2\gcd(b_1,\dots, b_n)^n =2\].Since $\gcd(b_1,b_2,\dots b_n)=1$Now let $p\mid \gcd(b_1^n+Q,b_2^n+Q,\dots, b_n^n+Q)$ be a prime.Then \[-Q\equiv b_1^n\equiv b_2^n\cdots \equiv b_n^n\pmod p\]\[(b_1^n)(b_2^n)\cdots (b_n^n)\equiv (-Q)^n\pmod p \implies Q^n\equiv -Q^n\pmod p\implies 2Q^n\equiv 0\pmod p\].Now if $p\neq 2$.Then $p\mid Q^n\implies p\mid Q\implies p\mid b_i \implies p\mid \gcd(b_1,b_2,\cdots b_n)=1$ a contradiction!Thus $p=2$.Then if $4\mid \gcd(b_1^n+Q,b_2^n+Q,\dots, b_n^n+Q)$.Clearly all $b_i$ are odd.Clearly not all $b_i\equiv 1\pmod 4$ otherwise $-1\equiv -Q\equiv b_i^n\equiv 1\pmod 4$.Similarly not all $b_i\equiv 3\pmod 4$.Thus there are $i,j$ such that $b_i\equiv 1\pmod 4 $ and $b_j\equiv 3\pmod 4$.But then $0\equiv b_i^n-b_j^n\equiv 1-(-1)=2\pmod 4$ again a contradiction.Hence $\gcd(b_1,b_2,\cdots b_n)=1,2\implies \gcd(b_1,b_2,\cdots b_n)\leq 2$ as desired$\blacksquare$
27.04.2020 00:30
ok !
17.05.2020 00:30
Let $d = \gcd(a_1, a_2, \dots a_n).$ Then let $a_i = db_i$ for each $i$. We want to show that $\gcd(b_1^n + b_1 \dots b_n, b_2^n + b_1 \dots b_n , \dots ) \le 2.$ Suppose for the sake of contradiction that there exists prime $p > 2$ dividing each of $b_i^n + b_1 \dots b_n.$ Then, we must have $b_i^n = -b_1 \dots b_n \pmod{p}.$ Multiplying over all $i$ gives $$(-b_1b_2 \dots b_n)^n \equiv (b_1 b_2 \dots b_n)^n \implies 2(b_1 \dots b_n)^n \equiv 0 \pmod{p}.$$ Claim: $p \nmid b_i$ for any $i.$ Proof: Suppose that it does. Notice that $b_1^n \equiv b_2^n \equiv \dots b_n^n \pmod{p}.$ If there exists $p$ with $p \mid b_i$, then $b_i \equiv 0 \pmod{p}$ for all $p$, contradiction. Thus, $p \mid 2$, and we conclude. $\blacksquare$
02.09.2020 22:17
Note we can scale so $\text{gcd}(a_1, \dots , a_n) = 1$; then we wish to show that if $q$ divides all of the $a_i^n+P$, then $q \leq 2$. Write down all the equations of the form $a_i^n \equiv -P \pmod{q}$. Note that $q$ cannot share a prime factor with any of the $a_i$, since then that prime would divide all the $a_i$. Now multiplying together all these equations gives $1 \equiv -1 \pmod{q}$ and we're done.
05.09.2020 06:30
Let $(a_1,a_2\ldots a_n)=1$; from here, FTSOC assume that there exists some odd prime $q$ dividing all of $a_i+P$. Then, we see that if one $a_i$ is a multiple of $q$, then $P$ is a multiple of $q$ which would force every other $a$ to be a multiple of $q$ and violate the $(a_1,a_2\ldots a_n)=1$ condition. Hence, we have $q\nmid P$. Though, multiplying every equation gives us that $P^n\equiv -P^n$ modulo $q$ which upon dividing both sides by $P^n$ (allowed as it is not a multiple of $q$) gives that $1\equiv -1 \pmod{q}$ which obviously is impossible.
11.10.2020 10:31
Let $d$ be the $\gcd(a_1,...,a_n)$ and write $a_i = dk_i$. Then we have $\gcd(a_1+P,...,a_n+P) = \gcd(d^nk_{1}^n+d^nk_1...k_n,...,d^nk_{n}^n+d^nk_1,...,k_n)$. Let P' denote the product $k_1....k_n$. What is left to prove is that $d'=\gcd(k_1+P',...,k_n+P') \leq 2$. Clearly $d'$ is relatively prime to each $k_i$ since otherwise a commmon divisor would divide the remaining $k's$. We know have the congruences $k_i = -P' \mod d'$ and if we multiply them we get $(a_1...a_n)^n = P^n = (-P)^n = -P^n$ (since n is odd). Hence $d'$ divides $2P$ but since $d'$ and P are relatively prime this implies that $d' | 2$ and hence $d' \leq 2$
24.03.2021 22:07
It seems that many people have forgotten to prove that the gcd isn't 4 or 8 or something like that! Clearly dividing everything by $\gcd(a_1,a_2,\ldots,a_n)$ doesn't change anything, hence WLOG let $\gcd(a_1,a_2,\ldots,a_n)=1$, so the inequality becomes: $$\gcd(a_1^n+P, a_2^n+P,\ldots,a_n^n+P) \leq 2,$$whenever $\gcd(a_1,a_2,\ldots,a_n)=1$. First, I claim that no primes $p>2$ divide the gcd. Suppose FTSOC that a prime $p$ does divide the gcd. Clearly $p$ cannot divide all of $a_1,a_2,\ldots,a_n$. Now suppose $p$ divides some of these numbers, so $p \mid P$. But there exists an $i$ with $p \nmid a_i$, which means $p \nmid a_i^n+P$: contradiction. Hence $p$ divides none of $a_1,a_2,\ldots,a_n$. Then it is necessary to have $a_i^n \equiv -P \pmod{p}$ for all $i$. Since $n$ is odd, multiplying these congruences yields $P^n \equiv -P^n \pmod{p}$. But since $p \nmid P$, this gives $-1 \equiv 1 \pmod{p}$, which is impossible since $p \neq 2$. Hence proved. Now I claim that $4$ does not divide the gcd. Suppose FTSOC that $a_i^n+P \equiv 0 \pmod{4}$ for all $i$. As with before, since not all of $a_1,a_2,\ldots,a_n$ can be even, none of them can be even. Further, observe that since $n$ is odd, $a_i^n \equiv a_i \pmod{4}$. Note that if all of the $a_i$ are congruent to $1 \pmod{4}$, then their product is as well and thus $a_i^n+P \equiv 2 \pmod{4}$, contradiction. Similarly not all of the $a_i$ are congruent to $3 \pmod{4}$. But then picking $i,j$ such that $a_i \equiv 1 \pmod{4}$ and $a_j \equiv 3 \pmod{4}$ implies that $a_i^n+P \not \equiv a_j^n+P \pmod{4}$, so they cannot both equal zero: contradiction. Combining these two claims, it follows that the gcd is at most $2$. $\blacksquare$
26.10.2021 16:21
22.11.2021 19:33
Long time no AoPS post Claim : We can safely assume $\gcd(a_1, a_2, a_3, \cdots a_n) = 1$ Proof : Assume $\gcd(a_1, a_2, a_3, \cdots a_n) = d \neq 1$. Therefore there exist $(b_1, b_2, b_3, \cdots b_n)$ such that $b_i = \frac{a_i}{d}$ for every $1 \le i \le n$. $\implies \gcd(b_1, b_2, b_3, \cdots b_n) = 1$ So now we have to prove $d^n \gcd \left((b_1)^n + \prod b_i , (b_2)^n + \prod b_i , (b_3)^n + \prod b_i , \cdots (b_n)^n + \prod b_i \right) \le 2 d^n \longleftrightarrow \gcd(b_1 + \prod b_i , b_2 + \prod b_i , b_3 + \prod b_i , \cdots b_n + \prod b_i) \le 2$ Which is equivalent to assuming $\gcd(a_1, a_2, a_3, \cdots a_n) = 1$ Now we have to prove $\gcd \left( (a_1)^n + \prod a_i , (a_2)^n + \prod a_i , (a_3)^n + \prod a_i , \cdots (a_n)^n + \prod a_i \right) \le 2$ Lemma : $\gcd(t_1, t_2, t_3, \cdots t_n) = \gcd(t_1, t_2 - t_1, t_3 - t_1, \cdots t_n - t_1)$ Proof : Let $\gcd(t_1, t_2, t_3, \cdots t_n) = q$. From Generalized Bezout's Identity we can find $(c_1, c_2, c_3, \cdots , c_n)$ such that $t_1c_1 + t_2c_2 + t_3c_3 + \cdots + t_nc_n =q$. Similarly we can find $(d_1, d_2, d_3, \cdots , d_n)$ such that $t_1d_1 + (t_2 - t_1)d_2 + (t_3 - t_1)d_3 + \cdots + (t_n - t_1)d_n = r = \gcd(t_1, t_2 - t_1, t_3 - t_1, \cdots t_n - t_1)$ Since $q | t_1$ and $q | t_2$, we have $q | t_2 - t_1$. Likewise $q | t_3 - t_1$, $q | t_4 - t_1$, $\cdots q | t_n - t_1$ Consequently $q | r$. Analogously we prove $r | q$ and since $q, r \in \mathbb{N} \longrightarrow q = r$ So the original question now becomes to prove $\gcd \left( (a_1)^n + \prod a_i , (a_2)^n - (a_1)^n , (a_3)^n - (a_1)^n , \cdots (a_n)^n - (a_1)^n \right) \le 2 $ But $\gcd \left((a_1)^n , (a_2)^n - (a_1)^n , (a_3)^n - (a_1)^n , \cdots (a_n)^n - (a_1)^n \right) = \gcd \left((a_1)^n , (a_2)^n , (a_3)^n , \cdots (a_n)^n \right) = 1$ Hence Proved!
12.02.2022 17:16
I can't get the above solution. In particular, in the last few lines how exactly are we proving $$\gcd \left( (a_1)^n + \prod a_i , (a_2)^n - (a_1)^n , (a_3)^n - (a_1)^n , \cdots (a_n)^n - (a_1)^n \right) \le 2 $$
12.05.2022 06:35
WLOG assume $\gcd(a_1,a_2,\dots,a_n)=1$ by dividing all $a_i$ by $\gcd(a_1,a_2,\dots,a_n).$ Let the LHS equal $d.$ Then, $a_i^n\equiv -P\pmod{d}$ so multiplying for all $i$ we have $P^n\equiv-P^n\pmod{d}.$ If $q$ is an odd prime divisor of $d,$ we see $$q\mid 2P^n\implies q\mid P\implies q\mid -a_i^n\implies q\mid a_i\implies q\mid\gcd(a_1,a_2,\dots,a_n)=1.$$Thus, $d=2^k.$ Suppose FTSOC that $k>1.$ Then, $4\mid d\mid 2P^n$ so $2\mid P.$ Since $2\mid a_i^n+P,$ we know $2\mid a_i,$ a contradiction. Hence, $d\mid 2.$ $\square$
09.09.2022 14:30
Seems wrong. WLOG, assume that $\gcd(a_1, a_2, \cdots, a_n) = 1$. Note that we can assume this because multiplying all of $a_i$ by $g$ does not change anything, as the $g$ just cancels out. Let $d = \gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P)$. Note that we have $$a_i^n = k_id - p$$(say). Then multiplying from $i = 1$ to $i = n$, we have $$P^n = \prod_{i = 1}^{n} (k_id - P)$$which gives (since $n$ is odd) $$2P^n = d \cdot K$$for some $K \in \mathbb{N}$. Thus, $d \mid 2P^n$. Suppose some prime $p$ divides both $d$ and $P^n$. Then, we have $p \mid P$, which gives $p \mid a_i$ for all $i$ which is a contradiction since we assumed $\gcd(a_1, a_2, \cdots, a_n) = 1$. Thus, $d \mid 2$ and thus, $$\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P) \le 2$$which is what we needed. $\blacksquare$ (Taken $2$ hints from MONT lol) I think that, because I have not taken the case $d = 2^k$, my solution is wrong, so can anyone tell me, whether it is ok to not take the case $d = 2^k$?
19.09.2022 20:05
Okay, So assume if the gcd on the LHS is greater than 1, implies that gcd is dividing the other numbers too (easy modular arithmetic), then at most it would be 2(the gcd of whole a_i's)^n
22.01.2023 19:12
Assume that $\gcd{(a_1,\dots,a_n)}=1$. Then if $p\mid a_i^n+P$ for all $1\le i\le n$ we find that \[P^n\equiv -P^n\pmod p\implies P\equiv 0\pmod p\]if $p$ is an odd prime. But there must exist some $a_i$ where $p\nmid a_i$ which gives a contradiction. Now if $p=2$ then by taking $\pmod 4$ we get that $2\mid P$ and since at least one odd number exists we get another contradiction. Therefore the $\gcd$ is either $1$ or $2$, and we are done. $\blacksquare$
28.03.2023 21:18
Claim. For every odd prime $p$, $\nu_p(LHS)\le \nu_p(RHS)$. Proof. Use strong induction on $S=\sum_{k=1}^n a_k$. Base case $S=n$ is trivial. Consider when $p$ divides the LHS(otherwise this is trivial). Then \[A=a_1^n\equiv a_2^n\equiv\dots\equiv a_n^n\pmod p.\]But \[P^n=A^n\equiv (-P)^n\pmod p\rightarrow p\mid P,\]so $p$ divides every one of $(a_k)$. But this means we can reduce the problem to $\left(\frac{a_k}{p}\right)$, which we already solved by the inductive hypothesis. $\blacksquare$ Claim. $\nu_2(LHS)\le \nu_2(RHS)$. Proof. Use strong induction on $S=\sum_{k=1}^n a_k$. Base case $S=n$ is trivial. Consider when $2$ divides the LHS(otherwise this is trivial). If $P$ is even, then each of $(a_k)$ is even, and we can reduce the problem to $\left(\frac{a_k}{2}\right)$, which we already solved by the inductive hypothesis. Otherwise, $P$ is odd, then each of $(a_k)$ is odd. I claim that not all of \[a_1^n+P,a_2^n+P,\dots,a_n^n+P\]are divisible by $4$, which will immediately finish. Suppose otherwise, then \[a_1\equiv a_2\equiv\dots\equiv a_n\equiv P\pmod 4,\]where the last part is because $n$ is odd. But then \[a_1^n+P\equiv a_1+P\not\equiv 0\pmod 4,\]contradiction. $\blacksquare$ QED.
24.05.2023 21:30
Note that if all $a_i$ are multiplied by $k$, then both sides will be multiplied by $k^n$. Thus, WLOG that $$\gcd(a_1\cdots a_n)=1,$$so we are then showing that $$\gcd(a_1^n+P\cdots a_n^n+P)\leq 2.$$ We will first show that there is no prime $q\geq3$ such that $q$ divides all of $a_1^n+P\cdots a_n^n+P.$ Suppose FTSOC that such a prime exists. Then, $$a_1^n\equiv -P\pmod q$$$$a_2^n\equiv -P\pmod q$$$$\cdots$$$$a_n^n\equiv -P\pmod q.$$If any $a_i$ were divisible by $q$, then $P$ would be divisible by $q$, so all of them would be, which contradicts our assumption that $\gcd(a_1\cdots a_n)=1.$ Thus, assume that none of them are divisible by $q$. The trick is to multiply all of these congruences together, to get $$P^n\equiv -P^n\pmod q,$$since $n$ is odd. Hence, $P^n\equiv0\pmod q$ since $q$ is odd. Thus, since $q$ is prime, $P$ is already divisible by $q$. Thus, some $a_i$ is divisible by $q$, contradiction. In order to finish, we will then show that we cannot have all of $a_1^n+P,\cdots a_n^n+P$ be divisible by 4. Again, FTSOC assume they all are and proceed as earlier to get $$a_1^n\equiv -P\pmod 4$$$$a_2^n\equiv -P\pmod 4$$$$\cdots$$$$a_n^n\equiv -P\pmod 4.$$Again, multiply all of these to get $$P^n\equiv -P^n\pmod 4,$$which is just saying that $P$ is even. Hence, from the earlier congruences, $a_i^n$ is even for all $a_i$, hence all $a_i$ are even, contradiction, so we are done.
31.07.2023 05:07
Let $\gcd(a_1,a_2, \ldots, a_n) = d$. It follows that we can express $a_i = db_i$ for all $1 \leq i \leq n$ and note that $\gcd(b_1, b_2, \ldots, b_n) = 1$. Let $Q = b_1 \cdot b_2 \cdots b_n$. Plugging in the substitution into the original expression yields that we need to prove that $$\gcd(b_1^n+Q, b_2^n+Q, \ldots, b_n^n+Q) \leq 2$$ Let $m = \gcd(b_1^n+Q, b_2^n+Q, \ldots, b_n^n+Q)$. It follows that $$b_i^n \equiv -Q \pmod m$$for all $1 \leq i \leq n$. Multiplying each of the $n$ relations gives us $$Q^n \equiv (-Q)^n \equiv -Q^n \pmod m$$since $n$ is odd. This means that $m \mid 2Q^n$. Let $q$ be a prime factor of $m$ so that $q \mid 2Q^n$. If $q \mid Q$, then $b_i^n \equiv -Q \equiv 0 \pmod q$ which implies that $q \mid b_i$ for all $i$. This is bad because recall $\gcd(b_1, b_2, \ldots, b_n) = 1$. So, since $q \nmid Q$, we have $q \mid 2$. This implies that $m = 1$ or $m = 2^k$ for some $k$. We will prove that $k =1$. If $k \geq 2$, then $2Q^n \equiv 0 \pmod 4$ which means that $Q$ is divisible by $2$. If we consider $b_i^n \equiv -Q \equiv 0 \pmod 2$ it follows that $2 \mid b_i$ for all $i$ which is bad because recall $\gcd(b_1, b_2, \ldots, b_n) = 1$. Thus $k = 1$ and we either have $m = 1$ or $m = 2$ as desired.
05.09.2023 08:23
HOW IS ANDYXPANDY HERE EVERY SINGLE TIMEE this ones pretty misplaced lol Since it's homogeneous, WLOG $\gcd{(a_1,...,a_n)}=1$. Then taking an odd prime $p\mid a_k^n+P$, we have $a_k^n\equiv-P^n\pmod p$; multiplying them, we get $P^n\equiv -P^n\pmod p\rightarrow p\mid P\rightarrow p\mid a_i$, contradiction to the gcd, hence p=2; if P is odd then all $a_k$ are odd. Suppose $4\mid a_k^n+P$. Case 1. P=3 mod 4. Then all $a_k$=1 mod 4 due to n odd, contradiction since P is then 1 mod 4. Case 2. P=1 mod 4. Then all $a_k$=3 mod 4, contradiction since P is product of odd number of 3 mod 4 = 3 mod 4. We conclude the $\gcd$ is either $1$ or $2$, which is indeed $\le 2$. $\blacksquare$
11.09.2023 03:59
Quite simple Let $\gcd(a_1, a_2, \cdots a_n) = d$ $b_1, b_2,\cdots = a_1/d, a_2/d,\cdots$, and let $X = b_1b_2\dots b_n$ Then it remains to show $\gcd(b_1^n+X,b_2^n+X,\dots, b_n^n+X)\leq 2$ Consider some $p | b_1^n+X, p| b_2^n + X, \dots$. Then note that $p \nmid b_i$ for any $i$, since otherwise there would exist some $p\nmid b_j$ so $p\nmid b_j^n + b_1\cdots b_i \cdots b_n$, a contradiction. Then note that $b_i^n \equiv -X \pmod p$, so $$X^n \equiv b_1^nb_2^n\cdots b_n^n \equiv -X^n \pmod p,$$so $p|2X^n$ and thus $p|2$. It remains to show its impossible to have $4 | b_i^n + X$ for all $i$ if $b_i \equiv 1, 3 \pmod 4$. Case 1: If there are an even number of $b_i \equiv 3 \pmod 4$, there must exist some $b_j \equiv 1 \pmod 4$, which means $b_j^n + X \equiv 2 \pmod 4$. Case 2: If there are an odd number of $b_i \equiv 3\pmod 4$ then any one of the $b_i^n + X \equiv 2 \pmod 4$. $\blacksquare$
17.12.2023 23:57
Nice and easy Let $d = \gcd(a_1, a_2, \dots, a_n)$, and let $a_i = db_i$ for each $i$. The condition is equivalent to showing $$\gcd(b_1^n + P, b_2^n+P, \dots, b_n^n + P) \leq 2.$$Suppose that some $p \nmid 2$ divides this GCD. Then, note that $b_1^n \equiv b_2^n \equiv \cdots \equiv b_n^n \equiv c \pmod p$ for some $c$. On the other hand, we have $$a_1^n +P \mid a_1^{n^2} + P^n \equiv c^n \cdot 2 \not \equiv 0 \pmod p,$$which is an obvious contradiction. To resolve the $\nu_2$, simply work with $4$ instead of $p$.
05.01.2024 21:07
Fix some prime $p$. WLOG, let $\nu_{p}(a_1) \le \nu_{p}(a_2) \le \cdots \le \nu_{p}(a_n)$. We begin with the case when $\nu_{p}(a_1) < \nu_{p}(a_n)$. Then note that, \[ \nu_{p}(a_1^n) = n\nu_{p}(a_1) = \nu_{p}(a_1) + \cdots + \nu_{p}(a_1) < \nu_{p}(a_1) + \nu_{p}(a_2) + \cdots + \nu_{p}(a_n) = \nu_{p}(a_1\cdot a_2 \cdots a_n) = \nu_{p}(P). \] This means that $\nu_{p}(a_1^n + P) = \nu_{p}(a_1^n)$. Now note that $\nu_{p}(a_i^n + P) \ge \min\left\{\nu_{p}(a_i^n),\nu_{p}(P)\right\} \ge \nu_{p}(a_1^n + P)$ for all $i$. This then gives us that $\nu_{p}(\gcd(a_1^n + P,a_2^n + P,\ldots,a_n^n + P)) = \nu_{p}(a_1^n+P) = \nu_{p}(a_1^n)$. Now note that $\nu_{p}(2\gcd(a_1,\ldots,a_n)^n) \ge \nu_{p}(a_1^n)$ thus we are done for this case. Now for the case when $\nu_{p}(a_1) = \cdots = \nu_{p}(a_n)$. We can scale the power of $p$ from both sides to get WLOG that $\nu_{p}(a_1) = \cdots = \nu_{p}(a_n) = 0$. Then we divide into two cases, one where $p=2$ and other when $p \ge 3$. Firstly, if $p \ge 3$, then we get that $\nu_{p}(2\gcd(a_1,\ldots,a_n)^n) = n\nu_{p}(a_1) = 0$. So we have to prove that $\nu_{p}(\gcd(a_1^n + P,a_2^n + P,\ldots,a_n^n + P)) \le 0$. FTSOC assume the contrary. Then we get that $\nu_{p}(\gcd(a_1^n + P,a_2^n + P,\ldots,a_n^n + P)) > 1 \implies p \mid a_i^n + P$ for all $i$. So, \[ a_i^n \equiv -P = -a_1\cdots a_n \pmod{p} \implies a_i \equiv - a_1\cdots a_i \cdot a_{i+2} \cdots a_n \pmod{p}. \]Now we multiply all the cyclic iterations and use the fact that $n$ is odd to get that $(a_1\cdots a_n)^{n-1} \equiv -1 (a_1\cdots a_n)^{n-1} \pmod{p} \implies 1 \equiv -1 \pmod{p} \implies p \mid 2$, contradiction. Otherwise if $p = 2$, then we get that the RHS is $\nu_{2}(2\gcd(a_1,\ldots,a_n)^n) = 1 + n\nu_{2}(a_1) = 1$. Thus it is enough to show that $4\nmid \gcd(a_1^n + P,a_2^n + P,\ldots,a_n^n + P)$. Suppose not; then $4 \mid a_i^n + P$ for all $i$. Repeating the same process above, we again get that $4 \mid 2$ which is a contradiction and we are done.
18.01.2024 11:10
As pointed out previously, many people have missed to disprove the case where gcd could be $2^m$ where $m \ge 2$ (even I had missed it until i saw the thread ) Since the degree of both the sides are the same, we can homogenize by assuming $\gcd(a_1,a_2 \cdots a_n)=1$ Now suppose an odd prime $p$ divides the LHS, then we make 2 cases Case 1: $p|a_i$ for some $i \le n$ Notice that this gives us $p|P$ and hence $p|a_i \ \forall \ i, \ 1 \le i \le n$ which is clearly a contradiction since we assumed that all $a_i$'s had no common factor. Hence this case is impossible $\square$ Case 2: $p|a_i^{n-1}+\frac{P}{a_i}$ Writing this in modular form gives us $$-a_i^{n-1}\equiv \frac{P}{a_i} \pmod{p}$$Multiplying all the $n$ such equivalences we get $(-1)^n \cdot P^n \equiv P^n \pmod{p}$ which means $2\equiv 0 \pmod{p}$ which isn't possible because we assumed $p$ is an odd prime $\square$ Now since we know that only $p=2$ divides the LHS, we will prove that $4$ doesn't divide the LHS to ensure that $\gcd \le 2$ Notice that none of the $a_i's$ are even which gives us $a_i^2\equiv 1 \pmod{4}$. Now let $n=2k+1$, we get by the divisibility that $$(a_1^2)^k \cdot a_1 \equiv (a_2^2)^k \cdot a_2 \cdots \equiv (a_n^2)^k \cdot a_n \pmod{4} \implies a_1 \equiv a_2 \cdots a_n \pmod{4}$$Finally $a_i^n+P \equiv 2a_i^n \equiv 0 \pmod{4}$ which is possible only when $2|a_i$ which is a contradiction since none of $a_i$ are even $\blacksquare$
18.01.2024 15:56
I too missed the case of $2^m$ as pointed out by @above. Thanks to you for pointing it out We can assume $\gcd(a_1,a_2 \cdots a_n)=1$
Lets assume the GCD to be divisible by a prime p We get $ a_1^n \equiv a_2^n \cdots \equiv a_i^n \equiv -P = -a_1\cdots a_n \pmod{p} $ Now we use the fact that $n$ is odd. $(a_1\cdots a_n)^{n} \equiv -1 (a_1\cdots a_n)^{n} \pmod{p}$. From this only 2 is possible. Now for the case of $2^m$ , we can procced as above We are done
25.01.2024 02:21
We can assume $\gcd(a_1,a_2,\dots, a_n)=1$, so it suffices to prove $$d=\gcd(a_1^n+P,a_2^n+P,\dots a_n^n+P)\leq 2$$Let $p$ be a prime that divides that $\gcd$ Claim. $p\nmid a_i$ and $p\nmid P$ Proof: If $p\mid a_i \Rightarrow p\mid P\Rightarrow p$ divides all $a_i$, which contradics $\gcd(a_1,a_2,\dots, a_n)=1$ We also have $d\mid a_i^n+P \hspace{0.2cm}\forall i$, so $a_i^n\equiv -P\pmod d \Rightarrow$ $$P^n=(a_1a_2\cdots a_n)^n\equiv (-P)^n\equiv -P^n\pmod d$$so $2P^n\equiv 0\pmod d\Rightarrow d\mid 2$ as desired
08.03.2024 03:04
cute After dividing both sides of the inequality by $\gcd(a_1, a_2, \ldots, a_n)^n$, we reduce it to the case where $\gcd(a_1, a_2, \ldots, a_n) = 1$. Then we wish to show that $$\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\le 2.$$First, we prove that $4 = 2^2$ does not divide the LHS. Note that at least one of the $a_i$ must be odd, as otherwise $2$ would divide their gcd. Considering all possible cases, we find that: If all of them are odd and equivalent modulo $4$, for all $i$, $a_i^n + P \equiv 2 \not\equiv 0 \pmod 4$ If all of them are odd and one is $1 \pmod 4$ while another is $3 \pmod 4$, these exist $i$ and $j$ such that $(a_i^n + P) - (a_j^n + P) \equiv 2 \pmod 4$, so $4$ cannot divide the LHS If at least one of them is even, then $P$ is even, so for some $i$, $a_i^n + P$ is odd Now, we show that it's impossible for an odd prime to divide $\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)$. Suppose ftsoc there existed some odd prime $p$ that did; then for all $1 \le i \le n$, we have $P \equiv -a_i^n \pmod p$. Multiplying all of these congruences together, we get $$P^n \equiv (-1)^n(a_1a_2\cdots a_n)^n \pmod p \implies P^n \equiv -P^n \pmod p,$$so $p \mid 2P^n$. This implies that $p \mid P$, so for all $i$, we also find that $p \mid a_i^n \implies p \mid a_i$, which is a contradiction because $\gcd(a_1, a_2, \ldots, a_n) = 1$.
06.05.2024 00:46
Suppose $\gcd(a_1, a_2, \cdots, a_n) = d$. Define $\nu_d(n)$ as the largest integer $k$ such that $d^k \mid n$. We know that $\nu_d(P) \geq n$ and there exists $k$ such that $\nu_d(a_k) = 1$, so it follows that $$\nu_d(a_k^n + P) = n = \mathrm{min} \, \nu_d(a_i^n + P)$$for $1 \leq i \leq n$. Thus, $$\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P) = d^n \gcd(A_1^n + P', A_2^n + P', \cdots, A_n^n + P')$$where $A_i = \dfrac{a_i}{d}$ and $P' = \dfrac{P}{d^n}$. $\gcd(A_1, A_2, \cdots, A_n) = 1$. Further, on the right hand side of the inequality, we have $$\gcd(a_1, \cdots, a_n)^n = d^n$$so cancelling $d^n$ on both sides, we obtain $$\gcd(A_1^n + P', A_2^n + P', \cdots, A_n^n + P') \leq 2$$Since the inequality still holds equivalently when $\gcd(a_1, a_2, \cdots, a_n) = 1$, for convenience, we could now suppose in the original problem statement that $\gcd(a_1, a_2, \cdots, a_n) = 1$, and we must show that, $$\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P) \leq 2$$Consider a prime $p$, where $p \mid a_k$ for some $k$. Since $p \mid P$ while $p \nmid a_i$ for all of the remaining $a_i$, it follows that $\nu_p(a_i^n + P) = 0$. This implies that $$\nu_p(\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P)) = 0$$for all primes that divide one of $a_i$. Now, consider a prime $q$ that does not divide any $a_i$. For $q \mid \gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P)$ to be true, we must have $$-P \equiv a_1^n \equiv a_2^n \equiv \cdots \equiv a_n^n \pmod q$$This implies that $$-P^n \equiv (a_1a_2\cdots a_n)^n \equiv P^n \pmod q$$or $$2P^n \equiv 0 \pmod q$$We note that $\gcd(P^n, q) = 1$, so if $q \neq 2$, then $q$ doesn't exist, and $\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P)=1$, as desired. If $q=2$, then we must have $\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P) = 2^m$ for some $m \in \mathbb{Z^+}$ as $q$ is the only prime that divides $\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P)$. We claim that if $q=2$, then $\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P) \equiv 2 \pmod 4$. Suppose for the sake of contradiction that $\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P) \equiv 0 \pmod 4$. First, noting that $a_i \equiv 1,-1 \pmod 4$ for $1 \leq i \leq n$, if there exists $u$ and $v$ such that $a_u \not\equiv a_v \pmod 4$ (meaning one of them is $1 \pmod 4$ while the other is $-1 \pmod 4$), then we must have $P \equiv -1 \pmod 4$ and $P \equiv 1 \pmod 4$ at the same time, which is impossible. If all $a_i \equiv 1 \pmod 4$, then $P = a_1a_2 \cdots a_n \equiv 1 \pmod 4$, so $a_i + P \equiv 1+1 \equiv 2 \pmod 4$, as claimed. If all $a_i \equiv -1 \pmod 4$, then $P = a_1a_2 \cdots a_n \equiv -1 \pmod 4$ (since $n$ is odd), and $a_i + P \equiv -1 + (-1) \equiv 2 \pmod 4$, as claimed. All cases are exhausted and yield either $\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P) = 1$ or $\gcd(a_1^n + P, a_2^n + P, \cdots, a_n^n + P) = 2$, so we are done. $\blacksquare$
11.05.2024 23:10
28.06.2024 19:47
Let $\gcd(a_1,a_2,\cdots,a_n)=d$, and $a_i=dx_i, P=d^nP'$. Then $$\gcd(a_1^n+P, a_2^n+P, \cdots, a_n^n+P)=d^n\gcd(x_1^n+P', x_2^n+P', \cdots, x_n^n+P') \leq 2d^n$$so we want to prove $$\gcd(x_1^n+P', x_2^n+P', \cdots, x_n^n+P') \leq 2$$Now suppose we have a power of a prime $p^e$ such that $p^e|x_i^n+P',x_j^n+P'$, then $x_i^n \equiv x_j^n \mod p^e$ and since they are coprime we must have $\gcd(p,x_i,x_j)=1$. But note that $p^e|x_i^n+P'=x_i(x_i^{n-1}+\frac{P'}{x_i})$ and $p$ is coprime with $x_i$, so $p^e|x_i^{n-1}+\frac{P'}{x_i}, x_j^{n-1}+\frac{P'}{x_j}$ which means \begin{align*} x_i^{n-1}+\frac{P'}{x_i} &\equiv x_j^{n-1}+\frac{P'}{x_j} \mod{p^e} \\ x_i^{n}x_j + P'x_j &\equiv x_j^nx_i+P'x_i \mod{p^e} \\ x_j^n(x_j-x_i) &\equiv P'(x_i-x_j) \mod{p^e} \end{align*}If $x_j - x_i $ is relatively prime to $p^e$ then $x_j^n \equiv -P' \equiv -x_1\cdots x_n \mod{p^e}$. Taking the product over all $x_1^n, \ldots, x_n^n$ we get $x_1^n\cdots x_n^n \equiv -x_1^n\cdots x_n^n \mod{p^e} \implies 1 \equiv -1 \mod{p^e} \implies p^e=2$. Thus in this case the greatest common prime dividing all $x_i^n+P'$ is $2$. If $x_j-x_i $ is not relatively prime to $p^e$. If $x_j-x_i \equiv 0 \mod{p^e}$ then since we know this holds for every pair of $(i,j)$, every integer in the sequence must be the same modulo $p^e$, which means $x_i^n + P' \equiv x_i^n + x_i^n \equiv 2x_i^n \equiv 0 \mod{p^e}$. Since $p \nmid x_i$, $p=2$, and $e=1$ so $p^e=2$ and no higher powers of 2 is achievable. If $x_j-x_i \equiv p^tk \mod{p^e}$ then there exists $t \leq e$ such that $x_i \equiv x_j \mod{p^t}$ which means every integer in the sequence must be the same modulo $p^t$. Thus $x_i^n + P' \equiv x_i^n + x_i^n \equiv 2x_i^n \mod{p^t}$, and since $p\nmid x_i$, we have $p^t=2$ and no higher powers of $2$ is achievable.
12.08.2024 02:49
The inequality is homogeneous, so assume WLOG that $\gcd(a_1,\dots,a_n)=1$. Now it suffices to prove that $\gcd (a_1^n+ P, a_2^n + P, \dots, a_n^n + P)\le 2$. When $n=1$, $a_1=1$ because $\gcd(a_1,\dots,a_n)=1$ so $2\le 2$, as desired. Therefore, assume $n\ge 2$. If some prime $p>2$ divides $\gcd (a_1^n+ P, a_2^n + P, \dots, a_n^n + P)$, then $a_i^n\equiv -P\pmod{p}$ for all $i$. If any $a_i\equiv 0\pmod{p}$, then $P\equiv 0\pmod{p}$, so $a_i\equiv 0\pmod{p}$ for all $i$, which is not allowed because $\gcd(a_1,\dots,a_n)=1$. Because $a_i\not\equiv 0\pmod{p}$, we can multiply the congruences together to get $P^n\equiv -P^n\pmod{p}$ but this means that $P\equiv 0\pmod{p}$, which is clearly impossible. Now it suffices to prove that $4\not|\gcd (a_1^n+ P, a_2^n + P, \dots, a_n^n + P)$. If $P$ is odd, then $a_i\equiv \pm1\pmod{4}$ for all $i$. Since $n$ is odd, this means that $a_i^n\equiv a_i\equiv -P\pmod{4}$ for all $i$. This means that all $a_i$ are the same in $\pmod{4}$, so $P\equiv a_1^n\equiv a_1\equiv -P\pmod{4}$, which is clearly impossible for odd $P$. Otherwise, $P$ is even. If all $a_i$ are even, then $\gcd(a_1,\dots,a_n)\ne 1$. Therefore some $a_i$ is odd so some $a_i^n+P$ is odd so $4\not|\gcd (a_1^n+ P, a_2^n + P, \dots, a_n^n + P)$, as desired.
14.09.2024 19:56
Let $\gcd(a_1, \dots, a_n) = d$, and define $b_i = \frac{a_i}{d} \forall i$. Further, let $Q = b_1 \cdots b_n$. Then the problem statement is equivalent to $$\gcd(b_1^n + Q, b_2^n + Q, \dots, b_n^n + Q) \le 2\gcd(b_1, \dots, b_n)^n = 2.$$ Claim 1: $\gcd(b_1^n + Q, b_2^n + Q, \dots, b_n^n + Q)$ is a power of 2. Proof: Assume FtSoC that $b_1^n + Q, b_2^n + Q, \dots, b_n^n + Q$ have a common odd prime factor $r$. Then we have the equations $$b_i^n \equiv -(b_1b_n \dots b_n) \pmod{r}.$$Taking the cyclic product, $$\prod_i b_i^n \equiv (-1)^n (\prod_i b_i)^n \equiv (-1)^n \prod_i b_i^n \equiv -\prod_i b_i^n \pmod{r}$$$$ \implies r \mid (b_1b_n \dots b_n)^n$$$$\implies r \mid b_1 \dots b_n.$$But now, for any $j$, we have $$b_j^n \equiv -(b_1b_n \dots b_n) $$$$\equiv 0 \pmod{r}$$$$\implies r \mid b_j^n$$$$\implies r \mid b_j.$$So $b_1, \dots, b_j$ have the common factor $r$, a contradiction to the fact that they are coprime. $\square$ Claim 2: $4 \nmid \gcd(b_1^n + Q, b_2^n + Q, \dots, b_n^n + Q)$. Proof: Assume otherwise, i. e. $4 \mid b_i^n - Q \forall i$. Note that the $b_i$ are all odd; indeed, if any $b_i$ were to be even, then so would be $Q$; and therefore all the $b_i$, contradicting the fact that they are coprime. Now, we have the equations as in the proof of the first claim, culminating in $ 2 \prod_i b_i^n \equiv 0 \pmod{4} \implies \prod_i b_i^n \equiv 0 \pmod{2}$, so one of the $b_i$ is even, contradiction. Therefore, we have $\gcd(b_1^n + Q, b_2^n + Q, \dots, b_n^n + Q) \in \{ 1, 2 \}$, which is what we wanted. $\square$
22.10.2024 18:09
Note that the power of each term is $n$. WLOG assume that: $\gcd(a_1, a_2, \cdots, a_n)=1$. Thus, it suffice to show that: $$\gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)\le 2.$$Let $d = \gcd(a_1^n+P,a_2^n+P,\dots, a_n^n+P)$. If $d \le 2$, then we are done. Assume that $d \ge 3$. Claim: $\gcd(d, P)=1$ Proof: Then, let $p$ be an odd prime such that: $p|d$ which implies: $p|a_k^n+P$. If $p|P$, then we have: $p|a_k^n \implies p|a_k$, but this contradicts the fact that: $\gcd(a_1, a_2, \cdots, a_n)=1$. Thus, $p \nmid P$ and therefore $\gcd(d, P)=1$. Since $d|a_k^n+P$, we have: $a_k^2 = d t_k -P$ for some integer $t_k$. Taking the product over $k=1$ till $k=n$, we have: $P^n = (d t_1 - P)(d t_2-P) \cdots (d t_n-P)$. Considering $\pmod d$, we have: $2 P^n \equiv 0 \pmod d$. Since $\gcd(d, P)=1$, we have $d|2$ and therefore $d \le 2$.
16.11.2024 17:29
Unreasonably long writeup because why not? This is a TST-style writeup so do not judge me. First of all we let, \[\epsilon=gcd(a_1,a_2,\dots,a_n)\]which leads us to a simplification through letting $a_i=\epsilon \cdot b_i$ as: \[gcd(a_1^n+P,a_2^n+P,\dots,a_n^n+P)=gcd\left(\epsilon^n b_1^n+\epsilon^n \prod_{i=1}^{n} b_i, \epsilon^n b_2^n+\epsilon^n \prod_{i=1}^{n} b_i, \dots, \epsilon^n b_n^n+\epsilon^n \prod_{i=1}^{n} b_i\right)\]\[=\epsilon^n gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right)\]by basic simplification of greatest common divisor function. Now basically our original statement is equivalent to proving that for $gcd\left(b_1,b_2,\dots,b_n\right)=1$ we have that, \[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right) \le 2 \ \ \ \ \ \ \ (1)\]considering some prime $p \ne 2$ such that $p \mid b_j^n+\prod_{i=1}^{n}b_i$ holding for each $j$ that is, a brief statement assuming the opposite. Lemma : $p \nmid b_j$ for any $j$. Proof : For the sake of contradiction, say for some point $j$ we have $p \mid b_j$ immediately consider all the other $k \ne j$ type statements which would give us $p \mid b_k^n \iff p \mid b_k$ by Euclid's Lemma again, and finally $p \mid b_i$ for each $i$ contradicting $gcd(b_1,b_2,\dots,b_n)=1$. Q.E.D. On the other hand, \[b_1^n \equiv b_2^n \equiv \dots \equiv b_n^n \equiv -\prod_{j=1}^{n}b_j \ (mod \ p)\]and if we take product of all the individual statements, \[\left(\prod_{i=1}^{n}b_i\right)^n \equiv \left(-\prod_{i=1}^{n}b_i\right)^n \ (mod \ p) \implies 2\left(\prod_{i=1}^{n}b_i\right) \equiv 0 \ (mod \ p)\]due to the fact that $n$ is odd. However since our assumption now is $p \ne 2$ we must have \[p \mid 2\left(\prod_{i=1}^{n}b_i\right) \implies p \mid \left(\prod_{i=1}^{n}b_i\right)\]but by consecutive Euclid's Lemma application we must have that $p \mid b_j$ for some $j$ which by the above lemma creates contradiction to our conditions. Now finally we must only have $p=2$ as the sole divisor over all such statements. The only thing we need to control is the power of $2$. We consider a new condition to see what happens assuming that: \[4 \mid \left(b_j^n+\prod_{i=1}^{n} b_i\right) \ \forall j\]now if any $2 \mid b_a$ for some $a$ then immediately due to, \[4 \mid b_j^n+\prod_{i=1}^{n}b_i\]such that $j \ne a$ gives us $2 \mid b_i \ \forall i$ and again contradicts the $gcd(b_1,b_2,\dots,b_n)=1$ condition. Finally, each $b_i$ becomes odd. Now suppose we have that, \[\prod_{i=1}^{n}b_i \equiv 1 \ (mod \ 4)\]then we have $b_j^n \equiv -1 \ (mod \ 4)$ for each $j$ possible iff $b_j \equiv (-1) \ (mod \ 4)$ since $n$ is odd and $x \equiv 1 \ (mod \ 4) \implies x^n \equiv 1 \ (mod \ 4)$ for any $n$. However then, \[1 \equiv \prod_{i=1}^{n}b_i \equiv (-1)^n \equiv (-1) \ (mod \ 4)\]contradicting our assumption. On the other hand, we might have: \[\prod_{i=1}^{n}b_i \equiv (-1) \ (mod \ 4)\]in which case $b_j^n \equiv 1 \ (mod \ 4)$ for each $j$ possible iff $b_j \equiv 1 \ (mod \ 4)$ when we combine the following facts: \begin{align*} &a \equiv (-1) \ (mod \ 4) \implies a^n \equiv (-1) \ (mod \ 4) \ \ \noindent \text{for odd n} \\ &a \equiv 1 (mod \ 4) \implies a^n \equiv 1 \ (mod \ 4) \ \ \forall n \end{align*}Thus we have that, \[(-1) \equiv \prod_{i=1}^{n}b_i \equiv 1^n \equiv 1 \ (mod \ 4)\]which contradicts our assumption again. Hence we have covered all possible cases and deduced that first, \[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right)=2^a\]for some $a$ and later that $a \le 1$ and thus \[gcd\left(b_1^n+\prod_{i=1}^{n} b_i,b_2^n+\prod_{i=1}^{n} b_i, \dots,b_n^n+\prod_{i=1}^{n} b_i\right) \mid 2\]which in combination with $a \mid b \implies a \le b \ \forall (a,b) \in \mathbb{Z^{+}}$ gives us our required $(1)$ and thus we are done.
05.12.2024 00:12
Scale down $a_1, a_2, \dots, a_n$ until their GCD is $1$. It suffices to show that if $k$ divides all of the terms on the left hand side, $k=2$. We have $a_i^n \equiv -P \bmod{k}$ for all $i$, so \[-P^n = (-P)^n \equiv a_1^n a_2^n \dots a_n^n = P^n \pmod{k}.\]If $P$ shared any prime factor with $k$, this prime factor would also be shared by all of $a_1, \dots, a_n$ which is a contradiction. Therefore we can divide both sides by $P^n$ to get $-1 \equiv 1 \pmod{k}$, hence $k=2$.
10.12.2024 12:49
Let $d = \gcd(a_1, \dots, a_n)$, $a_i = dx_i$ and $Q = x_1 \dotsm x_n$ so that it suffices to prove $\gcd(x_1^n + Q, \dots, x_n^n + Q) \leq 2$ as then \begin{align*}\gcd(a_1^n + P, \dots, a_n^n + P) = d^n \gcd(x_1^n + Q, \dots, x_n^n + Q) \leq 2d^n = 2\gcd(a_1,\dots, a_n)^n.\end{align*}To this end, suppose that an odd prime $p$ divides $x_i^n + Q$ for all $i$. Clearly we now have $-Q \equiv x_1^n \equiv \dots \equiv x_n^n \pmod{p}$, and so \[Q^n \equiv x_1^n \dotsm x_n^n \equiv \underbrace{(-Q) \dotsm (-Q)}_{n \text{ times}} \equiv -Q^n \pmod{p}.\]This implies that $p \mid Q$ and so that $p \mid x_i$ for some $i$. From this it is evident that $p \mid x_i$ for all $i$, contradicting the fact that $\gcd(x_1, \dots, x_n) = 1$.