[EGMO3] GCD Bounds

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

[EGMO3] GCD Bounds

G H J

Reveal topic tags

greatest common divisor

L

G H BBookmark kLocked kLocked NReply

Source: EGMO 2015, Problem 3

The post below has been deleted. Click to close.

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

2105 posts

#1 h Apr 16, 2015, 1:32 PM • 3 Y

Y by Amir Hossein, Adventure10, Mango247

Let $n, m$ be integers greater than $1$ , and let $a_1, a_2, \dots, a_m$ be positive integers not greater than $n^m$ . Prove that there exist positive integers $b_1, b_2, \dots, b_m$ not greater than $n$ , such that $\gcd(a_1 + b_1, a_2 + b_2, \dots, a_m + b_m) < n,$ where $\gcd(x_1, x_2, \dots, x_m)$ denotes the greatest common divisor of $x_1, x_2, \dots, x_m$ .

This post has been edited 2 times. Last edited by v_Enhance, Apr 18, 2015, 12:59 PM
Reason: latex cleanup, use source field

Z K Y

The post below has been deleted. Click to close.

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

824 posts

andria

#4 h Apr 16, 2015, 3:17 PM • 5 Y

Y by ferma2000, Amir Hossein, translate, Adventure10, Mango247

Easy problem:
My solution: we consider all of the choices of the $m$ -tuples $(b_1, b_2, ..., b_m)$ (the number of them is clearly $n^m$ ) and assume that $d_1,d _2,...,d_{n^m}$ are the greatest common divisors of $(a_1+b_1,..., a_m+b_m)$ for different $m$ -tuples $(b_1,..., b_m)$ . Assume, for sake of contradiction, that $d_i\ge n$ for every $1\le i \le n^m$ . Now assume that for two $m$ -tuples $(b_1, b_2,..., b_m), (c_1,c_2,..., c_m)$ we have $d_i=d_j$ ; then, because these two m-tuples are different, there exists $k$ such that $b_k\neq c_k$ . Then $d_i\mid a_k+b_k, a_k+c_k \longrightarrow d_i\mid |b_k-c_k| \le n-1$ so $d_i\le n-1$ , contradiction. So all of them are distinct, and so one of them, call it $d$ , is greater than or equal to $n^m+n$ , but $d\mid a_k+b_k-a_\ell-b_\ell < n^m+n$ , contradiction. DONE

This post has been edited 1 time. Last edited by mavropnevma, Apr 16, 2015, 3:35 PM
Reason: Corrected some indexing errors.

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#5 h Apr 16, 2015, 3:42 PM • 10 Y

Y by FlakeLCR, DrMath, Tawan, Amir Hossein, Centralorbit, hannahptl, vsamc, Math_Doctor., Adventure10, Mango247

Your last inference is not correct. First, you can only infer $d \geq n^m+n-1$ , and then, what if $a_k+b_k - a_\ell - b_\ell = 0$ ? In fact, if for all $k$ we have $a_k+b_k =d$ , which is possible, since the upper bound on $a_k+b_k$ is $n^m + n$ , there is no contradiction.

Z K Y

The post below has been deleted. Click to close.

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

487 posts

#6 h Apr 16, 2015, 3:59 PM • 4 Y

Y by Tawan, Amir Hossein, Adventure10, Mango247

Like previous post, consider all $n^m$ values of the gcd. Suppose they are all $\ge n$ . All of these must be distinct, as otherwise, $d \mid |(a_k+b_k)-(a_k+c_k)| = |b_k-c_k| < n$ , which is impossible. If all of them are distinct $\exists$ $d \ge n^m+n-1$ . Then, $\forall k \in [1,m]$ , $d|a_k+b_k \implies a_k+b_k = d$ (since other multiples are too large). So, $a_k = d-b_k \ge n^m+n-1-n = n^m-1$ . So, all of the $a_i$ 's are $n^m-1$ or $n^m$ . If they are not all equal, taking $b_i = 1$ for all $i$ , gives us a gcd of $1$ , since both $n^m$ and $n^m+1$ are present amongst $a_i+b_i$ , a contradiction. Suppose that they are all equal. Take $b_i = i$ , to again get a gcd of $1$ , another contradiction.

Z K Y

