Why is the old one deleted?

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

Why is the old one deleted?

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.

64 posts

#1 h Apr 16, 2025, 1:33 AM • 3 Y

Y by dangerousliri, R8kt, MuhammadAmmar

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

Here $\gcd(a, b)$ is the largest positive integer that divides both $a$ and $b$ . Integers $a$ and $b$ are coprime if $\gcd(a, b) = 1$ .

Proposed by Paulius Aleknavičius, Lithuania

This post has been edited 2 times. Last edited by EeEeRUT, Apr 18, 2025, 12:56 AM
Reason: Authorship

Z K Y

The post below has been deleted. Click to close.

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

1501 posts

#2 h Apr 16, 2025, 1:49 AM • 1 Y

Y by R8kt

We claim that all $N$ even and power of $3$ work.
To see they do for $N$ even it is trivial as all $c_i$ 's are odd and for $N$ power of $3$ just notice the $c_i$ 's cycle between being $1,2 \pmod 3$ and thus the sum of consecutive terms is always divisible by $3$ .
Now suppose $N$ was odd but not a power of $3$ then notice $c_1=1, c_2=2$ so $3 \mid N$ and thus we can consider $N=3^k \cdot \ell$ for $k \ge 1$ and if $\ell=3m+1$ then notice $3m-1, 3m+2$ are both coprime to $\ell$ and are consecutive coprimes for obvious reasons so we must have $\gcd(N, 6m+1)>1$ however if they did share a prime divisor then from euclid alg it divides $3^k$ and thus it has to be $3$ which is a contradiction, a similar thing can be done for $\ell=3m+2$ thus we are done :cool:

:cool:

.

Z K Y

The post below has been deleted. Click to close.

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

110 posts

#3 h Apr 16, 2025, 2:06 AM • 1 Y

Y by R8kt

Ans is all $N$ even and $N =3^m$ .
note that all even is true (easy to see)
claim 1 if $2 \mid N+1$ then $3 \mid N$
after that is easy (I am lazy to retype the solution again)

Z K Y

The post below has been deleted. Click to close.

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

123 posts

NicoN9

#4 h Apr 16, 2025, 8:03 AM • 2 Y

Y by R8kt, shafikbara48593762

Why is that deleted? rewriting!

The answer is all even number, and power of $3$ (and $N\ge 3$ .) These $N$ works since if $N$ is even, then all $c_i$ are odd, and if $N$ is power of $3$ , then $c_1, c_2, c_3, \dots$ are $1, 2, 1, 2, \dots \pmod 3$ , which works.

Also, we see that if $N$ odd, then $c_1=1$ and $c_2=2$ , thus $3\mid N$ . Assume for a contradiction that $N$ has prime factors $3<p_1<\dots <p_r$ and let $P=p_1p_2\dots p_r$ .

$\bullet$ if $P\equiv 1\pmod 3$ , then there exists an integer $h$ with $c_h=P-2$ , and $c_{h+1}=P+1$ . Now, $\gcd(N, c_h+c_{h+1})=\gcd(N, 2P-1)=1.$ contradiction.

$\bullet$ similarly for $P\equiv 2\pmod 3$ , we have $c_k=P-1$ and $c_{k+1}=P+2$ . $\gcd(N, 2P+1)=1$ .

So we are done.

This post has been edited 1 time. Last edited by NicoN9, Apr 16, 2025, 8:05 AM
Reason: 3 divides N

Z K Y

The post below has been deleted. Click to close.

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

86 posts

#5 h Apr 16, 2025, 1:07 PM • 1 Y

Y by R8kt

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 K Y

The post below has been deleted. Click to close.

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

SimplisticFormulas

99 posts

SimplisticFormulas

#6 h Apr 17, 2025, 1:00 PM • 1 Y

Y by R8kt

overcomplication be like

Z K Y

The post below has been deleted. Click to close.

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

168 posts

Safal

#7 h Apr 17, 2025, 5:39 PM • 1 Y

Y by R8kt

My Solution

This post has been edited 6 times. Last edited by Safal, Apr 17, 2025, 7:08 PM

Z K Y

The post below has been deleted. Click to close.

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

197 posts

