GCD of sums of consecutive divisors

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

GCD of sums of consecutive divisors

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: EGMO 2025 P1

The post below has been deleted. Click to close.

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

267 posts

#1 h Apr 13, 2025, 1:03 PM • 3 Y

Y by farhad.fritl, cubres, aqusha_mlp12

For a positive integer $N$ , let $c_1 < c_2 < ... < c_m$ be all the positive integers smaller than $N$ that are coprime to $N$ . Find all $N \ge 3$ such that
$gcd(N, c_i + c_{i + 1}) \neq 1$ for all $1 \le i \le m - 1$ .

Z Y

The post below has been deleted. Click to close.

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

Marius_Avion_De_Vanatoare

55 posts

Marius_Avion_De_Vanatoare

#2 h Apr 13, 2025, 1:14 PM

Y by

The only working $N$ are even numbers and powers of $3$ . It is clear that for even numbers all coprime numbers are odd, and for powers of $3$ all consecutive coprime numbers are different mod 3.
Now, to show that these are the only working, if $N$ is even the problem is solved. If $N$ is odd, as $1$ and $2$ are coprime with it, we have that $N$ is divisible by 3.
Next, let $N=3^{\alpha}x$ for $x$ not divisible by 3. I will show $x$ is 1, else consider the numbers coprime with $N$ which are closest to $x$ , these are either $x+1$ and $x-2$ if $x$ is 1 mod 3, or $x-1$ and $x+2$ if $x$ is 2 mod 3.
So their sum, which is either $2x-1$ if $x$ is 1 mod 3 or $2x+1$ else, which can't have a common divisor with $N$ .

Z Y

The post below has been deleted. Click to close.

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

9038 posts

#3 h Apr 13, 2025, 2:04 PM

Y by

It was posted here before.

Z Y

The post below has been deleted. Click to close.

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

86 posts

#4 h Apr 13, 2025, 3:27 PM

Y by

Let’s consider two cases depending on whether $N$ is even or odd:

Case 1: $N$ is even.
In this case, any number coprime with $N$ will be odd. Therefore, the sum $C_i + C_{i+1}$ will be even, which means the GCD of $N$ and $C_i + C_{i+1}$ will always be greater than 1. So, the condition is satisfied for all even $N$ .

Now, let’s analyze the odd case.

Let $C_1 = 1$ , $C_2 = 2$ . According to the problem condition, $\gcd(N, 3) > 1$ .
This implies $N$ must be divisible by 3. Trying some small odd values divisible by 3, we see that $N = 3, 9, 27$ satisfy the condition, while $N = 15, 21$ do not.

So we explore two subcases:
Case 2.1: $N = 3^a$

In this form, every number congruent to 1 or 2 mod 3 is coprime with $N$ .
Let $C_j = 3t + 1$ , then $C_{j+1} = 3t + 2$ , so the sum $C_j + C_{j+1} = 3t + 1 + 3t + 2 = 6t + 3$ , which is divisible by 3.
Similarly, for $C_j = 3t + 2$ , we have $C_{j+1} = 3t + 4$ , so $C_j + C_{j+1} = 6t + 6$ , again divisible by 3.
Thus, any $N = 3^a$ , where $a$ is a positive integer, satisfies the condition.

Case 2.2: $N = 3^a \cdot k$ , where $\gcd(k, 3) = 1$ .
Then $k \equiv 1$ or $2 \mod 3$ .

Case 2.2.1: Let $k \equiv 2 \mod 3$ .
Since $N$ is odd, $k \equiv 5 \mod 6$ , so write $k = 6t + 5$ .
There exists an integer $h$ such that $C_h = 6f + 4$ .
Here, $\gcd(6f + 4, 3) = 1$ , and $\gcd(6f + 5, 6f + 4) = 1$ .
Then $C_{h+1} = 6f + 7$ , and clearly $\gcd(6f + 7, 6f + 5) = 1$ , $\gcd(6f + 7, 3) = 1$ .
Now the sum $C_h + C_{h+1} = 12f + 11$ .
Then,
$\gcd(12f + 11, N) = \gcd(12f + 11, 3^a \cdot (6f + 5)) = \gcd(12f + 11, 6f + 5)$ $= \gcd(6f + 6, 6f + 5) = 1 \quad \text{(Contradiction!)}$
Case 2.2.2: $k \equiv 1 \mod 3$ , i.e., $k = 6f + 1$ .
Then take $C_h = 6f - 1$ , and $C_{h+1} = 6f + 2$ .
Now:
$\gcd(N, C_h + C_{h+1}) = \gcd(12f + 1, N) = \gcd(12f + 1, 6f + 1) = \gcd(6f, 6f + 1) = 1 \quad \text{(Contradiction!)}$
Final Answer:
1) $N = 2k$ , for any natural number $k > 1$
2) $N = 3^a$ , for any natural number $a$

Z Y

G

H

=

© 2025 AoPS Incorporated

a