The post below has been deleted. Click to close.

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

28 posts

#7 h Apr 16, 2015, 4:11 PM • 2 Y

Y by Amir Hossein, Adventure10

Suppose we have $a_i = a_j=a$ for some $i,j$ , than take $b_i=1$ and $b_j=2$ . We have $gcd(a_1+b_1 , \ldots , a_m+b_m) \leq gcd(a_i + b_i , a_j+ b_j) = gcd(a+1,a+2)=1 < n$
So we can suppose that all the $a_i$ are distinct.
Suppose also we have $a_i \geq a_j$ and $a_i - a_j = k \leq n$ for some $i,j$ , than take $b_i=n-k+1$ and $b_j=n$ . We have $gcd(a_i+b_i, a_j+b_j)= gcd(a_j+n+1,a_j+n)=1 < n$
So we can suppose that $| a_i - a_j| \geq n+1$ for all $i,j$
Define $d_1 , d_2 , \ldots , d_{n^m}$ as the gcd we can have for all our $n^m$ choices of $b_i$ 's . Suppose WLOG $a_1 < a_2 < \ldots < a_m$ . We have $a_{1} \leq a_m - n - 1 \leq n^m - n - 1$ so $a_1 + b_1 \leq n^m -1$ in any case . But $d_i \leq a_1 + b_1 \leq n^m -1$ for all $i$ . So $1 \leq d_i \leq n^m - 1$ . Now since there are $n^m$ $d_i$ 's for pigeonhole there must be two of them equal.
Suppose $d_r=d_s$ , now there must be an $a_t$ that has different $b_i$ 's (suppose $b_l > b_k$ ) . We have $d_r \mid a_t + b_l$ and $d_s \mid a_t + b_k$ , so $d_r \mid b_l - b_k$ and finally $d_r \leq b_l - b_k \leq n-1 < n$ .

Z K Y

The post below has been deleted. Click to close.

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

6877 posts

#8 h Apr 18, 2015, 12:55 PM • 6 Y

Y by r31415, rafayaashary1, Amir Hossein, SSaad, Adventure10, Mango247

This is a toddler's version of USAMO 2014/6. Far too easy for its position, considering I solved it in my near-sleep.

Assume not. By varying $1 \le b_i \le n$ , we obtain an $n \times \dots \times n$ lattice on which we can label each point with the corresponding GCD. Observe that
(a) each GCD has $\ge n$ , and hence can appear at most once in the grid.
(b) at most one label is divisible by $n$ . (This small optimization is necessary to get the bound to go through; the content is in (a).)
With these two observations, we find that the some label must exceed $n + n^m-1 + n^{m-1}$ with the extra $n^{m-1}$ term coming from (b).

Thus, for some $a_i$ and $1 \le \epsilon \le n$ we have $a_i \ge n^m + n^{m-1} + n - 1 - \epsilon \ge n^m + n^{m-1} - 1 > n^m$ where in the last step we have used $n,m \ge 2$ . Contradiction.

Z K Y

The post below has been deleted. Click to close.

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

15142 posts

#10 h Apr 18, 2015, 2:25 PM • 21 Y

Y by Aiscrim, pi37, r31415, codyj, FlakeLCR, rafayaashary1, DrMath, Tawan, rmtf1111, Amir Hossein, Centralorbit, Mathcollege, hannahptl, aops29, Mathasocean, vsamc, CancerPatient, Math_Doctor., ILOVEMYFAMILY, pavel kozlov, Adventure10

The following solution - belonging to a friend of mine - shows that it is enough to work with $1\leq b_k \leq 2$ for $1\leq k \leq m$ .

Assume the assertion to be false, i.e. for any choice of $1 \leq b_1,b_2,\ldots,b_m \leq n$ to get $\gcd(a_1 + b_1, a_2 + b_2, \ldots, a_m + b_m) \geq n$ .
Consider now the $m$ -tuples $(1,1,1,\ldots,1,1), (1,2,1,\ldots,1,1), \ldots, (1,1,1,\ldots, 2,1), (1,1,1,\ldots,1,2)$ and use each of them as $(b_1,b_2,\ldots,b_m)$ . It is obvious the $m$ corresponding $\gcd$ 's, assumed larger than or equal to $n$ , are pairwise coprime. All these $m$ $\gcd$ 's however divide $a_1+1$ , so $a_1+1\ge n(n+1)\cdots (n+m-1) > n^m+1.$ contradicting $a_1 \le n^m$ .