#8 h Apr 17, 2025, 7:24 PM • 1 Y

Y by R8kt

We claim that the solutions are $N=2^kt, 3^k$ .

First note that if $2 \mid N$ then we only have odd numbers left, and odd plus odd must be even so every $N=2^kt$ works. If $2 \nmid N$ then we know that $1=c_1, 2=c_2$ so $1+2=3 \mid N$ . If $N=3^k$ then $c_1, c_2, \ldots , c_m \equiv 1, 2, \ldots \mod{3}$ and clearly $3 \mid c_i+c_{i+1}$ for all $i$ so $N=3^k$ also works.

If $N=3^kt$ where $2,3 \nmid t \neq 1$ then we know that there is some $h \in \{1,2\}$ such that $ht \equiv 2 \mod{3}$ . Then, $ht$ won't be in $\{c_1,\ldots,c_m\}$ because it isn't coprime with $t$ , $ht+1$ is coprime with $t$ but will be $0 \mod{3}$ so it won't be in $\{c_1,\ldots,c_m\}$ either. $ht+2$ will be $1 \mod {3}$ and $(ht+2,t)=(2,t)=1$ so $ht+2$ is coprime with $N$ . Similarly $ht-1$ is coprime with $t$ and is $1 \mod{3}$ so $ht-1$ is coprime with $N$ and $ht-1, ht+2$ are actually consecutive coprime numbers, so we can take $ht-1+ht+2 =2ht+1$ . This is clearly coprime with $t$ and it is $2 \mod{3}$ so it is coprime with $N$ . Thus no $3^kt$ works if $2, 3 \nmid t$ . So the only solutions are $N=2^kt, 3^k$ .

