Let $N>1$ be an integer. We are adding all remainders when we divide $N$ by all positive integers less than $N$. If this sum is less than $N$, find all possible values of $N$.
Problem
Source:
Tags:
boywholived
19.01.2013 17:41
xeroxia wrote: Let $N>1$ be an integer. We are adding all remainders when we divide $N$ by all positive integers. If this sum is less than $N$, find all possible values of $N$. Are you sure about that underlined sentence?. If we divide $N$ by $N+1$ we get the remainder $N$ which is equal to $N$?.Does this question misses something?
xeroxia
20.01.2013 00:01
boywholived wrote: xeroxia wrote: Let $N>1$ be an integer. We are adding all remainders when we divide $N$ by all positive integers. If this sum is less than $N$, find all possible values of $N$. Are you sure about that underlined sentence?. If we divide $N$ by $N+1$ we get the remainder $N$ which is equal to $N$?.Does this question misses something? "All positive integers less than $N$". I have corrected. Sorry.
DoctorB
20.01.2013 16:10
Let $r(N,q)$ be the remainder when $N$ is divided by $q$. Then $r(N,q)$ is somewhat chaotic for small $q$, but very predictable for $q>N/2$. In fact, if $M$ is the largest integer smaller than $N/2$ (i.e. either $N=2M+1$ or $N=2M+2$) then:
\[2M+2
\ge N>
\sum_{q=1}^{N-1}
r(N,q)
\ge \sum_{q=N-M}^{N-1}
r(N,q)
\] \[
= \sum_{q=N-M}^{N-1}
N-q
= \sum_{k=1}^{M} k
= \frac{M(M+1)}{2}
\]
which immediately gives $M<4$, i.e. $N\in
\{2,3,4,5,6,7,8\}$. Trying these individually shows that they all work except for $7,8$.
Answer:$\{2,3,4,5,6\}$