Show that infinitely many positive integer pairs $(m,n)$ exist such that $\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{N}$.  I couldn't solve it but I did make an observation which might or might not be helpful. WLOG assume that $m &lt; n$ (since the term is symmetric wrt $m,n$ along with the fact that ignoring the $m=n$ case wouldn't create any trouble). Write $n=mq+r$ for some $r\in \{[0,m-1]\cap \mathbb{N}\}$. Now, the question boils down to showing $\frac{m+1}{n}+\frac{r+1}{m} \in \mathbb{N}$. Note that each of the summand is $\leq 1$. Since the equality case wouldn't be helpful in generating infinitely many pairs of $(m,n)$, we can safely say that the sum is equal to $1$.  Now I don't know how to proceed from here.
123531
The question is:     Show that there are an infinite number of pairs $(m,n): m, n \in \mathbb{Z}^{+}$, such that: $$\frac{m+1}{n}+\frac{n+1}{m} \in \mathbb{Z}^{+}$$   I started off approaching this problem by examining the fact that whenever the expression was a positive integer, the following must be true:  $$\frac{m+1}{n}+\frac{n+1}{m} - \left\lfloor\frac{m+1}{n}+\frac{n+1}{m}\right\rfloor = 0$$  However, I was unable to do much more with this expression, so I abandoned it and started the problem again from a different angle.  Next I re-arranged the expression to state that:  $$\frac{m^2+m+n^2+n}{mn} \in \mathbb{Z}^{+} \implies \frac{m(m+1) + n(n+1)}{mn} \in \mathbb{Z}^{+}$$  And therefore:  $$mn \mid (m(m+1) + n(n+1))$$  However, I'm unsure how to demonstrate there are infinitely many occurances of $(m, n)$ for which this is true. So I'd appreciate any help.   Thanks in advance
60337
Here's the full question:  Prove that, for any $n + 1$ integers, $\{x_0, x_1, x_2, . . . , x_n\}$, there exist two integers $x_i$ and $x_j$ with $i \neq j$ such that $x_i − x_j$ is divisible by $n$.  Now, the integers aren't necessarily consecutive, positive, or without repeats. I've tried breaking this into cases, such as "$x_i = x_j, \dfrac{0}{n} = 0$" etc. But I don't think it's possible to exhaust the cases.  I feel like there should be an easy way to contradict this one, by saying that $x_i - x_j$ isn't divisible by $n$. But I just wasn't getting anywhere with that one.  I thought about using induction, but I would have just as hard a time proving this for $n$ integers before $n+1$ integers, so I don't think it would be possible for me to do it that way.  If anyone could help out, that would be wonderful. I'm pretty stuck here.
80346
I'm having some trouble proving the following proposition:  Let $m \in \mathbb N$ and $a,b,k \in \mathbb Z$, then: $$ka \equiv kb \pmod{m} \iff a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$$  I began by trying to prove that $a \equiv b \pmod{\frac{m}{\gcd(k,m)}} \implies ka \equiv kb \pmod{m}$ but I got stuck with: $$a\gcd(k,m) \equiv b \gcd(k,m) \pmod{n}$$ Then I also tried to prove that $ka \equiv kb \pmod{m} \implies a \equiv b \pmod{\frac{m}{\gcd(k,m)}}$ But I also was not able to conclude anything. This is my first time learning modular arithmetic and I'm still confused with the concepts and have no intuition with this at all, this is perhaps why I'm having some trouble solving these types of questions. How can I prove this?
76288
Problem:Let $k$ be an odd positive integer. Prove that $(1+2+3...+n)|(1^k+2^k+3^k+...+n^k)$ for all positive integers $n$.  My Attempt: Proof (By Induction on $k$): Let $P(k)$ be the proposition that $(1+2+3...+n)|(1^k+2^k+3^k+...+n^k)$ for all positive integers $n$ when $k$ is odd. Then $P(1)$ and $P(3)$ are trivially true. So for $k\geq 5$, we assume that $P(k)$ holds. We would like to show that $P(k+2)$ also holds. In order to do that consider the following sums  $$1^{2}(1^k+2^k+3^k+...+n^k)=1^{k+2}+2^k+3^k+...+n^k$$ $$2^{2}(1^k+2^k+3^k+...+n^k)=2^2*1^k+2^{k+2}+2^2*3^k+...+2^2*n^k$$ $$..$$ $$n^2(1^k+2^k+3^k+...+n^k)=n^2*1^k+n^2*2^k+n^2*3^k+...+n^{k+2}$$ Note that $$1^2(1^k+2^k+3^k+...+n^k)+2^2(1^k+2^k+3^k+...+n^k)+...+n^2(1^k+2^k+3^k+...+n^k)\equiv 0\pmod {\frac{n(n+1)}{2}}$$  Therefore, if we denote $\sum_{i=1}^{n}i^2=s$, then    $(t)(1^k+2^k+3^k+...+n^k)-t+\sum_{i=1}^{n}i^{k+2}\equiv 0\pmod {\frac{n(n+1)}{2}}$ which implies that $P(k+2)$ holds. Hence by PMI we are done.  Now I am a bit hesitant in convincing myself whether this proof is correct or not. This is because I have never seen induction performed in this manner. Any reasons as to why this argument falls would be much appreciated.
80050
This is a homework problem.  I tried proving this by means of induction. Verifying the case $n=1$ is easy, the only solution to $\frac{1}{x_1} = 1 $ is $x_1 = 1$, therefore there is only one, and thus a finite number of solutions. I am having some difficulties with proving that the case of $N+1$ follows from the $N$'th case (for some $N \in \mathbb{Z}_{>0}$), assuming that the sum only has a finite amount of solutions in $\mathbb{Z}_{&gt;0}$ (our induction hypothesis). Can you help me with this?   I am equally interested in any other way to prove that the given sum has only a finite number of solutions, whether it can be done by means of induction or not.  Thanks in advance!
109872
For fixed positive integers $m$ and $n$, let $$S=\sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n.$$Show that $S = 0$ if $n &lt; m$ and $S = n!$ if $n = m$.  I know that I have to use PIE(principle of inclusion and exclusion) and a counting argument. Here's my work so far:  There are $m$ people, $\binom{m}{k}$ represents all the ways to pick $k$ people out of $m$ people. $(m-k)^n$ represents all the ways of giving the people that weren't chosen nn distinguishable objects. What I don't get is how to apply PIE, why the signs are alternating, and how does  $S = 0$ if $n &lt; m$ and $S = n!$ if $n = m$. Could anyone offer an answer by the counting argument I started? Thanks!
70000
I have to prove that:     $$\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$$   I tried to open up the right side with Pascal's definition that: $$ { n \choose k} = {n-1 \choose {k}} + {n-1 \choose {k-1}}$$  Here is what I came up with, and I am sure it is wrong because it does not equal the left side:  $$ {m+n+1 \choose m+1} = {m+n \choose m+1} + {m+n \choose m} = ... ={m+n \choose m+1} + {m+n-1 \choose m} + {m+n-2 \choose m-1} + ... + {m \choose m+1} = \sum_{k=0}^{n} {m+k \choose m+k-n+1 }  $$  Which, again, probably is wrong because it is not equal $\sum_{k=0}^{n} { m+k \choose m}$. Any help is appreciated
93979
I need to prove that $\frac{(m+n-1)!}{m!n!}$ is an integer there is a question  which is similar to this question but i cant figure out how I can insert the '-1' in there. Thanks
106016
It seems known that there are infinitely many numbers that can be expressed as a sum of two positive cubes in at least two different ways (per the answer to this post: ).  We know that  $$1729 = 10^3+9^3 = 12^3 + 1^3,$$  and I am wondering if there are infinitely many numbers like this that can be expressed as the sum of two positive cubes in exactly two ways?  In fact, are there even any other such numbers?  EDIT: As provided by MJD in the comments section, here are other examples: $$4104 = 2^3+16^3 = 9^3+15^3,$$ $$13832 = 20^3+18^3=24^3+2^3,$$ $$20683 = 10^3 +27^3 = 19^3 +24^3.$$
68698
Do you have any idea to prove the following identity via a combinatorial (or algebraic) method?  $\sum_{n=r}^{n=\infty} {n \choose r}^{-1} = \frac{r}{r-1}$  This is  of the book Chen C.C., Koh K.M. Principles and techniques in combinatorics. The book does not give a solution, although it mentions: "see H. W. Gould, Combinatorial Identities, Morgantown, W.V. (1972), 18-19".  many thanks in advance, Shahram
60238
For any integer $a,b$ let $N_{a,b}$ denote the number of positive integer $x&lt;1000$ satisfying $x= a \mod 27$ and $x=b \mod 37$. Then which of them is correct         there exist $a,b$ such that $N_{a,b} =0$    for all $a,b$, $N_{a,b}=1$   for all $a,b$, $N_{a,b}&gt;1$   there exist $a,b$ such that $N_{a,b}$ and  there exist $a,b$ such that $N_{a,b}=2$.      Since we know that by Chinese Remainder Theorem if $m_1, m_2, .., m_k$ are pairwise relatively prime positive integers, and if $a_1, a_2, .., a_k$ are any integers, then the  simultaneous congruences $x ≡ a_1 (mod\;m_1), x ≡ a_2 (mod\;m_2), ..., x ≡ a_k (mod\;m_k)$ have a solution, and the solution is unique modulo $m$, where  $m = m_1m_2⋅⋅⋅m_k$. Then how we will approach by acoording to this theorem. So please someone help me and explain it.
75196
I am trying to find a way for the positive integers written as the sum of other positive integers.( expressed in terms of some functions)  I searched a bit and I came across with  But in my case the order matters. What I mean is for example if we write for 4,  there would be 7 ways to express 4 as;           1 + 3           2 + 2           3 + 1           1 + 1 + 2           1 + 2 + 1            2 + 1 + 1           1 + 1 + 1 + 1   Can anyone guide me in approaching to the solution of my problem? Thanks in advance.
1448
Apparently $1+2+3+4+\ldots+n = \dfrac{n\times(n+1)}2$.  How? What's the proof? Or maybe it is self apparent just looking at the above?   PS: This problem is known as "The sum of the first $n$ positive integers".
104287
Show there are infinitely many primes that are equivalent to $1 \pmod{8}$.  Hello there! I have been trying to do this problem for a pretty long time with no avail.    I noticed that this is really similar to Euclid's proof that there are infinitely many primes.  However, I can't find a way to use that here.  Can anyone help me?
100338
I have a question with regards to combinatorics. I am supposed to show the following combinatorial identity: $\sum\limits_{r=0}^n\binom{n}{r}\binom{m+r}{n}=\sum\limits_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$.   The algebraic way is to consider the coefficient of $t^m$ in the expansion of $(1+t)^n(1-t)^{-(n+1)}$. For $r\in\{0,1,\cdots,n\}$, we have the coefficient of $t^{n-r}$ in the expansion of $(1+t)^n$ to be equal to $\binom{n}{r}$, and the coefficient of $t^{m+r-n}$ in the expansion of $(1-t)^{-(n+1)}$ to be equal to $\binom{m+r}{n}$. By the addition and multiplication principles this will show that the coefficient of $t^m$ in the expansion of $(1+t)^n(1-t)^{-(n+1)}$ will be equal to $\sum\limits_{r=0}^n\binom{n}{r}\binom{m+r}{n}$.  On the other hand, we note that $(1+t)^n(1-t)^{-(n+1)}=(1+\frac{2t}{1-t})^n(1-t)^{-1}=\sum\limits_{r=0}^n\binom{n}{r}2^rt^r(1-t)^{-(r+1)}$. As the coefficient of $t^{m-r}$ is equal to $\binom{m}{r}$, this implies that the coefficient of $t^m$ in the expansion of $(1+t)^n(1-t)^{-(n+1)}$ is equal to $\sum\limits_{r=0}^n\binom{n}{r}\binom{m}{r}2^r$.  What I am thinking of, is to think of a way to prove this identity without the use of the generalized binomial series. I was trying to think of a combinatorial method to solve this problem. In particular, I was trying to prove the combinatorial identity as follows:  Firstly, let us be given a class of $n$ boys and a class of $m$ girls, where $n\leq m$. Choose a team $A$ of $r$ boys, and choose a team $B$ of $r$ girls, and finally choose any subset (may be empty) of boys from $A$ to clean the classroom, where $r\in\{0,1,\cdots,n\}$. For each value of $r$, we see that there are $\binom{n}{r}$ choices for $A$, $\binom{m}{r}$ choices for $B$, and subsequently there are $2^r$ ways to choose a subset from $A$. In this way we get the number of ways to do so to be equal to the expression on the RHS of the identity.  What I am struggling though, is to be able to count the number of desired ways in a way that will give me the expression on the LHS of the identity. I tried firstly to choose the boys to clean the classroom before choosing the sets $A$ and $B$, but I wound up with some messy expression that does not seem close to matching the expression on the LHS.  I would like to know if there is another way of looking at this method (or I could have been missing out on something), or if there is any other combinatorial method (or any other algebraic method that does not involve the use of generalized binomial series) that one could think of to show the desired identity.
122461
Let $p(n)$ denote the largest prime factor of $n$. Prove that there are infinitely many $n$ such that $$p(n)&lt;p(n+1)&lt;p(n+2).$$  Edit:   My solution: Choose $n=\prod_{i=1}^{k}p_i$, product of the first $k$ primes. This means that $n+1=\prod_{i=1}^{k}p_i+1$ is either a larger prime or has a prime factor larger than that of all factors of $n$. Still not sure about $n+2$.
81669
If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$.   I have no idea to solve this question. Please help me to solve the problem.