(It's impossible for $ht+2 \leq 2t+2$ to be out of range because $2t+2 < 3t \leq N \implies 2<t$ , since $t=1,2$ are both impossible this construction is always safe)

This post has been edited 1 time. Last edited by de-Kirschbaum, Apr 17, 2025, 8:09 PM

Z K Y

The post below has been deleted. Click to close.

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

MathematicalArceus

35 posts

MathematicalArceus

#9 h Apr 17, 2025, 7:27 PM • 1 Y

Y by R8kt

Answers: The only possible solutions are $N=3^k$ and $N=2k \quad \forall k$ .

$N=2k$ Note that obviously this works, because $c_i \in \{2k+1\}$ and sum of any odd number is always even and hence $c_i+c_{i+1}=2m \implies \gcd(2m,2k)>1$ , the condition, we required.

$N=3^k$ Note that taking the set $\{c_i\}$ and writing the set under $\pmod{3}$ gives us: $\{1,-1,1,-1,\dots -1\}$ so for any $i$ , $c_i+c_{i+1} \equiv 0 \pmod{3}$ , granting our condition to be true.

No other sols exist: We only consider for odd $N$ , because all even $N$ works. Note that if any odd $N$ works, this means $3 \mid N$ because for any odd $N, \text{ } c_1+c_2=1+2=3 \implies \gcd(N,3)>1 \implies 3 \mid N$ . Now, let $N=3^kp_1^{a_1}p_2^{a_2}\dots p_n^{a_n}$ . We consider $p_1p_2\dots p_n \pmod{3}$ .

$p_1p_2\dots p_n \equiv 1 \pmod{3}$ Note this implies that $p_1p_2\dots p_n -2 \equiv 2 \pmod{3}$ and $p_1p_2\dots p_n+1 \equiv 2 \pmod{3}$ . Adding we get $2p_1p_2\dots p_n-1 \equiv 1 \pmod{3}$ , which is obviously coprime to $N$ . Note that $c_i = p_1p_2\dots p_n-2, c_{i+1} = p_1p_2\dots p_n+1$ and hence we get $c_i+c_{i+1}$ , such that its gcd with $N$ is 1.

Similarly $p_1p_2\dots p_n \equiv 2 \pmod{3}$ follow the same argument and hence, we are done!

Remark

This post has been edited 2 times. Last edited by MathematicalArceus, Apr 17, 2025, 7:41 PM

Z K Y

The post below has been deleted. Click to close.

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

42 posts

#10 h Apr 18, 2025, 4:31 AM • 2 Y

Y by R8kt, GeoKing

Just for the sake of not typing twice, here is a pdf solution :gleam:

:gleam:

Attachments:

EGMO 2025 Solution.pdf (32kb)

Z K Y

The post below has been deleted. Click to close.

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

478 posts

#11 h Apr 18, 2025, 1:11 PM • 2 Y

Y by R8kt, SilverBlaze_SY

Solved with SilverBlaze_SY.

We prove that $N=2k$ for $k\ge 2$ and $N=3^k$ for $k\ge 1$ are the only solutions.

First we show that these work.

For $N=2k$ , note that all the integers coprime to $N$ are odd and summing two of them would give an even result. So the $\gcd$ is at least $2$ and we are done.

For $N=3^{k}$ , note that the integers coprime to it alternate between $1$ and $2\pmod 3$ . This means that sum of two consecutive integers among them is going to be divisible by $3$ which makes the $\gcd$ at least $3$ and we are done.

Now we show that the other cases are not possible. FTSOC assume that some other integer which is not even or a power of $3$ works.

Note that clearly $\gcd(N,1)=1$ and $\gcd(N,2)=1$ as $N$ is odd. Since we must have $\gcd(N,3)\not=1$ , we get $3\mid N$ .

Represent $N=3^{\alpha_1}\cdot q$ where $\alpha_1\ge 1$ and $\gcd(q,3) = 1$ , $q\not=1$ .

If $q\equiv 1\pmod 3$ , then note that $\gcd(N,q-2)=\gcd(N,q+1)=1$ . Also, $\gcd(N,(q-2)+(q+1))=\gcd(N, 2q-1) = 1$ which gives a contradiction.

If $q\equiv 2\pmod 3$ , then note that $\gcd(N, q-1) = \gcd(N, q+2)=1$ . Also, $\gcd(N,(q-1)+(q+2))=\gcd(N, 2q+1)=1$ which gives a contradiction too.

Therefore such a choice of $N$ is not possible and we are done.

This post has been edited 1 time. Last edited by kamatadu, Apr 18, 2025, 2:22 PM

Z K Y

The post below has been deleted. Click to close.

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

68 posts

#12 h Apr 19, 2025, 9:04 AM

Y by

WE can use a type of "infinite ascent" here to show that only $3^k$ and all even numbers is the only solution:
FTSOC,consider
$N=3^K.p_1^{a_1}...p_i{a_i}$ ,but there must exist some $x>N$ for which : $gcd(3x+1,N) \neq 1\implies gcd(3x-1,N)=1=gcd(3x+2,N)$ ,hence we must have :
The prime dividing $3x-1+3x+2=6x+1$ in the prime list of our $N$ ,but here we see that $gcd(6x+1,N)=1$ hence we have to include another prime $q$ which is not in our list hence we can make our list infinitely big hence no numbers like this exists.

Why $(6x+1,N) =1$ as explained by Luis above also that if we continue on applying the EDA,we would reach somewhere : $6x+1|3^k.(3x+1)$ which is not not possible.

This post has been edited 2 times. Last edited by Mathgloggers, Apr 19, 2025, 9:32 AM
Reason: n

Z K Y

The post below has been deleted. Click to close.

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

67 posts

#13 h Apr 22, 2025, 3:28 AM

Y by

Claim: The only solution are N is even number and $N=3^k$ $\forall$ $k\ge1$
Proof:
For N is even:
$c_i\equiv 1,2(mod3)$ as $gcd(N,c_i)=1$
i.e if $c_i\equiv 1(mod3)$ then, $c_{i+1}\equiv 2 (mod3)$ or vice versa $\implies gcd(N,c_i + c_{i+1})>1$
For $N=3^k$ , similar to above
For $N=3^k\cdot t$ and $(3,t)=1$ $t>1$
case 1: $t\equiv1(mod3)$
$3\mid t-1$ so $3\nmid (t-2, t+1)$ $\implies gcd(3^k\cdot t, (t-2)+(t+1))=gcd(3^k\cdot t, 2t-1)=1$ , we are done..
case 2: $t\equiv 2(mod3)$
$3\mid t-2$ and $3\nmid (t-1, t+2)$ $\implies gcd(3^k\cdot t,(t-1)+(t+2))=gcd(3^k\cdot t, 2t+1)=1$ , we are done...

Z K Y

The post below has been deleted. Click to close.

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

63 posts

EVKV

#14 h Apr 22, 2025, 5:36 PM

Y by

CASE 1 N is even

Claim: All even N works
Proof: As all $c_{i}$ are even the sum of 2 consecutive co-prime 2 divides the gcd thus its not 1

CASE 2 N is odd

Claim: 3|N
Proof: 1,2 are consecutive co primes and so gcd(N,3) $\neq$ 1 so 3|N

Claim: Only prime dividing N is 3
Proof: Assume the contrary lets assume $q_{1}, \cdots ,q_{n}$ are all the primes except 3 which divide N

Claim if $\prod q_{i}$ $\equiv 1$ mod 3 then there exists an r such that the product divides 3r+1 and $3r+1 \leq N$

Proof: clearly 3r+1= $\prod q_{i}$ $\leq N$ satisfies this

Claim if $\prod q_{i}$ $\equiv 2$ mod 3 then there exists an r such that the product divides 3r+1 and $3r+1 \leq N$

Proof: clearly 3r+1= $2\prod q_{i}$ $\leq N$ satisfies this

Now 3(r-1)+2 and 3r +2 are consecutive co primes
3(r-1)+2 + 3r +2 $\equiv -2+1$ $\equiv 1$ mod $q_{i}$ for all i $\leq n$
3(r-1)+2 + 3r +2 $\equiv 2+2$ $\equiv 1$ mod $3$
Thus gcd(N,3(r-1)+2 + 3r +2)=1
Contradiction

Claim: N= $3^a$ for $a \in N$

Proof: Clearly the consecutive co primes are $1+2 \equiv 0$ mod 3 thus gcd(N, $c_{i} + c_{i+1}$ ) $\neq1$

REMARK:
A nice problem tho I changed my solution making it more rigorous crt was def grt motivation

I rate it 5 mohs

SOLVED ON 21/4/25
ALSO 50TH POST YAY

This post has been edited 2 times. Last edited by EVKV, Apr 22, 2025, 5:42 PM

Z K Y

The post below has been deleted. Click to close.

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

14 posts

#15 h Apr 23, 2025, 10:08 AM

Y by

(Livesolved on YouTube: Art of Olympiad Mathematics)

Answer: $n$ is even or a power of $3$ .

Proof. If $n$ is even, then all $c_i$ are all odd, meaning that $c_i + c_{i+1}$ is even, which is never coprime to $n$ so it works. If $n=3^k$ , then all the $c_i$ 's are just numbers that are not divisible by $3$ meaning that the residues go $1, 2, 1, 2, ...$ mod $3$ . Hence this works as well.

Now, let's suppose $n=3^k \cdot a$ . Then we look at $a+1$ and $a-1$ . At least one of them is not divisible by $3$ , and by looking at the sums of adjacent ones we are done - either we get $a+(a+2)=2a+2$ which is coprime to $n$ if $3 | a+1$ or we get $a$ + $a-2$ which works as well.

Z K Y

The post below has been deleted. Click to close.

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

11 posts

#16 h Yesterday at 1:57 PM

Y by

We will easy check all even $N$ works.
Now prove $N$ is odd. Then $c_1=1$ and $c_2=2$ . Then $3 \mid N$ .
Let $N = 3^k \times m$ and $m > 1$ .
If $m \equiv 1\pmod{3}$ then $(m - 2, N) = 1$ and $(m + 1, N) = 1$ . Now $(2m - 1, N) \ne 1$ . But $(2m - 1, N) = (2m - 1, 3^k \times m) = (2m - 1, m) = (-1, m) = 1$ (Because $(2m - 1, 3) = 1$ )
$m \equiv 2\pmod{3}$ same. Then $m = 1$ or $N = 3^k$ .
Answer is $N$ is even or $N = 3^k$ .

This post has been edited 1 time. Last edited by Tuvshuu, Yesterday at 2:02 PM
Reason: how i know

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a