Help me please

Art of Problem Solving

AoPS Online

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Help me please

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.

8 posts

#1 h Mar 23, 2025, 7:37 AM

Y by

Determine all integers $n>1$ that satisfy the following condition: For every integer k such that $0\le k<n$ there always exists a positive integer $A$ that is divisible by n and $S(n)\equiv k (mod n)$ . $S(n)$ : sum of elements of $A$

Z K Y

The post below has been deleted. Click to close.

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

10496 posts

#3 h Monday at 11:29 AM

Y by

It's a nice problem, the answer is for all $n>1$ . Also please mind your notation: it should be $S(A)\equiv k\mod n$ and $S(A)$ in the last line.
First note that the problem is clear when $(s(n),n)=1$ . Choose $\pi\equiv 1(n)$ prime and $t\ge 0$ . Then $s(n\pi^t)=s(n)(\pi^t+\cdots+1)\equiv (t+1)s(n) \mod n$ and this runs through all residue classes mod $n$ .
Now we show that some multiple $a$ of $n$ exists with $(s(a),n)=1$ . Then we finish the problem as before.

Write $n=p_1^{k_1}\cdots p_e^{k_e}$ , the prime factorisation.
We consider $p_1$ and write $S$ for the set of indices $2\le s\le e$ with $p_1\equiv 1(p_s)$ . We write $T$ for the rest, hence the set of indices $2\le t\le e$ with $p_t\not| (p_1-1)$ . These sets may be empty.
We want to choose a large $\lambda$ such that $p_s\not|\lambda$ for $s\in S$ and such that $\lambda\equiv 1(p_t-1)$ for $t\in T$ . This is not difficult: write $M:=\Pi_{s\in S}p_s, N=\Pi_{t\in T}(p_t-1)$ and take $\lambda \equiv 1(MN)$ . In particular we can choose $\lambda>k_1$ and we set $l_1=\lambda-1$ .
We do the same for the other prime factors and we consider $a=\Pi_1^e p_i^{l_i}$ , a multiple of $n$ .

Then $s(a)=\Pi_1^e (p_i^{l_i}+\cdots+1)$ and one checks that $(s(a),n)=1$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a