Gcd of N and its coprime pair sum

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 N and its coprime pair sum

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.

85 posts

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

Y by dangerousliri, R8kt, MuhammadAmmar, SatisfiedMagma, GA34-261

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 3 times. Last edited by EeEeRUT, May 11, 2025, 11:49 AM

Z K Y

The post below has been deleted. Click to close.

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

1560 posts

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

Y by R8kt, HeshTarg, GA34-261

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.

151 posts

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

Y by R8kt, GA34-261

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.

164 posts

NicoN9

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

Y by R8kt, shafikbara48593762, GA34-261

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.

115 posts

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

Y by R8kt, GA34-261

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

132 posts

SimplisticFormulas

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

Y by R8kt, GA34-261

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.

174 posts

Safal

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

Y by R8kt, GA34-261

My Solution

This post has been edited 11 times. Last edited by Safal, May 31, 2025, 10:01 PM

Z K Y

The post below has been deleted. Click to close.

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

204 posts

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

Y by R8kt, GA34-261

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

47 posts

MathematicalArceus

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

Y by R8kt, GA34-261

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.

64 posts

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

Y by R8kt, GeoKing, GA34-261

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.

481 posts

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

Y by R8kt, SilverBlaze_SY, GA34-261

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.

94 posts

#12 h Apr 19, 2025, 9:04 AM • 1 Y

Y by GA34-261

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.

70 posts

#13 h Apr 22, 2025, 3:28 AM • 1 Y

Y by GA34-261

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.

71 posts

EVKV

#14 h Apr 22, 2025, 5:36 PM • 2 Y

Y by Nobitasolvesproblems1979, GA34-261

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 • 1 Y

Y by GA34-261