This post has been edited 1 time. Last edited by mavropnevma, Apr 18, 2015, 2:26 PM

Z K Y

The post below has been deleted. Click to close.

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

977 posts

#11 h Apr 18, 2015, 8:49 PM • 3 Y

Y by Amir Hossein, Adventure10, Mango247

I believe that combining mavropnevma and vEhance's ideas an absurd bound on $a_i$ can be used. Let $b_1=1$ and then $b_i$ vary from $1$ to $n$ with $2\le i \le m$ . Now suppose that $\gcd(a_1 + b_1, a_2 + b_2, \ldots, a_m + b_m) \geq n$ for all all n-tuples of $(b_1,b_2,...,b_m)$ that satisfy the conditions given in the previous sentence. The corresponding $gcd$ 's are clearly all distinct as has been shown earlier in the thread. But all the $gcd$ 's divide $a_1+1$ so then $a_1+1\ge(n)(n+1)...(n+n^{m-1}-1)>n^{n^{m-1}}+1$ so all we need was $a_1 \le n^{n^{m-1}}$ which is far far stronger than the condition given.

Z K Y

The post below has been deleted. Click to close.

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

1980 posts

#12 h Sep 22, 2016, 2:47 PM • 4 Y

Y by Tawan, Amir Hossein, TheCosineLaw, Adventure10

Nice and easy.

Let us define $T=n(n+1)\dots(n+m-1)$ and fix $b_1=1$ and vary $b_2,\dots,b_m$ . We have $n^{m-1}$ different $(m-1)$ tuples $(b_2,\dots,b_m)$ and each gives a gcd at least $n$ . If two of them give the same gcd $g$ , then $g \mid (a_i+b_i)-(a_i+b_j)$ , but $|b_i-b_j| \le n-1$ , a contradiction! We see that all these gcd's are pairwise distinct and so, $a_1+1 \ge L=\operatorname{lcm}\left(n,n+1,\dots,n+n^{m-1}-1\right)>n^m+1$ where the last inequality follows since for any prime $p<m+n$ , $v_p(L) \ge \log_p(L)-1>(n^{m-1}-(m-1))\log_p(m+n)-1 \ge n^{m-1}-m$ and $v_p(T)=v_p((m+n-1)!)-v_p((n-1)!)<\frac{m+s_p(n-1)}{p-1}<\frac{m+\log_p(n-1)}{p-1}$ and we clearly see that $T \mid L$ . Thus, $L \ge T=n(n+1)\dots(n+m-1)>n^m+1$ and the last inequality holds.

Of course, it can be done much more easily

Z K Y

The post below has been deleted. Click to close.

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

66 posts

neel02

#13 h Jul 5, 2018, 9:45 AM • 2 Y

Y by Adventure10, Mango247

Too much easy as #3 !

Sorry if I have same sol. with @above !

Consider all possible [ namely $n^m$ ] $m$ tupples of $(b_i)$ 's . Note that all the $n_m$ gcd's are different with the assumption that all of the gcds are greater than $n$ . For minimality we can assume that they are $m$ consecutive no. from $n$ [Obviously avoiding the stronger bound for the sake of the prob. !

] Pick a $a_i$ such that all $b_j$ added to it is 1 . So
$a_y+1 \geq n(n+1)...(n+m-1)>n_m+1$ so
$a_y>n^m$ a contradiction for the given $a_i$ 's !

Z K Y

The post below has been deleted. Click to close.

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

1614 posts

yayups

#14 h Oct 5, 2018, 11:42 PM • 2 Y

Y by Adventure10, Mango247

