MHB Divisibility Problem: Prove Existence of $i,j$

  • Thread starter Thread starter qamaz
  • Start date Start date
  • Tags Tags
    Divisibility
AI Thread Summary
The discussion centers on proving the existence of indices \(i\) and \(j\) such that the sum of a sequence of integers \( (a_1, a_2, \ldots, a_n) \) is divisible by \(n\). A suggested approach involves defining \(b_j = \sum_{k=1}^j a_k\) and applying the pigeonhole principle to the remainders of \(b_j\) when divided by \(n\). The concept of \(\mathbb{Z}^n\) is clarified as the set of all ordered \(n\)-tuples of integers. The discussion emphasizes the importance of understanding these mathematical constructs to solve the divisibility problem. Ultimately, the existence of such indices is guaranteed by these principles.
qamaz
Messages
3
Reaction score
0
$$\text{ Let } n∈N \text{ and } (a1,a2,…,a_{n})∈\mathbb{Z}^{n}.

\text{ Prove that always exist } i,j∈ \underline{n} \text{ with } i≤j \text{ so }

\sum\limits_{k=i}^{\\j} a_{k} \text{ divisible by n} .$$
 
Last edited:
Physics news on Phys.org
Hi, and welcome to the forum!

Hint: Consider $$b_j=\sum_{k=1}^ja_k$$, $j=1,\ldots,n$ and apply the pigeonhole principle to remainders when $b_j$ are divided by $n$.
 
What is the meaning of $$\mathbb{Z}^{n}$$?
 
$$\mathbb{Z}$$ denotes the set of integers. If $A$ and $B$ are sets, $A\times B$ denotes the set of all ordered pairs, where the first element comes from $A$ and the second one comes from $B$. More generally, $A_1\times \dots\times A_n$ denotes the set of all $n$-tuples, i.e., of ordered sequences of length $n$, where the $i$th element comes from $A_i$ for $i=1,\ldots,n$. Finally, $A^n=A\times\dots\times A$ ($n$ times). Thus, $$(a_1,\ldots,a_n)\in\mathbb{Z}^n$$ means that all $a_i$ are integers.
 
Back
Top