N 3

Art of Problem Solving

AoPS Online

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

PEN Math problems from the collection "Problems in Elementary Number Theory"

Math problems from the collection "Problems in Elementary Number Theory"

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

N 3

G H J

Reveal topic tags

modular arithmetic

relatively prime

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

3615 posts

Peter

#1 h May 25, 2007, 12:25 AM • 4 Y

Y by UpvoteFarm, Adventure10, Mango247, and 1 other user

Let $\,n>6\,$ be an integer and $\,a_{1},a_{2},\ldots,a_{k}\,$ be all the natural numbers less than $n$ and relatively prime to $n$ . If $a_{2}-a_{1}=a_{3}-a_{2}=\cdots =a_{k}-a_{k-1}>0,$ prove that $\,n\,$ must be either a prime number or a power of $\,2$ .

Z K Y

The post below has been deleted. Click to close.

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

1434 posts

rem

#2 h Sep 24, 2007, 9:31 PM • 5 Y

Y by Adventure10, UpvoteFarm, Mango247, and 2 other users

Note that $a_{1}= 1$ -- the smallest positive integer that will be always relatively prime to $n$ . Also, $a_{2}= p$ where $p$ is a prime, because if it was not prime, then the smallest prime number dividing $a_{2}$ would be greater than $1$ and relatively prime to $n$ because $a_{2}$ is relatively prime to $n$ . So, $a_{2}= p$ where $p$ is a prime, so $p$ must be the smallest prime relatively prime to $n$ .

Then, $a_{2}-a_{1}= a_{3}-a_{2}=\cdots = a_{k}-a_{k-1}= p-1$ .
We will now consider 3 cases:
Case 1 $p = 2$ . Then, $a_{2}-a_{1}= a_{3}-a_{2}=\cdots = a_{k}-a_{k-1}= 1$ , and because $n-1$ is relatively prime to $n$ , then $a_{k}= n-1$ so $1,2,...,n-1$ are all relatively prime to $n$ so $n$ is prime.
Case 2 $p = 3$ . Then, $a_{2}-a_{1}= a_{3}-a_{2}=\cdots = a_{k}-a_{k-1}= 2$ so the numbers $1,3,5,...,n-1$ are relatively prime to $n$ , so all odd numbers less than $n$ are relatively prime to $n$ , so $n$ has no divisors that are odd primes, so the only prime it is divisible by is $2$ , so $n$ is a power of $2$ .
Case 3 $p > 3$ . Then, $a_{2}-a_{1}= a_{3}-a_{2}=\cdots = a_{k}-a_{k-1}= p-1$ , so $a_{k}= 1+(k-1)(p-1)$ but because $n-1$ is the largest number less than $n$ and relatively prime to $n$ , $n-1 = 1+(k-1)(p-1)$ so $n-2 = (k-1)(p-1)$ . So, $p-1$ divides $n-2$ . Let $q$ be any prime dividing $p-1$ , then as $1 < q\leq p-1 < p$ , $q$ is not relatively prime to $n$ , so as $q$ is prime, $q$ must divide $n$ . On the other hand, $q|(p-1)|(n-2)$ so $n-2$ and $n$ are both divisible by $q$ , so $n-(n-2) = 2$ is divisible by $q$ so $q = 2$ . Then, $p-1$ can only be divisible by $2$ , so it is a power of $2$ , so $p = 2^{r}+1$ ; because $p > 3$ and is prime, $p$ is not divisible by $3$ , and as $2^{r}+1\equiv (-1)^{r}+1\pmod 3$ and $p$ is not divisible by $3$ , $(-1)^{r}+1$ cannot be $0$ , so $r$ is even.
But then, $a_{3}= a_{1}+2(p-1) = 1+2*2^{r}= 1+2^{r+1}\equiv 1+(-1)^{r+1}\pmod 3$
$\equiv 0\pmod 3$ as $r$ is even. Hence, $3|a_{3}$ and as $\gcd(a_{3},n) = 1$ , $n$ is not divisible by $3$ so $3$ and $n$ are coprime so $1 < a_{2}\leq 3$ which contradicts the fact that $a_{2}>3$ . So we get a contradiction and in the case when $p > 3$ the required $n$ does not exist.

Then, the only valid cases are $1$ and $2$ which yield $n$ being a prime or a power of $2$ QED.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a