I want to prove that     For every pair of positive integers $(m,n)$, the statement $m!n!(m+n)!|(2m)!(2n)!$ holds.   which is equivalent to     For every pair of positive integers $(m,n)$, the statement $$ \sum_{i=1}^{\infty}\left\lfloor\frac m{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac n{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac {m+n}{p^i}\right\rfloor \le\sum_{i=1}^{\infty}\left\lfloor\frac {2m}{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac {2n}{p^i}\right\rfloor$$ holds for every prime number $p$.   I have tried setting $m=ap+c,n=bp+d$ with $a,b,c,d$ nonnegative integers and $c,d&lt;p$. From that, the inequality becomes $$ a+\sum_{i=1}^{\infty}\left\lfloor\frac a{p^i}\right\rfloor+ b+\sum_{i=1}^{\infty}\left\lfloor\frac b{p^i}\right\rfloor+ a+b+\left\lfloor\frac{c+d}{p}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac{a+b}{p^i}+\frac {c+d}{p^{i+1}}\right\rfloor \\\le 2a+\left\lfloor\frac{2c}{p}\right\rfloor+\sum_{i=1}^{\infty}\left\lfloor\frac {2a}{p^i}+\frac{2c}{p^{i+1}}\right\rfloor\\+ 2b+\left\lfloor\frac{2d}{p}\right\rfloor+\sum_{i=1}^{\infty}\left\lfloor\frac {2b}{p^i}+\frac{2d}{p^{i+1}}\right\rfloor$$ $$\iff \sum_{i=1}^{\infty}\left\lfloor\frac a{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac b{p^i}\right\rfloor+ \left\lfloor\frac{c+d}{p}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac{a+b+\frac {c+d}{p}}{p^i}\right\rfloor \\\le \left\lfloor\frac{2c}{p}\right\rfloor+\sum_{i=1}^{\infty}\left\lfloor\frac {2a+\frac{2c}{p}}{p^i}\right\rfloor\\+ \left\lfloor\frac{2d}{p}\right\rfloor+\sum_{i=1}^{\infty}\left\lfloor\frac {2b+\frac{2d}{p}}{p^i}\right\rfloor\text.$$  After that, I tried splitting cases based on whether $2c\ge p$, whether $2d\ge p$, and whether $c+d\ge p$. The case where $2c&lt;p$, $2d\ge p$, and $c+d\ge p$ becomes $$\sum_{i=1}^{\infty}\left\lfloor\frac a{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac b{p^i}\right\rfloor+ 1+\sum_{i=1}^{\infty}\left\lfloor\frac{a+b+1}{p^i}\right\rfloor \le \sum_{i=1}^{\infty}\left\lfloor\frac {2a}{p^i}\right\rfloor+ 1+\sum_{i=1}^{\infty}\left\lfloor\frac {2b+1}{p^i}\right\rfloor$$ $$\iff \sum_{i=1}^{\infty}\left\lfloor\frac a{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac b{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac{a+b+1}{p^i}\right\rfloor \le \sum_{i=1}^{\infty}\left\lfloor\frac {2a}{p^i}\right\rfloor+ \sum_{i=1}^{\infty}\left\lfloor\frac {2b+1}{p^i}\right\rfloor$$ $$\iff \sum_{i=1}^{\infty}\left( \left\lfloor\frac a{p^i}\right\rfloor+ \left\lfloor\frac b{p^i}\right\rfloor+ \left\lfloor\frac{a+b+1}{p^i}\right\rfloor\right) \le \sum_{i=1}^{\infty}\left( \left\lfloor\frac {2a}{p^i}\right\rfloor+ \left\lfloor\frac {2b+1}{p^i}\right\rfloor\right)\text.$$  How to carry on from there?
115773
Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.   I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? Thank you.
85098
I need help!  I need to prove that for any $2 \le n,k$ positive integers $(n - 1)^2 \mid n^k -1$ if and only if $(n - 1) \mid k$  Thanks!
74644
If $l$ and $n$ are any positive integers, is there a  proof of the identity     $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$   which uses the Inclusion-Exclusion Principle?  (If necessary, restrict to the case where $l\ge n$.)    This question is closely related to   and also
53347
Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd.    I solve the problem in the following way: I assume that $m&gt;n$ then  $$a^{2^m}+1=a^{2^m}-1+2$$ With this expression if I take a divisor prime $p$ of $a^{2^n}+1$ then if $p|a^{2^m}+1$ this prime must divide 2 and the result follows.   But, how can I prove this statement without use of primes? This exercise appears before the concept of prime is introduced then I prefer do not use it.    Any idea?   Thanks!
75474
In Euclid's proof that there are infinitely many primes, the number  $p_1 p_2 ... p_n + 1$ is constructed and proved to be either a prime, or a product of primes greater than $p_n$.  Trivially, we could also use the number $R_n=p_1 p_2 ... p_n - 1$ to prove the theorem, for n>2.  Intuitively, as $n$ grows, the probability that $R_n$ is prime gets smaller. Is there a proof that $R_n$ is not prime for any $n$ greater than some integer $M$ ? Or conversely, that there is an infinite number of prime $R_n$ numbers?  A possibly equivalent question: Is there a prime number greater than $p_n$ and smaller than $R_n$ for any $n$ greater than some integer $M$ ?
104310
I need to prove that for every natural n that happens and the prove needs to be by induction, I wont prove for n=1 because its obvious,so lets move to n and n+1 $$ \frac{(2n!)}{(n!)^2} ≥ \frac{(4^n)}{(2n+1)} $$ the assumption for n+1 $$ \frac{(2n+2)!}{(n+1)!^2} ≥ \frac{(4^{n+1})}{2n+3} $$ now I dont now how to progress,I tried this for n+1 $$ \frac{(2n+2)(2n+1)(2n!)}{(n+1)!^2} ≥ \frac{(4^{n}4^1)}{(2n+1)+2)} $$ and had a suggestion to use $ 2n! = (n!) \prod _{n=n}^{2n}\:n\cdot )! $ but cant see how it helps,ty.
13134
There's a problem statement:     For each $m \in \mathbb{N}$, we construct a sequence $m_0$, $m_1$, $m_2,\dots$ denoted $S_m$, recursively via $m_0=m$ and      $$m_{i+1} = m_i + \left\lfloor \sqrt{m_i} \right\rfloor$$      for all $i \ge 0$.   Here, $\lfloor x \rfloor$ is the floor of $x$, the greatest integer less than or equal to $x$.   Hence, we have $\left\lfloor \sqrt{10} \right\rfloor=3$ and $\left\lfloor \sqrt{29} \right\rfloor=5$.      Show that for each positive integer $m$, the sequence $S_m$ contains the square of some integer.   I'm pretty certain that this can be proved with induction. I am just not quite sure what to induct on. Examining examples shows that $S_m$ always results in a perfect square eventually, though I'm not sure how to prove it.
94710
Given an integer $m=pq$, where $p,q$ are both primes such that $p\equiv 1 \pmod{4}, q\equiv 1 \pmod{4}$. It is known that $p$ can be written as a sum of two squares (of positive integers) in a unique way, and the same for $q$. Prove that $m$ can be written as a sum of two squares (of positive integers) in exactly two distinct ways.  Attempt  Notice that for positive integers $u,v,A,B$, we have \begin{align*}(u^2+v^2)(A^2+B^2)&amp;=(uA+vB)^2+(vA-uB)^2=(vA+uB)^2+(uA-vB)^2\end{align*} Therefore if $p=a^2+b^2,q=c^2+d^2$, then \begin{align*}m&amp;=(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(bc-ad)^2=(bc+ad)^2+(ac-bd)^2\end{align*} meaning that $m$ can be written as a sum of two squares (of positive integers) in at least two distinct ways.  How do I prove that there doesn't exist a third way of writing $m$ as a sum of two squares (of positive integers)?
37435
Call $P(k): k!&lt;k^k$, for $k\geq 2$ Test it out with 2, and it's true ($2&lt;4$).   Assume that $P(k)$ is true for some $k\geq2$.  Then show that $P(k+1)$ is true.   $P(k+1): (k+1)!&lt;(k+1)^{k+1}$  Ministep: $(k+1)!=k!(k+1)$ Ministep: $(k+1)^{k+1}=(k+1)^{k}(k+1)$    $k!(k+1)&lt;(k+1)^{k}(k+1)$  Can I just pull out that (k+1) and call it a day? That will make $k!&lt;(k+1)^{k}$.   We're already assuming that $k!&lt;k^k$, for some integer $k\geq 2$, and I don't think I need to prove that $k^{k}&lt;(k+1)^{k}$. I mean, I guess I could go prove that as well, but let's assume for the moment that I don't have to. Since we're assuming the original $P(k)$ is true, I should be able to write $k!&lt;k^{k}&lt;(k+1)^{k}$ right? That would prove the $k+1$ case. Is this the correct way to go about things? It seems too easy, but makes sense.  Thanks for confirmation and/or pointing out mistakes!
114720
I got stuck on this inequality for a day. If $p$ is positive integer, then the problem becomes too easy, but I can't find how we deal with the general case when p can be any positive number. Can someone give me a hint? I really appreciate     Prove that $|x^p - y^p| \le p|x-y|(x^{p-1} + y^{p-1})$ provided that $1 \le p \lt \infty$ and $x, y \ge 0$
24542
Problem: For positive integers $n,j,k$, prove that the following holds:     $$\left\lfloor\frac 1j\left\lfloor\frac nk\right\rfloor\right\rfloor=\left\lfloor\frac n{jk}\right\rfloor$$     I simply need hints to start on this problem. I have verified that it's indeed true by checking a few examples and I can't seem to find a counter-example, so I'm almost sure that the problem is indeed correct.  However, I can't seem to think of a proper (and rigorous) proof of this. Can someone please help me by giving me a few hints?  I want to prove it myself, so I'd appreciate if people don't directly post the proof themselves. Also, please keep your hints as subtle as possible (there's no fun in proving something if the hint gives out most of the answer) :D
6905
Let $(a_n)$ be a strictly increasing sequence of positive integers such   that: $a_2 = 2$ and $a_{mn} = a_m a_n$ for $m, n$ relatively prime. Show that $a_n = n$, for every positive integer $n$.   This is a result apparently due to Paul Erdős, and  has a proof by induction.  I tried like this, $a_{10}=a_2a_5$. After this what we can do?    [Editor's comment] Possibly due to the apparent simplicity of the conditions it may be difficult to appreciate the subtleties of this question. If we try and construct a counterexample like $a_3=4$, $a_4=5$, $a_5=6$, then the requirements dictate $a_6=8$, $a_{10}=12$, $a_{15}=24$. At this point we realize that we have been speeding. For monotonicity forces $a_9\le 11$, and therefore $a_{18}\le22&lt;a_{15}$, violating the requirements. It is not obvious why something similar ruins all the modifications to the sequence $a_n=n$. [/comment, JL]
97895
Prove that every positive integer $n$ has a unique expression of the form: $2^{r}m$ where $r\ge 0$ and $m$ is an odd positive integer  if $n$ is odd then $n=2^{0}n$, but I dont know what to do when $n$ is even  and to prove that this expression is unique is it a good choice to  use the fundamental theorem of arithmetic?  I would really appreciate your help
81416
I know that there is a similar post, but I 'm trying a different proof. I will write $P$  for the set of all positive prime numbers. Question: If $\phi$ is Euler's Phi Function, we want to find all $n \in \mathbb{Z^+}$ such that $\phi(n)=4$. Answer: Let $n=p_1^{n_1}\dotsb p_k^{n_k}\in \mathbb{Z}^+$ be the factorisation of $n$ in to primes. Then $$\phi(n)=p_1^{n_1-1} \dotsb p_k^{n_k-1}(p_1-1) \dotsb (p_k-1)=4.$$ So, for any $i \in \{1,2,\cdots,k\}$ we have $p_i-1|4$. Hence, $$p_i-1\in\{1,2,4\} \iff p_i\in \{2,3,5\} \subset P.$$ Now, we can see the primes that $n$ contains: $n=2^{n_1}3^{n_2}5^{n_3}$, where  $n_1,n_2,n_3 \in \mathbb{Z}^+$. So, \begin{align*} \phi(2^{n_1}3^{n_2}5^{n_3})=4 \iff \phi(2^{n_1})\phi(3^{n_2})\phi(5^{n_3})=4  \tag{*} \end{align*} The possible cases for $n_i$ are:  $n_1=1,2,3\implies \phi(2)=1,\phi(2^2)=2, \phi(2^3)=4$ respectively $n_2=1 \implies \phi(3)=2$ $n_3=1 \implies \phi(5)=4$  All the posible combinations for the relation (*) are $\phi(5)$, $\phi(5)\phi(2)$, $\phi(3)\phi(2^2)$, $\phi(2^3)$. So, $$n \in \{5,10,12,8\}.$$ Is this completely right? Thank you.
11458
Prove, by contradiction, that, if $n$ is a positive integer such that $n^3 − n − 6 = 0$, then, for every positive integer $m$ with $m \not = n$, $m^3  − m − 6 \not = 0$.    Proposition: If $n$ is a positive integer such that $n^3 − n − 6 = 0$, then, for every positive integer $m$ with $m \not = n$, $m^3  − m − 6 \not = 0$.  Hypothesis: $n$ is a positive integer such that $n^3 − n − 6 = 0$.  Conclusion: For every positive integer $m$ with $m \not = n$, $m^3  − m − 6 \not = 0$.    My workings  A (Hypothesis): $n$ is a positive integer such that $n^3 − n − 6 = 0$.  A1 ($\neg B$): There exists a positive integer $m$ with $m \not = n$ such that $m^3  − m − 6 = 0$.  A2: $n^3 - n = 6$  $\implies n(n^2 - 1) = 6$ where $n \in \mathbb{Z}^+$  A3: $m^3 - m = 6$  $\implies m(m^2 - 1) = 6$ where $m \in \mathbb{Z}^+$ and $m \not = n$.  A4: $n(n^2 - 1) = m(m^2 - 1)$ where $m \not = n$.  $\implies \dfrac{n(n^2 - 1)}{m(m^2 - 1)} = 1$ where $m \not = n$.  Since $m,n \in \mathbb{Z}^+$, $(n^2 - 1) \ge 0$ and $(m^2 - 1) \ge 0$. Therefore, $n(n^2 - 1) = m(m^2 - 1)$ iff $n = m$.   Contradiction.  $Q.E.D.$    I would greatly appreciate it if people could please take the time to provide feedback on the correctness of my proof. Given that $m \not = n$, did I construct my proof correctly? Or is it incorrect to structure it this way if $m \not = n$?
110000
How can I prove that $n!&lt;n^n$ for every $n&gt;1$ using the induction principle?  If I put $n=2$ I get $2&lt;4$ so I know that $n!&lt;n^n$ is true.  Now I don't know how to prove that $(n+1)!&lt;(n+1)^{n+1}$. I can write $(n+1)!=n!(n+1)$ but then I don't know how to go on.
119892
i know that|$S_n$|=$n!$ and |$A_n$|= $\frac{n!}{2}$ but i'm not sure where to go from there. Thanks.