In fact the $n^m$ can be improved to $n^{n^{m-1}}-1$ . And even at that its way too easy (even for like #1 in my opinion).

Assume the statement is false. Suppose $(b_1,\ldots,b_m)\ne(b_1',\ldots,b_m')\in[n]^m$ . Then, we have $b_i\ne b_i'$ for some $i$ , so then
$\gcd(\gcd(a_1+b_1,\ldots,a_m+b_m),\gcd(a_1+b_1',\ldots,a_m'+b_m'))\mid\gcd(a_i,a_i+1)=1,$ so the two gcds are coprime. Thus, considering all $(b_1,\ldots,b_m)\in[n]^m$ with $b_1$ fixed to be $1$ , we see that there are $n^{m-1}$ pairwise coprime numbers, all at least $n$ , that divide $a_1+1$ . Thus, $a_1\ge n^{n^{m-1}}-1$ , which is a contradiction, as desired.

Z K Y

The post below has been deleted. Click to close.

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

1218 posts

#15 h Oct 6, 2018, 5:13 PM • 2 Y

Y by Adventure10, Mango247

Nice problem. Here's my solution: Suppose that no such $n$ -tuple of positive integers exists. Consider all $n^m$ possibilities of the sets $<b_i>$ . Let the corresponding GCD's be $g_1,g_2, \dots,g_{n^m}$ . According to our assumption, we have $g_i \geq n \text{ } \forall i \in \{1,2, \dots,n^m \}$ .

Claim All the $g_i$ 's are distinct.

PROOF: Suppose, to the contrary, $g_p=g_ q$ for some sets $<b_i>$ and $<B_i>$ . Then for these two sets to be distinct, atleast one of their corresponding elements must be distinct. Let's say that we have $b_k \neq B_k$ for some $k \in \{1,2, \dots,n \}$ . WLOG assume that $B_k>b_k$ . Then $g_p \mid a_k+b_k$ and $g_q \mid a_k+B_k$ . As $g_p=g_q$ , so we have $g_p \mid B_k-b_k$ . But the maximum and minimum values that any element of the $n^m$ sequences can take is $n$ and $1$ respectively, which gives $B_k-b_k \leq n-1$ . This in turn gives $g_p \leq B_k-b_k \leq n-1$ , which contradicts our original assumption that $g_i \geq n \text{ } \forall i \in \{1,2, \dots,n^m \}$ . Thus, all $g_i$ 's are distinct. $\Box$

Lemma If any two $a_i$ 's are same, then the required set $<b_i>$ can be found.

PROOF: Just take the corresponding $b_i$ 's as $1$ and $2$ respectively, to get the GCD as 1. $\Box$

Return to the problem at hand. As we have $n^m$ distinct integers greater than or equal to $n$ , we must have $g_s \geq n^m+n-1$ for some $s \in \{1,2,\dots,n^m\}$ . Suppose $g_s$ is the GCD of the set $A=\{a_1+x_1,a_2+x_2,\dots,a_m+x_m\}$ . Then $g_s \mid a_i+x_i$ for every $i \in \{1,2,\dots,m\}$ , which means $g_s \leq a_i+x_i \leq n^m+n$ . This gives that $g_s$ is either $n^m+n$ or $n^m+n-1$ . Now, suppose not all elements of $A$ are the same, i.e. $a_i+x_i \neq a_j+x_j$ for some $i,j \in \{1,2,\dots,m\}$ . WLOG assume that $a_i+x_i>a_j+x_j$ . Then $g_s \mid (a_i+x_i)-(a_j+x_j)$ , which means $g_s \leq (a_i-a_j)+(x_i-x_j) \leq (n^m-1)+(n-1)=n^m+n-2$ , which is not possible. So all the elements of the set $A$ are equal, and so they must be equal to their GCD, i.e. $g_s$ . We now make two cases:

CASE-1 $(g_s=n^m+n)$
This means that $a_i=n^m$ and $x_i=n$ $\forall i \in \{1,2,\dots,m\}$ . But then we are done by our Lemma.

CASE-2 $(g_s=n^m+n-1)$
This means that $a_i=n^m$ or $a_i=n^m-1$ $\forall i \in \{1,2,\dots,m\}$ . We first consider $m>2$ . In this case, we are once again done by our Lemma, as atleast two of the $a_i$ 's are same. Now we take $m=2$ . Then WLOG we can take $a_1=n^2-1$ and $a_2=n^2$ . Then taking $b_1=b_2=1$ , we have $\gcd(a_1+b_1,a_2+b_2)=\gcd(n^2,n^2+1)=1$ , which is definitely less than $m=2$ . So we are done when $m=2$ also.

Thus, we get that such a required set $<b_i>$ always exists. Hence, done. $\blacksquare$

This post has been edited 9 times. Last edited by math_pi_rate, Dec 27, 2018, 9:29 AM
Reason: Fixed a small mistake as pointed in PM

Z K Y

The post below has been deleted. Click to close.

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

1566 posts

#16 h Dec 25, 2018, 2:42 PM • 3 Y

Y by brokendiamond, AlastorMoody, Adventure10

Quite easy for a P3, although really nice!

socrates wrote:

Let $n, m$ be integers greater than $1$ , and let $a_1, a_2, \dots, a_m$ be positive integers not greater than $n^m$ . Prove that there exist positive integers $b_1, b_2, \dots, b_m$ not greater than $n$ , such that $\gcd(a_1 + b_1, a_2 + b_2, \dots, a_m + b_m) < n,$ where $\gcd(x_1, x_2, \dots, x_m)$ denotes the greatest common divisor of $x_1, x_2, \dots, x_m$ .

Since $b_i \in \{1, \cdots n\},$ hence we have the $n^m$ vectors $(b_1, b_2, \cdots, b_m).$ Label them as $v_i$ where $i$ ranges from $1$ to $n^m.$ The ordering for the $i$ -s doesn't matter.
Now define
$\begin{align*} l_{v_i}:=gcd(a_1+b_1, \cdots, a_m+b_m) \quad \text{where }v_i \text{ is the vector associated with }(b_1, \cdots b_m) \end{align*}$ Claim 1: If $a_i =a_j$ for any $i < j,$ then the problem condition holds true.
Proof: Indeed, note that at least one of $l_{v_x}, l_{v_y}$ equals $1$ where $v_x=(b_1, \cdots ,b_i, \cdots ,b_j, \cdots ,b_m)$ and $v_y=(b_1, \cdots ,b_i+1, \cdots ,b_j, \cdots ,b_m),$ as $p|u$ and $p|u+1$ never holds true. Since $n>1,$ we are done here. $\square$

Now assume on the contrary that $l_{v_i} \ge n$ for all the $n^m$ vectors $v_i.$

Claim 2: We cannot have $l_{v_i} = l_{v_j}$ for any $i \ne j,$ i.e. all the $l_{v_i}$ are distinct numbers.
Proof: Assume on the contrary that $i \ne j$ and $l_{v_i} = l_{v_j}.$ Since $i \ne j,$ hence at least one of the $b_i$ -s is different for both, say $b_i \in v_i, b_i' \in v_j$ with $b_i \ne b_i'.$ Then
$l_{v_i}|a_i+b_i \text{ and }l_{v_i}|a_i+b_i' \implies l_{v_i}|b_i-b_i' \implies n \le l_{v_i} \le |b_i-b_i'|$ which is a contradiction as $1 \le b_i, b_i' \le n.$ $\qquad \qquad \quad \quad \quad \quad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \square$

Now note that $n \le l_{v_i} \le \max_{1 \le i \le n} \{a_i+b_i\} \le n^m +n$ for all $1 \le i \le n^m.$ If $l_{v_i}=n^m+n$ for some $v_i,$ then we must have $v_i=(n,n, \cdots ,n)$ (i.e. $b_1=\cdots=b_m=n)$ and $a_1=a_2=\cdots =a_m=n^m.$ Now since $m \ge 2,$ we have at least two equal numbers $a_1, a_2$ and so we have a contradiction by claim 1.

Thus,
$\{l_{v_1}, l_{v_2} \cdots, l_{v_{n^m}}\} \equiv \{n, n+1, \cdots ,n^m+n-1 \}, \text{ i.e. the two sets are equal}$ Hence $l_{v_i} =n^m+n-1$ for some $i.$ Then note that we must have $a_j \ge n^m-1$ for all $j,$ else if this is not true for some $j,$ then $n^m+n-1=l_{v_i} \le a_j+b_j < n^m-1+n,$ absurd. (here $b_j \in v_i).$ But we also have $n^m \ge a_j$ for all $j.$ Hence if $m \ge 3,$ then we will find two equal numbers among $\{a_1, a_2, a_3 \},$ and so we have a contradiction by claim $1.$

Thus we are left with the case when $m=2.$ Here, we must have $\{a_1, a_2\} \equiv \{n^2, n^2-1\}$ as $a_j \ge n^2-1$ was proved above. Suppose $a_1=n^2$ and $a_2=n^2-1.$ Then choose $b_1=b_2=n.$ Hence $gcd(a_1+b_1,a_2+b_2)=gcd(n^2+n, n^2+n-1)=1<2,$ a contradiction.

Hence, we will find a $v_i$ with $l_{v_i} <n,$ as desired. $\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \blacksquare$

This post has been edited 3 times. Last edited by Wizard_32, Dec 27, 2018, 9:08 AM
Reason: qed

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#17 h Sep 10, 2021, 12:23 PM • 2 Y

Y by centslordm, Mango247

So I got a slightly different problem where each of the $b_i$ were either $0$ or $1$ and nothing else was changed. The proof below is for that problem, but simply replacing every $1$ with a $2$ and $0$ with a $1$ (since $n\geq 2$ ), plus a tiny (like, 3 word) change proves a stronger version of the original problem.

Consider the $m$ $m$ -tuples
$(0,0,\ldots,0),(0,1,0,\ldots,0),\ldots,(0,0,0,\ldots,1)$ and consider the gcd when $(b_1,\ldots,b_m)$ is used as each of them. I claim that one of these gcds must be less than $n$ . Clearly these gcds all divide $a_1$ , and further they are all coprime, as if some $d>1$ divides $a_i+b_i$ , it doesn't divide both $a_i+b_i+1$ and $a_i+b_i-1$ . Hence the product of $\gcd(a_1+b_1,\ldots,a_m+b_m)$ over all $m$ choices for $(b_1,\ldots,b_m)$ must divide $a_1$ , so it must be at most $n^m$ . But if all the gcds are at least $n$ , since they're all coprime, all but one of them must be at least $n+1$ , so their product must be at least $n(n+1)^{m-1}>n^m$ , contradiction. $\blacksquare$

For the original problem where we replace $1$ with $2$ and $0$ with $1$ , everything is the same except the product of gcds must divide $a_1+1$ , so is at most $n^m+1$ , making the final inequality be $n(n+1)^{m-1}>n^m+1$ , which is certainly true as well since $n(n+1)^{m-1}\geq n^{m-1}(n+1)=n^m+n^{m-1}>n^m+1$ . With a little more work, for the case where $b_i \in \{0,1\}$ we can prove that the same bound holds even if $a_1,\ldots,a_m$ can be up to $n^{2^{m-1}}$ .
I actually feel like the version of the problem where the $b_i$ are restricted to either $0$ or $1$ is a bit easier: certainly the bound is "tighter", though still not asymptotically very different, but this restriction does narrow down the possible ways to approach this problem, and the fact that the gcds are always coprime is easier to find.

This post has been edited 1 time. Last edited by IAmTheHazard, Oct 30, 2021, 12:22 AM

Z K Y

The post below has been deleted. Click to close.

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

55 posts

#19 h Jan 15, 2023, 11:05 PM • 1 Y

Y by Mango247

We improve $n^m$ to $n^{2^{m-1}}$ and impose $b_i \in \{1, 2\}$ . Since $n, m \ge 2$ this is a stronger set of conditions.

We prove by induction on $i$ that for $i = 2, ..., m$ , we can find $(b_2, ..., b_i)$ such that $\gcd(a_1 + b_1, ..., a_i + b_i) \le n^{2^{m-i}}$ . Note that for $i = m$ this gives $\gcd(a_1 + b_1, ..., a_m + b_m) \le n$ . This proof holds regardless of whether $b_1 = 1$ or $b_1 = 2$ , and since $n$ divides at most one of $a_1 + 1, a_1 + 2$ , there exists $b_1$ such that $\gcd(a_1 + b_1, ..., a_m + b_m) < n$ .

Base case: $a_1 + b_1 \le n^{2^{m-1}}+2$ . Then consider $d_1, d_2 = \gcd(a_1 + b_1, a_2 + 1), \gcd(a_1 + b_1, a_2 + 2)$ . Since $\gcd(a_1 + 1, a_2 + 2) = 1, \gcd(d_1, d_2) = 1$ and $d_1 \mid a_1 + b_1, d_2 \mid a_1 + b_1 \Rightarrow d_1d_2 \mid a_1 + b_1 \Rightarrow a_1 + b_1 \ge d_1d_2$ . Hence by the averaging principle one of $d_1, d_2 \le (a_1 + b_1)^{1/2} \le (n^{2^{m-1}}+2)^{1/2}$ . Since $n, m \ge 2$ we can then find $\gcd(a_1 + b_1, a_2 + b_2) \le n^{2^{m-2}}$ .

Inductive step: Assume holds for $i-1$ . $\gcd(a_1 + b_1, ..., a_i + b_i) = \gcd(\gcd(a_1 + b_1, ..., a_{i-1} + b_{i-1}), a_i + b_i)$ . Since $\gcd(a_1 + b_1, ..., a_{i-1} + b_{i-1}) \le n^{2^{m-i+1}}$ , we proceed exactly as above to get $\gcd(a_1 + b_1, ..., a_i + b_i) \le (n^{2^{m-i+1}})^{1/2} = n^{2^{m-i}}$ . $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

5608 posts

#20 h Jan 18, 2023, 1:31 AM

Y by

We prove a stronger version (the original problem may be solved by replacing every $0$ with a $1$ and $1$ with a $2$ ) .

Let $n, m$ be integers greater than $1$ ,
and let $a_1, a_2, \dots, a_m$ be positive integers
not greater than $n^m$ .
Prove that there exist integers $b_1, b_2, \dots, b_m$
either zero or one and such that
$\gcd(a_1 + b_1, a_2 + b_2, \dots, a_m + b_m) < n.$
We claim that the gcd is less than $n$ for at least one possibility of the tuple $(b_1, b_2, \ldots, b_m)$ in the set $\{ (0,0,0\ldots, 0), (0,1,0,0 \ldots, 0), (0,0,1,0\ldots, 0) \ldots, (0,0,\ldots, 0,1)\}$
Suppose not and all such gcd's were at least $n$ . Notice that these $m$ gcds are pairwise coprime, so their product must divide $a_1$ . Since the gcd's are pairwise coprime, at least one of them must be greater than $n$ . This gives $a_1 > n^m$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

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

8866 posts

#21 h Dec 21, 2023, 10:49 PM

Y by

Assume otherwise. We will actually restrict $b_i \in \{0, 1\}$ for each $i$ . Associate with every $T = (b_1, b_2, \dots, b_m) \in \{0, 1\}^m$ a GCD $d_T = \gcd(a_1 + b_1, a_2+b_2, \dots, a_m + b_m)$ such that $d_T > n$ for every $T$ .

Note that any two $d_T$ must be relatively prime. It follows that $a_1 > \prod_{b_1 = 0 \text{ in } T} d_T > n^{2^{m-1}} > n^m$ which is an obvious contradiction.

This post has been edited 4 times. Last edited by HamstPan38825, Dec 25, 2023, 8:03 PM

Z K Y

The post below has been deleted. Click to close.

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

298 posts

#22 h Sep 9, 2024, 2:12 AM

Y by

Assume otherwise. Then we must have
$\begin{align*} \gcd(a_1, a_2, \dots, a_m) &\ge n \\ \gcd(a_1, a_2 + 1, \dots, a_m) &\ge n \\ \vdots \\ \gcd(a_1, a_2, \dots, a_m + 1) &\ge n, \\ \end{align*}$ but these GCDs are pairwise distinct (all coprime), so
$a_1 \ge n(n+1)\dots(n+m-1) > n^m$ which is a clear contradiction.
(technically just replace all the zeroes with twoes or something, it doesn't make any difference)

Z K Y

The post below has been deleted. Click to close.

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

651 posts

#23 h Apr 26, 2025, 4:42 AM

Y by

Assume taking $b_1 = b_2 = \dots = b_m = 0$ doesn't work. Then, take $b_1 = b_2 = \dots = b_m = 1.$ The pairwise $\gcd$ 's must all be greater than $n$ and relatively prime to each other, implying that $a_1\geq n(n + 1)\dots(n + m - 1) > n^m$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a