$A$ is a set of $n$ arbitrary natural numbers.  We know that $|A|=n$, so $\forall a_i\in A; a_i=nq+j(i)\ \ \ \ (0\le j(i)\lt n)$.  If there exists an $a_k$ such that $j(k)=0$, then the subset $\{a_k\}$ is the answer.  If not, then $\forall a_i\in A; a_i=nq+j(i)\ \ \ \ (0\lt j(i)\lt n)$.  Then I can say there exist at least two members of $A$ such that $n \mod a_a=n\mod a_b$.  But I can't go further. Help needed.    Guys sorry. It's "divisible by $n$". :-shame
123574
I assume this is correct to any size set, not 2015 in particular... it's obviously true for 2. I know from pen and paper it's true for 3, and 4....  I understand that I should look at the reminders, and build pigeonholes from them.  If one of the numbers has a 0 reminder obviously the entire set is divisible, so the possible reminders go from 1 to (n-1). i have n numbers hence one of the reminders repeats. the sums of the reminders go from 1 to n*(n-1)....  And that's it...  Any and all help would be appreciated.    Of course I mean non empty set...
112359
This is part of a bigger problem I'm trying to prove, but my argument relies of the validity of the following idea. Note that when I say countable, I don't mean finite -- I mean countable infinity.   Consider the set of natural numbers, $\mathbb{N}$. Now take a countable subset of them, call it $\mathsf{S}_1$. Then take a countable subset of $\mathbb{N}\setminus{\mathsf{S}_1}$ and call it $\mathsf{S}_2$. Then take a countable subset of $\mathbb{N}\setminus\{{\mathsf{S}_1}\cup{\mathsf{S}_2}\}$ and call it $\mathsf{S}_3$. Continue in this manner to construct $\mathsf{S}_i$'s such that ${\mathsf{S}_i}\cap{\mathsf{S}_j}=\emptyset$ for $i≠j$.  My question is this: is it necessarily the case that eventually there will be finitely many $\mathsf{S}_i$'s with $\mathbb{N}\setminus\bigcup_{i}{\mathsf{S}_i}={P}$ where $P$ is either empty or finite? My guess is yes, but I'm not how to prove it or how to find a counterexample.
49093
Claim: If $(x_\alpha)_{\alpha\in A}$ is a collection of real numbers $x_\alpha\in [0,\infty]$ such that $\sum_{\alpha\in A}x_\alpha&lt;\infty$, then $x_\alpha=0$ for all but at most countably many $\alpha\in A$ ($A$ need not be countable).  Proof: Let $\sum_{\alpha\in A}x_\alpha=M&lt;\infty$. Consider $S_n=\{\alpha\in A \mid x_\alpha&gt;1/n\}$.  Then $M\geq\sum_{\alpha\in S_n}x_\alpha&gt;\sum_{\alpha\in S_n}1/n=\frac{N}{n}$, where $N\in\mathbb{N}\cup\{\infty\}$ is the number of elements in $S_n$.  Thus $S_n$ has at most $Mn$ elements.   Hence $\{\alpha\in A \mid x_\alpha&gt;0\}=\bigcup_{n\in\mathbb{N}}S_n$ is countable as the countable union of finite sets. $\square$  First, is my proof correct? Second, are there more concise/elegant proofs?
8761
I'm working on a task where I'm a bit unsure if the answer I've got is correct.  Here is the task:     Show by induction that the following assertion is true for all natural   numbers $n$      $n^3 - n$ is divisible by $3$   Here is my answer:     For $n = 1$,   $n^3 - n = 1 - 1$   which is divisible by $3$      Assume the statement is true for some number $n$, that is, $n^3 - n$   is divisible by $3$. Now,      $(n + 1)^3 - (n + 1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3(n^2 + n) = (n^3 - n) + 3n(n+1)$      which is $n^3 - n$ plus a multiple of $3$.      Since we assumed that $n^3 - n$ was a multiple of $3$, it follows that   $(n + 1)^3 - (n + 1)$ is also a multiple of $3$.      So, since the statement "$n^3 - n$ is divisible by $3$" is true for $n  = 1$, and its truth for $n$ implies its truth for $n + 1$, the statement is true for all whole number $n$.   I would appreciate if someone could go through the task and the answer and see if I've done this correctly.  Thanks a lot!
121709
Suppose $$ab \equiv 0 \pmod n$$ and that $a$ and $b$ are positive integers both less than $ n$. Does it follow that either $a | n$ or $b | n$?  If it does follow, give a proof.  If it doesn’t, then give an example.   For this question is this a suitable answer: No it doesn't. $3$ and $4$ are both less than $6$. $$3 \times 4 \equiv 0 \pmod {6}$$ but $4 \not \mid 6$.
123313
If $\gcd(a,n) = 1$ and $\gcd(b,n) = 1$, then $\gcd(ab,n) = 1$. Also... $a,b$ and $n$ are natural numbers.  I feel I should begin with EEA to multiply out the gcd's, but I don't know where to go from there...
31474
Could someone verify this proof?  Given the following definition of divisibility $(\forall{a,b \in \mathbb{N}})[a \mid b \equiv (\exists{c \in \mathbb{N}})(ac=b)]$.  Statement: $(\forall{a,b,c \in \mathbb{N}})[(a\mid b) \rightarrow (ac\mid bc)] $ .  Proof:  Let $a,b \in \mathbb{N}$ be arbitrary.  Assuming that $a\mid b$, we can conclude that $\exists{d \in \mathbb{N}}$ such that $ad = b$.  By Algebra we can deduce the following sequence of statements.  If $(ad)=b$, then $(ad)c=bc$.  Therefore $(ac)d=bc$.  Hence by the definition of divisibility we know that $ac\mid bc$.
69330
The natural numbers $a$ and $b$ are such $a^2+ab+1$ is divisible by $b^2+ba+1$. Prove that $a = b$.   I tried to algebraically manipulate it as follows:  $(b^2 + ba + 1)k = a^2 + ab + 1$  $[b(a + b) + 1]k = a(a + b) + 1$  $kb(a + b) + k = a(a + b) + 1$  $k - 1 = (a - kb)(a + b)$  I'm stuck here. What should I do next? A case-by-case analysis of possible congruencies would be too tedious and inelegant.
62760
what is the number of subsets of the set {k∈N|1≤k≤n} with no two consecutive numbers? The answer says: $$a_n=a_{n-1}+a_{n-2}$$ with the starting conditions: $$a_0=1, a_1=2$$1. why does $a_1=2$? $$$$ 2. How does this recursion was created, I understand that if $a_n$ mean all the places with no consecutive numbers so, $a_{n-1}$ come from the fact that after the first place all those places satisfy this condition, but why there is need to "look" at what happen after the two places?
55791
$A \subseteq \mathcal{R}(N)$ and given that (by inductive definition):   $N ∈ S$. If $a \in R$, then $R \setminus \{a\} \in A$.    I need to prove that for each $A \in S$, $N\setminus A$ is finite. How can I prove this formally?
36257
If a nonzero element $a$ of a ring $\mathbb{D}$ does not have a multiplicative inverse, then $a$ must be a zero divisor.   If $\mathbb{D}$ has finitely many elements, then the statement is true. However, I don't see why, as for the infinite case, 7 isn't a zero divisor only because every element $a &gt; 0$ when multiplied by a $b &gt; 0$ gives you $ab &gt; 0$ which has nothing to do with infinity or finite amounts of elements.
121339
Statement of the problem: Prove that if $A_1 \supseteq A_2 \supseteq A_3 \cdots$ are all finite, nonempty sets of real numbers, then the intersection $\bigcap_{n=1}^{\infty} A_n$ is also finite and nonempty.  My solution: $\bigcap_{n=1}^{\infty} A_n = \emptyset.$ Then at least one $A_n$ is disjoint from the rest - contradiction, since each $A_n \subseteq A_{n-1}.$ Next assume that the intersection has infinite cardinality - contradiction, since $A_n \supseteq \bigcap_{n=1}^{\infty} A_n,$ but we have $A_n$ finite.  This is a homework problem and this is what I will be turning in regardless of any answers I get. I would like to know if there is a direct proof of this claim. I had considered trying to show that $\exists x \in A_n$ for each choice of $n,$ which would show that the intersection is nonempty, but: a) I don't know how to do this, and b) I still would not be able to prove the intersection was finite except by contradiction.  Thanks!  edit: Moreover, we were told not to use induction on this problem. But if $A_1$ is finite, can't we reduce the collection of $A_n&#39;s$ to a subset of the power set of $A_1$ and then induct?
50394
Denote by $\mathbb{N}$ the set of natural numbers and by $2^{\mathbb N}$ the set of all subsets of $\mathbb N$. Let $E$ be some subset of $2^{\mathbb N}$ such that for  every pair of elements in $E$, one is a subset of the other. Clearly, $E$ could be countable by considering $E=\big\{\{1,\cdots, n\}, n\in\mathbb N\big\}$. My question is the following: could we find an example that $E$ is uncountable? Many thanks for the answer!
16166
I'm having trouble to prove the following question:  Supose $\{A_n\}_{n\in\mathbb{N}}$ is a family of sets such that $A_1\subset A_2\subset A_3\subset\ldots$ (it's possible to have $A_n=A_{n+1}$). I need to prove that $$\lim_{n\to\infty}A_n = A_1\cup\bigcup_{n=2}^\infty(A_{n}\backslash A_{n-1}).$$  I'm not sure if this is useful, but I proved that $A_{n}\backslash A_{n-1}$ and $A_{n'}\backslash A_{n'-1}$ are disjoint if $n\neq n'$.  Thank you.
104714
Is every set a subset of a larger set? In other words, for an arbitrary set S, can one always construct a set S' such that S is a proper subset of S'?  Is this question even meaningful?
74363
Find the number of Pairs $(A,B)$ of subsets of $[n]$ such that $A ⊆ B$? I just need clarification in my thought process. My professor's wording at times can through me off. I just want to know if I am on the right track. We will have $3$ regions: 1.Outside $B$ 2.Inside $A$ 3. Inside $B$, Outside $A$ I believe the number of pairs is $3^n$ but I am not sure. Any help would be appreciated.
3921
Let $A$ be a non-empty set and $n$ be the number of elements in $A$, i.e. $n:=|A|$.  I know that the number of elements of the power set of $A$ is $2^n$, i.e.  $|\mathcal{P}(A)|=2^n$.  I came across the fact that exactly half of the elements of $\mathcal{P}(A)$ contain an odd number of elements, and half of them an even number of elements.  Can someone prove this? Or hint at a proof?