(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 Apr 24, 2025, 1:57 PM • 2 Y

Y by Arcturuss, GA34-261

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, Apr 24, 2025, 2:02 PM
Reason: how i know

Z K Y

The post below has been deleted. Click to close.

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

20 posts

#17 h May 9, 2025, 8:00 PM • 1 Y

Y by GA34-261

Case 1: $N$ is even. Then all $c_i$ 's are odd, so $c_i+c_{i+1}$ is even, $\forall 1\leq i\leq N-1$ , so $\gcd(N, c_i+c_{i+1})>1$ , so all even $N$ work. $\square$

Case 2: $N$ is odd. Clearly, $N-1=c_{\varphi(N)}$ and since $N$ is odd, $N-2=c_{\varphi(N)-1}$ , implying $\gcd(N,2N-3)=\gcd(N,3)>1$ so $N$ is a multiple of $3$ . Write $N=3^a\cdot b$ , with $(b,2)=(b,3)=1$ . FTSoC suppose $b>1$ .

Case 2.1: $b\equiv 1(\mod 3)$
Then, if $d=\gcd(3^a\cdot b, b-2)$ , we have: $d\mid 3^a\cdot b$ and $d\mid 3^a\cdot b-2\cdot 3^a$ , implying $d\mid 2\cdot 3^a$ . However, the second condition implies $(d,6)=1$ , so there exists $i<\varphi(N)$ such that $c_i=b-2$ . Since $b-1\equiv 0(\mod 3)$ , $c_{i+1}\geq b+1$ . However, if there is some $d>1$ such that $d\mid 3^a\cdot b$ and $d\mid b+1$ , then $d\mid 3^a$ which is impossible. So $c_{i+1}=b+1$ , implying $\gcd(3^a\cdot b, 2b-1)>1$ , which is clearly a contradiction. $\square$

Case 2.2: $b\equiv 2(\mod 3)$ . Then we may do the same thing but for $b-1$ and $b+2$ , which will also yield a contradiction. $\square$

So $b=1$ is the only possible case, which can be easily checked to work, because $c_i$ ’s alternate $(\mod 3)$ , so we're done $\blacksquare$

This post has been edited 3 times. Last edited by ravengsd, May 22, 2025, 5:34 PM

Z K Y

The post below has been deleted. Click to close.

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

6882 posts

#18 h May 31, 2025, 1:13 AM • 2 Y

Y by GA34-261, NicoN9

Solution from Twitch Solves ISL:

The answer is $N$ even and $N$ powers of $3$ .
Begin by noting

Even $N$ all work: all $c_i$ are odd, so each $c_i + c_{i+1}$ work.
Odd $N$ not divisible by $3$ fail: note that $c_1 = 1$ and $c_2 = 2$ .

Hence, the problem reduces checking that if $N$ is an odd multiple of $3$ , then it works if and only if $N$ is a power of $3$ .
If $N$ was indeed a power of $3$ , then $(c_i)_i = (1,2,4,5,7,8,\dots)$ consists of all the non-multiples of $3$ in order. In this case, each $c_i + c_{i+1}$ is necessarily $0 \pmod 3$ , so these numbers do work.
The final case:
Claim: Suppose $N = 3^e d$ , where $e \ge 1$ , and $d > 1$ is not a multiple of $3$ (and odd). Then

If $d \equiv 1 \pmod 6$ , then $d-2$ and $d+1$ are consecutive $c_i$ 's whose sum $2d-1$ is coprime to $N$ .
If $d \equiv 5 \pmod 6$ , then $d-1$ and $d+2$ are consecutive $c_i$ 's whose sum $2d+1$ is coprime to $N$ .

Proof. We prove just the first bullet; the second calculation looks exactly the same. Assuming $d \equiv 1 \pmod 6$ , Note that $\begin{align*} 3 &\mid \gcd(d-1, N) \\ d &= \gcd(d, N) \\ \gcd(d-2, N) &= \gcd(d-2, 3^e d) = \gcd(d-2, 3^e \cdot 2) = 1 \\ \gcd(d+1, N) &= \gcd(d+1, 3^e d) = \gcd(d+1, -3^e) = 1. \end{align*}$ Moreover, $\gcd(2d-1, N) = \gcd(2d-1, 3^e d) = \gcd(2d-1, 3^e \cdot 2d) = \gcd(2d-1, 3^e) = 1.$ This completes the proof. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

184 posts

lksb

#19 h May 31, 2025, 1:37 AM • 1 Y

Y by GA34-261

If $N$ is even, then $c_i\equiv 1\pmod{2}\implies c_i+c_{i+1}\equiv 1+1\equiv 0\pmod{2}$ , therefore, $\boxed{\text{all even}\ N\ \text{work}}$
If $N$ is odd, then $c_1=1, c_2=2\implies 3\mid N$ , let $N=3^{\nu_3(N)}P$ , assume FTSoC that $P>1$ .
If $P\equiv1\pmod{3}$ , then $\exists k$ such that $c_k=P-2, c_{k+1}=P+1\implies 1\neq \gcd(N,c_k+c_{k+1})=\gcd(N,2P-1)=1$ , which is a contradiction
If $P\equiv-1\pmod{3}$ , then $\exists k$ such that $c_k=P-1, c_{k+1}=P+2\implies 1\neq \gcd(N,c_k+c_{k+1})=\gcd(N,2P+1)=1$ , another contradiction
Therefore, $\boxed{\text{powers of}\ 3\ \text{are the only odd solutions}}$ . And with so, 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.

8879 posts

#20 h May 31, 2025, 3:24 PM • 1 Y

Y by GA34-261

this took an embarrassingly long time :/

The answer is even numbers and powers of $3$ , which clearly work.

Note that $\gcd(n, 6) > 1$ , otherwise $d_1 = 1, d_2 = 2$ fail. So let $p_1 = 3, p_2, \dots, p_k$ be the distinct prime factors of $n$ . Consider an integer $c$ with $c \equiv 1 \pmod 3$ , $c \equiv -1 \pmod {p_2}$ , and $c \equiv -4 \pmod {p_i}$ for all $3 \leq i \leq k$ .

Then $p_2 \mid c+1$ and $3 \mid c+2$ , and $c$ and $c+3$ are consecutive numbers relatively prime to $n$ . On the other hand, $2c+3 \equiv 2 \pmod 3$ , $2c+3 \equiv 1 \pmod {p_2}$ , and $2c+3 \equiv -5 \pmod {p_i}$ for all $3 \leq i \leq k$ . Since $p_3 > 5$ , $\gcd(n, 2c+3) = 1$ , so we have our desired counterexample.

Z K Y

The post below has been deleted. Click to close.

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

81 posts

#21 h Jun 1, 2025, 5:35 AM

Y by

If $c_i's$ are all even, $c_i+c_{i+1}$ is even so $\gcd(N, c_i+c_{i+1})\ge 2$ .
If $N=3^k$ , then the only numbers coprime to $N$ are $1,2,4,5,\dots 3^k-1$ . Since they alternate between $1$ and $2$ modulo $3$ , $\gcd(N, c_i+c_{i+1})\ge 3$

Now if $N\neq 3^k$ and $N$ is odd, $1+2=3\mid N$ so let $N=3^k\cdot p_1^{\alpha_1}\cdot p_2^{\alpha_2}\dots \cdot p_m^{\alpha_m}$ , $p_i\neq 3$
Case 1: $p_1p_2\dots p_m\equiv 1\pmod 3$
So, $p_1p_2\dots p_m+1$ and $p_1p_2\dots p_m-2$ are both coprime to $N$ , but $\gcd(2p_1p_2\dots p_m-1,N)=1$ .

Case 2: $p_1p_2\dots p_m \equiv 2\pmod 3$
So, $p_1p_2\dots p_m+2$ and $p_1p_2\dots p_m-1$ are both coprime to $N$ , but $\gcd(2p_1p_2\dots p_m+1,N)=1$

So, the only integers that work are the ones claimed above.

This post has been edited 1 time. Last edited by Adywastaken, Jun 1, 2025, 10:12 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a