divisibility

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

divisibility

G H J

Reveal topic tags

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.

56 posts

srnjbr

#1 h Friday at 4:29 PM

Y by

Find all natural numbers n such that there exists a natural number l such that for every m members of the natural numbers the number m+m^2+...m^l is divisible by n.

Z K Y

The post below has been deleted. Click to close.

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

mathprodigy2011

233 posts

mathprodigy2011

#3 h Friday at 5:32 PM

Y by

srnjbr wrote:

Find all natural numbers n such that there exists a natural number l such that for every m members of the natural numbers the number m+m^2+...m^l is divisible by n.

We want the expression

$m \cdot \frac{m^i - 1}{m - 1}$
to be divisible by $n$ for all natural numbers $m$ . This is equivalent to requiring

$m \cdot \frac{m^i - 1}{m - 1} \equiv 0 \pmod{n}$
for $m = 0, 1, 2, \ldots, n - 1$ .

### Case 1: $m$ is relatively prime to $n$

Since $m$ and $n$ are relatively prime, the $m$ in front does not contribute to the divisibility by $n$ . Thus, we can omit it, reducing the problem to ensuring that

$\frac{m^i - 1}{m - 1}$
is divisible by $n$ . This requires that

$m^i \equiv 1 \pmod{n}$
and $m \not\equiv 1 \pmod{n}$ (we will consider the case $m \equiv 1$ separately). By Euler's totient theorem, $m^{\varphi(n)} \equiv 1 \pmod{n}$ for all $m$ relatively prime to $n$ , which tells us that $i$ must be divisible by $\varphi(n)$ . Therefore, for all $m$ relatively prime to $n$ such that m is not 1 mod n, the condition is satisfied if i is divisble by phi(n)

Case 2: $m \equiv 1 \pmod{n}$

Plugging this into the original expression, we have

1+1+....+1 = i mod n

For this to be divisible by $n$ , we must have $i$ divisible by $n$ . Therefore, combining the two cases, $i = n \cdot \varphi(n)$ works for all numbers relatively prime to $n$ .

### Case 3: $m$ is not relatively prime to $n$

We write the prime factorization of $n$ as

$n = p_1^{e_1} p_2^{e_2} \ldots p_k^{e_k}.$
Notice that if $e_1 > 1$ , then $p_1$ cannot satisfy the condition. This is because

$m \cdot \frac{m^i - 1}{m - 1}$
needs to be divisible by $p_1^{e_1}$ , but if we plug in $m = p_1$ , the second term

$\frac{p_1^i - 1}{p_1 - 1}$
is never divisible by $p_1$ , while the first term $m$ only contributes one factor of $p_1$ . Thus, for divisibility, we must have $e_j = 0, 1$ for all primes, meaning $n$ must be square-free.

Therefore,

$n = p_1 p_2 p_3 \ldots p_k$
is square-free. Finally, we plug in $p_1$ and observe that we need

$\frac{p_1^i - 1}{p_1 - 1}$
to be divisible by $p_2 p_3 p_4 \ldots p_k$ . Since these two numbers are relatively prime, and we have already shown that if they are relatively prime, there exists an integer that satisfies the condition, the proof is complete.

Thus, we conclude that $n$ must be square-free

This post has been edited 4 times. Last edited by mathprodigy2011, Friday at 5:35 PM
Reason: .

Z K Y

The post below has been deleted. Click to close.

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

663 posts

#5 h Friday at 6:46 PM

Y by

Kvant 2024 no. 10 M2816

Z K Y

The post below has been deleted. Click to close.

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

56 posts

srnjbr

#6 h Friday at 7:03 PM

Y by

Thank you

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a