Intereting Posts

Proper Nontrivial Ideals of Modular Lipshitz Quaternions
How many solutions does $\cos x + \cos (2x) + \cos (3x) +\cos (4x) = -\frac{1}{2}$ have in $$?
Prove that $\frac{(n!)!}{(n!)^{(n-1)!}} $ is always an integer.
Class number computation (cyclotomic field)
Proof of a matrix is positive semidefinite iff it can be written in the form $X'X$
Interchanging pointwise limit and derivative of a sequence of C1 functions
Who named “Quotient groups”?
Open sets in product topology
Assume $A,B,C,D$ are pairwise independent events. Decide if $A\cap B$ and $B\cap D$ are independent
Conditional probability containing two random variables
Is each “elementary + finite functions” function “elementary + finite functions”-integrable?
Connected sums and their homology
Name of this fractal
Creating an ellipsoidal 3D surface
p-series convergence

If $n\in \Bbb N$, $A\subset \Bbb N$, $|A|=n$, how to prove that there exists a subset of $A$ such that the summation of its element is divisible by $n$?

- $n$-Bit Strings Not Containing $010$
- Discriminant of a binary quadratic form and Jacobi symbol
- Find five positive integers whose reciprocals sum to $1$
- Divisibility Proof with Induction - Stuck on Induction Step
- Are there always at least $3$ integers $x$ where $an < x \le an+n$ and $\gcd(x,\frac{n}{4}\#)=1$
- Sum and difference coprimes
- Proving the irrationality of $\sqrt{5}$: if $5$ divides $x^2$, then $5$ divides $x$
- What is complete induction, by example? $4(9^n) + 3(2^n)$ is divisible by 7 for all $n>0$
- Linear Congruence Theorem - Are these solutions too? Where'd they hail from?
- How do we prove $n^n \mid m^m \Rightarrow n \mid m$?

Let $A = \{ a_1, \ldots, a_n \}$. Consider the numbers $0$, $a_1$, $a_1 + a_2$, $\ldots$, $a_1 + a_2 + \cdots + a_n$ modulo $n$. There are $n+1$ numbers and only $n$ residue classes modulo $n$, so by the pigeonhole principle there exist $i$ and $j$ such that $a_1 + \cdots + a_i$ and $a_1 + \cdots + a_i + \cdots + a_j$ are equal modulo $n$. Hence $n$ divides $a_{i+1} + \cdots + a_j$.

Let $A=\{a_1,a_2,\dots,a_n\}$.

Look at the numbers $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, and so on up to $a_1+a_2+\cdots+a_n$. If two of these sums are congruent modulo $n$, say $a_1+\cdots +a_i$ and $a_1+\cdots +a_j$, where $j\gt i$, then their difference $a_{i+1}+\cdots +a_j$ is congruent to $0$, and we have found a non-empty subset of $A$ with sum divisible by $n$.

On the other hand, if $a_1$, $a_1+a_2$, $a_1+a_2+a_3$, and so on up to $a_1+a_2+\cdots+a_n$ are all distinct modulo $n$, then one of them must be congruent to $0$.

Consider the $\rm\:n\:$ partial sums $\rm\: n_1,\,\ n_1\!+n_2,\,\ n_1\!+n_2\!+n_3,\ \ldots\ (mod\ n).$ If one is $\equiv 0\:$ we’re done, else two are $\,\equiv,\,$ so subtracting them yields a tail sum $\equiv 0.$

**Remark** $\ $ Here’s a similar Pigeonhole argument: $ $ if $\rm\:n\:$ is coprime to $10\,$ then every integer with at least $\rm\:n\:$ digits $\ne 0\:$ has a contiguous digit subsequence that forms an integer $\ne 0\,$ divisible by $\rm\:n.\:$ Hint: pigeonholing, two of the $\rm\:n\!+\!1\:$ numbers $\rm\:0,\ d_1,\ d_2 d_1,\ d_3 d_2 d_1,\, \ldots,\:d_m\!\ldots d_1\:$ must be $\rm\:\equiv\, \ (mod\ n),\:$ so subtracting them $\:\ldots$

- prove the divergence of cauchy product of convergent series $a_{n}:=b_{n}:=\dfrac{(-1)^n}{\sqrt{n+1}}$
- I want to find all pairs of integer $ (x, y)$
- Does it hold? $\int_{0}^{\pi/2}\cos^{2k}xdx=\frac{(2k-1)!!}{2k!!}\frac{\pi}{2}$
- Product of Sine: $\prod_{i=1}^n\sin x_i=k$
- A problem on range of a trigonometric function: what is the range of $\frac{\sqrt{3}\sin x}{2+\cos x}$?
- A set with measure 0 has a translate containing no rational number
- Prove that if $p$,$q$ and $\sqrt{2}p+\sqrt{3}q$ are rational numbers then $p=q=0$
- Why does $e$ have multiple definitions?
- Integral representation of Euler's constant
- How to divide polynomial matrices
- Ring with maximal ideal not containing a specific expression
- Is $2^k = 2013…$ for some $k$?
- Intuitive Understanding of the constant “$e$”
- measurability of a function -equivalent conditions
- Is an irreducible element still irreducible under localization?