Co-prime Sequence

If Thanic is given any positive integer $n$, he writes down all the integers co-prime to the given number - meaning numbers with which the GCD (Greatest Common Divisor) of $n$ is $1$. For example, if $n = 10$ is given, he keeps writing $1, 3, 7, 9, 11, 13, \dots$.

If after giving Thanic some integer $n$, the numbers he writes down form an arithmetic progression, then what are the possible values for $n$?

In an arithmetic progression the difference between two consecutive terms are always the same. For example: $3, 7, 11, 15, 19, \dots$.

Proof Based Problems

0 Upvote 0 Downvote

Solution

Disclaimer: The solutions we've shared are just one exciting approach, and there are surely many other wonderful methods out there. We’d love to hear your alternative solutions in the community thread below, so let's keep the creativity flowing!

The answer is all powers of $2$. Remember that $n$ is co-prime with $n-1$ and $n+1$. Therefore, the arithmetic sequence must have a common difference of $2$. Since $1$ is co-prime with every positive integer, the sequence must be $1, 3, 5, 7, \dots$. The only numbers satisfying this are powers of $2$.

This is a proof based problem added for learning purposes and does not accept submissions.

You can view the solution by clicking on the solution tab.

Editorial

Need a hint? Checkout the editorial.

View Editorial