Show that if $x, y, z$ are positive integers, then $(xy+1)(yz+1)(zx+1)$ is a perfect square if and only if $xy+1$, $yz+1$, $zx+1$ are all perfect squares.

Click for solution Ok then, I'll rewrite it more detailed. The if part is trivial. For the only if part, assume $ x,y,z$ are such integers with $ xy + 1, yz + 1, zx + 1$ not all perfect squares, moreover pick them such that $ x + y + z$ is minimal. Without loss of generality $ xy + 1$ isn't a perfect square. Now let $ t$ be the smallest positive root of $ t^2 + x^2 + y^2 + z^2 - 2(xy + yz + zt + tx + zx + ty) - 4xyzt - 4 = 0$, an equation which rewrites equivalently as \[ \\ (x + y - z - t)^2 = 4(xy + 1)(zt + 1), \\ (x + z - y - t)^2 = 4(xz + 1)(yt + 1), \\ (x + t - y - z)^2 = 4(xt + 1)(yz + 1). \] But our quadratic equation has roots $ t = x + y + z + 2xyz\pm 2\sqrt {(xy + 1)(yz + 1)(zx + 1)}$, which is given to be integer, so the right hand side is a square each time. But then the left hand side needs to be a square, which gives that $ (xt + 1)(yt + 1)(xy + 1)$ is a perfect square. Now, since the centered equations above tell us that $ xt + 1\ge0,yt + 1\ge0,zt + 1\ge0$, we have $ t\ge - \frac1{\max(x,y,z)} > - 1$ (since $ x = y = z = 1$ isn't a solution). If $ t = 0$, then working out the formula for $ t$ gives $ (x + y + z)^2 = 4(xy + yz + zx + 1)$ or $ (x + y - z)^2 = 4(xy + 1)$, which means $ xy + 1$ is a square, contradiction, so we have $ t > 0$ and by the minimality of $ x + y + z$ we must have $ t\ge z$. But for the two roots $ t,t'$ of our quadratic equation we have by de Viete that $ tt' = x^2 + y^2 + z^2 - 2xy - 2yz - 2zx - 4 < z^2 - x(2z - x) - y(2z - y) < z^2$, contradiction. keywords: vieta

Find infinitely many triples $(a, b, c)$ of positive integers such that $a$, $b$, $c$ are in arithmetic progression and such that $ab+1$, $bc+1$, and $ca+1$ are perfect squares.

Click for solution Maybe not hard,but I spend 1 hour to solve it..... We know that there exist infinitely many solution for the Pell's Equation: $v^2-3u^2=1$ Let $a=v+2u,b=-v+2u,c=2u$,(we can check that $a,b,c>0$) then $ab+1=4u^2-v^2+1=u^2$, $bc+1=4u^2-2uv+1=u^2-2uv+v^2-1+1=(u-v)^2$, $ac+1=4u^2-2uv+1=u^2+2uv+v^2-1+1=(u+v)^2$

Let $a$ and $b$ be positive integers such that $ab+1$ divides $a^{2}+b^{2}$. Show that \[\frac{a^{2}+b^{2}}{ab+1}\] is the square of an integer.

Click for solution the problem is not too hard because the method of vieta-jumping is much more known today than 20 years before. first we take \[\frac{a^{2}+b^{2}}{ab+1}=k.\] so we can write instead \[a^{2}+b^{2}-kab-k=0.\] we assume $a>b$ ($a=b$ implies $\frac{2a^{2}}{a^{2}+1}\in\mathbb{Z}$ so $a=b=1$ and $k=1$.) we take the equation as a quadratic function in $a$. if we assume that there is a solution $a,b$ (otherwise the problem would be trivial), we have the solutions $a_{1}, a_{2}$ with $a_{1}=a$. wmls the equations $a_{1}+a_{2}=kb$ and $a_{1}a_{2}=b^{2}-k$ hold (vieta). we want to show $a_{2}\geq 0$. so we assume $a_{2}<0$ so $b^{2}-k<0$ so $k>b^{2}$. since $a_{1}>kb>b^{3}$ we get $ab+1>b^{4}+1$ which is a contradiction to \[ab+1 | b^{2}(a^{2}+b^{2})=b^{4}+1+(ab-1)(ab+1).\] so i can assume $a_{2}\geq 0$. because of $a_{1}a_{2}=b^{2}-k<b^{2}$ and $a_{1}>b$ $a_{2}<b$ holds. so we have created a new solution $a,b$ with $a<b$. We can re-do this until one of the numbers is $0$. Since the $k$ doesn't change we get $k=\frac{a^{2}}{1}=a^{2}$ which is a perfect square. Naphthalin

If $a, b, c$ are positive integers such that \[0 < a^{2}+b^{2}-abc \le c,\] show that $a^{2}+b^{2}-abc$ is a perfect square.

Click for solution Let me rewrite that a bit easier. Assume there exists $ a,b,c,q > 0$ with $ c\ge q$ such that $ a^2 + b^2 - abc = q$ but $ q$ is not a perfect square (else there is nothing to prove). Take them such that $ a + b$ is minimal and assume wlog $ a\ge b$. Solving this equation for $ a$ we get two roots: $ a,a' = \frac {bc\pm \sqrt {b^2c^2 - 4(b^2 - q)}}2$, and since one is integer, so is the other. Since $ bc(a - bc) + b^2 - q\ge bc + b^2 - q\ge b^2 + (b - 1)c\ge0 = a(a - bc) + b^2 - q$ we need $ bc\ge a$ and thus $ b^2 > q$ (since $ q\not = b^2$ by assumption) and thus $ a,a' > 0$. Now $ a' + b\ge a + b$ by minimality of $ a + b$, while $ aa' = b^2 - q\le b^2$ by de Vieta, so $ a'\le b$. As we had $ a'\ge a\ge b$, we have $ a' = b = a\Rightarrow q = 0$, contradiction.

Let $x$ and $y$ be positive integers such that $xy$ divides $x^{2}+y^{2}+1$. Show that \[\frac{x^{2}+y^{2}+1}{xy}=3.\]

Click for solution I'll write Napthalin's solution a bit easier for you. Assume there exists $ x,y,k > 0$ with $ x^{2} - kxy + y^{2} + 1 = 0$ (else there is nothing to prove), and take the pair $ (x,y)$ where $ x + y$ is minimal, wlog $ x\ge y$. If $ x = y$ or $ y = 1$ we easily get $ x = y = 1$ and $ k = 3$. For $ k\not = 3$ (by AM-GM this is $ k > 3$) we have $ y > 1$, so solving for $ x$ we get two positive roots $ x,x' = \frac {ky\pm\sqrt {k^2y^2 - 4y^2 - 4}}{2}$. By the minimality of $ x + y$, we need $ x'\ge x > y$, while de Vieta tells us $ xx' = y^2 + 1$, contradiction.

Find infinitely many pairs of integers $a$ and $b$ with $1<a<b$, so that $ab$ exactly divides $a^{2}+b^{2}-1$. With $a$ and $b$ as above, what are the possible values of \[\frac{a^{2}+b^{2}-1}{ab}?\]

Click for solution a) the equation is symmetric in $a$ and $b$. $(2,3)$ is a solution with $k=2$. by vieta-jumping we get for the 2 zeroes $a_{1}$ and $a_{2}$ of $a^{2}+b^{2}-1=kab$ the equations $a_{1}+a_{2}=kb$ and $a_{1}a_{2}=b^{2}-1$. so $a_{2}>b$ for $k>1$. now we change $a$ and $b$ and get infinitely many pairs $(a,b)$. if we want to we could name them exactly... b) we want to show that all positive numbers greater than 1 are possible. so we set $a=k$ and $b=k^{2}-1$ where $k\in\mathbb{N}>1$: \[\frac{a^{2}+b^{2}-1}{ab}=\frac{k^{2}+k^{4}-2k^{2}+1-1}{k(k^{2}-1)}=\frac{k^{2}(k^{2}-1)}{k(k^{2}-1}=k\] $a$ and $b$ are greater than $1$ so $a^{2}+b^{2}-1>ab$ so we get $k>1$. Naphthalin

Let $n$ be a positive integer such that $2+2\sqrt{28n^2 +1}$ is an integer. Show that $2+2\sqrt{28n^2 +1}$ is the square of an integer.

Click for solution Peter wrote: Let $n$ be a positive integer such that $2+2\sqrt{28n^{2}+1}$ is an integer. Show that $2+2\sqrt{28n^{2}+1}$ is the square of an integer. One may slightly generalize the above problem: [Proposition] Let $p \equiv-1(mod \; 4)$ be a prime. Suppose that $2+2\sqrt{4p n^{2}+1}$ is an integer for some integer $n$. Then, $2+2\sqrt{4p n^{2}+1}$ is the square of an integer. [Proof] Since $4p n^{2}+1$ is an odd integer, we write \[4p n^{2}+1=(2u+1)^{2}\;\; \text{or}\;\; pn^{2}=u(u+1),\] where $u \in Z$. Then, we have $p \; \vert \; u$ or $p \; \vert \; u+1$ because $p$ is prime. However, $p \; \vert \; u+1$ is impossible. Assuming that $p \; \vert \; u+1$, we see that $gcd(u, u+1)=1$ and $u(u+1)=pn^{2}$ imply that $(u,u+1)=(a^{2}, pb^{2})$, $a, b \in Z$ so that \[a^{2}-pb^{2}=-1 \;\; \text{or}\;\; a^{2}\equiv-1 (mod \; p).\] This contradicts for the fact that $p \equiv-1(mod \; 4)$ or that $-1$ is a quadratic nonresidue modulo $p$. Hence, we conclude that $p \; \vert \; u$. In this case, we get $(u,u+1)=(pc^{2}, d^{2})$ for some $c, d \in Z$. It therefore follows that \[2+2\sqrt{4p n^{2}+1}=2+2(2u+1)=2+2(2d^{2}-1)=(2d)^{2}.\]

The integers $a$ and $b$ have the property that for every nonnegative integer $n$ the number of $2^n{a}+b$ is the square of an integer. Show that $a=0$.

Click for solution Probably this is what Hawk Tiger meant, written out. edriv wrote: For each n: $ 2^{n}a + b$ is a perfect square $ \Rightarrow 4(2^{n}a + b) = 2^{n + 2}a + 4b$ is a perfect square. Also $ 2^{n + 2}a + b$ is a perfect square. Then we have two perfect squares at distance $ 3b$. We con construct arbitrary large perfect squares with distance $ 3b$. But this is impossible, then: - the distance is 0, $ b = 0$, but then $ a,2a$ are both perfect squares $ \Rightarrow a = 0$ - then our squares are not arbitrary large: $ a = 0$.

Prove that among any ten consecutive positive integers at least one is relatively prime to the product of the others.

Click for solution Clearly the only common prime factors amongst 10 consecutive positive integers will be 2,3,5,7. 5 of them will be divisible by 2, at least one of which must also be divisible by 3 and at least one of which must also be divisible by 5, and, if two of the numbers are divisible by 7, one of them will be even. This leaves two multiples of 3, one multiple of 5, and one multiple of 7 unaccounted for, enough factors to dish out to 4 more of our integers. But this still leaves one integer not divisible by 2,3,5,7, and therefore co-prime with all other integers of the set, and so coprime with their product.

Let $n$ be a positive integer with $n \ge 3$. Show that \[n^{n^{n^{n}}}-n^{n^{n}}\] is divisible by $1989$.

Click for solution We consider $n^{n^{n^n}}=n^{n^n}$ in $\mathbb{Z}_m$ for coprime integers m=9, 13, 17, and the result will follow from the Chinese Remainder Theorem. Lemma: If $n$ is coprime with $m$, then, dividing by $n^{n^n}$ (which I may do since m and n are coprime), I must prove that $n^{n^{n^n}-n^n}\equiv 1\mod m$, which one can reduce, by Euler-Fermat, to showing that $\phi(m)|n^{n^n}-n^n$ For 9, if 3|n it is trivial, so we consider when 3 and n are coprime. Using the lemma, we must show $6|n^{n^n}-n^n$. Modulo 2 this is either 0-0 or 1-1, both of which are clearly zero. Modulo 3, since $n^2\equiv 1$ by FLT, if $n$ is even we get 1-1, and if $n$ is odd we get n-n, so in both cases we get a zero, so $2*3|n^{n^n}-n^n$ and we are done. For 13, again, if 13|n then it is trivial, so we assume 13 and n are coprime. Again we can apply the lemma and must show $12|n^{n^n}-n^n$, but we showed 3 works already, so it remains to show $4|n^{n^n}-n^n$. If n is even this is obvious. If n is odd, then $n^2 \equiv 1 \mod 4$ so $n^{n^n}-n^n \equiv n-n \equiv 0$ and we are done. For 17, clearly if 17 divides n then we are done, so let us suppose it is not, so n must be coprime to 17. If $n$ is even, $n\geq 4$, so $16|n^n$, since $2^4=16$. But then by Fermat's Little Theorem the above equation reduces to $1=1$ which is clearly true. If $n$ is odd, then I use the lemma. $n^{n^n}-n^n=n^n(n^{n^n-n}-1)$. Now, since $n^2\equiv 1 \mod 8$ for all odd n, $n^n\equiv n \mod 8$ for all odd n, so $8|n^n-n$, and $\phi(16)=8$, so since 2|n, n being coprime to 16, Euler's Theorem states that $(n^{n^n-n}-1) \equiv 0 \mod 16$, which is $\phi(17)$, so we are done.

Let $a, b, c, d$ be integers. Show that the product \[(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)\] is divisible by $12$.

Let $k,m,$ and $n$ be natural numbers such that $m+k+1$ is a prime greater than $n+1$. Let $c_{s}=s(s+1).$ Prove that the product \[(c_{m+1}-c_{k})(c_{m+2}-c_{k})\cdots (c_{m+n}-c_{k})\] is divisible by the product $c_{1}c_{2}\cdots c_{n}$.

Click for solution nicetry007 wrote: The product $ (c_{m+1}-c_{k})\; (c_{m+2}-c_{k})\;\cdots\; (c_{m+n}-c_{k})\;$ $ = \left((m+1)(m+2)-k(k+1)\right)\;\left((m+2)(m+3)-k(k+1)\right)\;\cdots \left((m+n)(m+n+1)-k(k+1)\right)$ $ = (m+1-k)(m+k+2)\; (m+2-k)(m+k+3)\;\cdots\;(m+n-k)(m+k+n+1)$ $ = \Pi_{i =1}^{n}(m+i-k) \;\Pi_{i=1}^{n}(m+k+i+1)$ The product $ c_{1}\;c_{2}\; \cdots \; c_{n}= (1 \cdot 2)\; (2 \cdot 3)\; \cdots \; (n \cdot (n+1))\; = n! (n+1)!$ The ratio $ \frac{(c_{m+1}-c_{k})\; (c_{m+2}-c_{k})\;\cdots\; (c_{m+n}-c_{k})\;}{c_{1}\;c_{2}\; \cdots \; c_{n}}$ $ = \frac{\Pi_{i =1}^{n}(m+i-k) \;\Pi_{i=1}^{n}(m+k+i+1)}{n! (n+1)!}$ $ = \;^{(m+n-k)}C_{n}\;\cdot \; \left( \frac{1}{m+k+1}\right) \;\cdot \;^{(m+k+n+1)}C_{ n+1}$ Since $ n+1\; < \;m+k+1$, the binomial term $ ^{(m+k+n+1)}C_{ n+1}$ is divisible by $ (m+k+1)$. Hence, $ \left( \frac{1}{m+k+1}\right) \;^{(m+k+n+1)}C_{ n+1}$ is an integer and the product $ (c_{m+1}-c_{k})\; (c_{m+2}-c_{k})\;\cdots\; (c_{m+n}-c_{k})\;$ is divisible by $ c_{1}\;c_{2}\; \cdots \; c_{n}$.

Show that for all prime numbers $p$, \[Q(p)=\prod^{p-1}_{k=1}k^{2k-p-1}\] is an integer.

Let $n$ be an integer with $n \ge 2$. Show that $n$ does not divide $2^{n}-1$.

Click for solution Solution by Christian Hirsch (similar, but still different): Assume that $n$ is the smallest number $>1$ with that property. Then let $k = \gcd(n,\varphi(n)) <n$ and see that $2^k \equiv 1 \mod n$ (by $2^n , 2^{\varphi(n)} \equiv 1 \mod n$), thus $k|2^k-1$. By minimality we have $k=1$, giving $2 \equiv 1 \mod n$, contradiction.

Suppose that $k \ge 2$ and $n_{1}, n_{2}, \cdots, n_{k}\ge 1$ be natural numbers having the property \[n_{2}\; \vert \; 2^{n_{1}}-1, n_{3}\; \vert \; 2^{n_{2}}-1, \cdots, n_{k}\; \vert \; 2^{n_{k-1}}-1, n_{1}\; \vert \; 2^{n_{k}}-1.\] Show that $n_{1}=n_{2}=\cdots=n_{k}=1$.

Click for solution Here is an other method. $ x = lcm(n_1,..,n_k)$ So $ n_i|2^x - 1,\forall i = 1,..,k$ Imply that $ x|2^x - 1$ So $ x = 1$ (tradition!) http://www.mathlinks.ro/Forum/viewtopic.php?p=849217#849217

Determine if there exists a positive integer $n$ such that $n$ has exactly $2000$ prime divisors and $2^{n}+1$ is divisible by $n$.

Click for solution The answer is yes. First, we prove inductively that: $ 3^m|2^{3^m} + 1$ For $ m = 1$ it's clear. Now, we see that: $ 2^{3^{m + 1}} + 1 = (2^{3^m} + 1)(2^{23^{m}} - 2^{3^m} + 1)$ $ 3^m|2^{3^m} + 1$ from the induction hypothesis and the other bracket is divisible by $ 3$, as one can easily verify. So we are done. Now we prove that for $ a \in \mathbb{Z}_ +$ ($ a > 2$) the number $ a^3 + 1$ has a prime divisor which is not prime divisor of $ a + 1$. To prove this, see that $ (\frac {a^3 + 1}{a + 1}, a + 1)|3$ and $ \frac {a^3 + 1}{a + 1}$ is not power of $ 3$ if $ a > 1$ since it is never divisible by $ 9$. Now, we will prove inductively that there exist a number $ n$ such that: $ n = 3^{s}p_1p_2...p_k$ and $ n|2^{n} + 1$ (induction on $ k$). For $ k = 0$ we of course have $ 3|2^3 + 1$. So suppose that for $ k \geq 1$ such number $ n$ exists and see that: $ 2^{3n} + 1 = (2^n + 1)(2^{2n} - 2^n + 1)$. As we proved before, the number $ 2^{3n} + 1$ has a prime divisor which is not prime divisor of $ 2^n + 1$ (so it is not any of the $ p_1, p_2, ..., p_k$). Call it $ p_{k + 1}$. Since $ p_{k + 1}$ is odd it is obvious that for $ i = 1,2,...,k$ we have $ p_i|2^{3np_{k + 1}} + 1$. We have also proved, at the beggining that $ 3^{s + 1}|2^{3^{s + 1}p_1p_2...p_k} + 1$. So $ m = 3^{s + 1}p_1p_2...p_{k + 1}$ also works and we are done with the induction. To end the proof it of course sufficies to take $ k = 1999$.

Let $m$ and $n$ be natural numbers such that \[A=\frac{(m+3)^{n}+1}{3m}\] is an integer. Prove that $A$ is odd.

Let $m$ and $n$ be natural numbers and let $mn+1$ be divisible by $24$. Show that $m+n$ is divisible by $24$.

Click for solution Seems a little straightforward. In $\mathbb{Z}_8$, $mn=-1$ has solutions $\{m,n\}=\{1,7\},\{3,5\}$ and in both cases $m+n=0$. In $\mathbb{Z}_3$, $mn=-1$ has solution $\{m,n\}=\{1,2\}$ and again $m+n=0$, so $24|m+n$.

Let $f(x)=x^3 +17$. Prove that for each natural number $n \ge 2$, there is a natural number $x$ for which $f(x)$ is divisible by $3^n$ but not $3^{n+1}$.

Determine all positive integers $n$ for which there exists an integer $m$ such that $2^{n}-1$ divides $m^{2}+9$.

Click for solution A number of the type $m^2+9$ can, with exception of $p=3$, only have prime divisors $p \not \equiv -1 \mod 4$: If $q \equiv -1 \mod 4$ and $q \neq 3$, we have $3$ invertible $\mod q$ and get $m^\prime^2 \equiv -1 \mod q$ with $m^\prime \equiv m \cdot 3^{-1} \mod p$. But now we easily derive a contradiction with Fermat's little theorem: $1 \equiv m^\prime^{p-1} = (m^\prime^2)^\frac{p-1}2 \equiv (-1)^\frac{p-1}2 \equiv -1 \mod p$. Claim: exactly those $n$ being a power of two work. If $n$ has any odd prime divisor $q$, then $2^q-1 | 2^n-1$, so we just have to disprove the possibility of $2^q-1|m^2+9$ for $q$ any odd prime. Since $q>1$, $2^q-1 \equiv -1 \mod 4$, thus there is a prime $p \equiv -1 \mod 4$ dividing $2^q-1$. If we would have $p=3$, then $2^2 \equiv 1 \mod p$ yielding $1 \equiv 2^q \equiv 2^{q \mod 2} \equiv 2^1 \mod p$, impossible. Thus $p>3$, but now $p$ has to divide $m^2+9$, impossible by the above. We are left to prove that all $n=2^k$ work and do so by induction on $k$: $k=1$ gives the number $3$ which obviously works with $m_1=3$. If we have found $m_k$ with $m_k \equiv -9 \mod (2{}^{2{}^k}-1)$, we see that $2{}^{2{}^{k+1}}-1=(2{}^{2{}^k}+1)(2{}^{2{}^k}-1)$ and that these two factors are coprime. By the chinese remainder theorem we find $m_{k+1} \equiv m_k \mod (2{}^{2{}^k}-1)$ and $m_{k+1} \equiv 2{}^{2{}^{k-1}} \mod (2{}^{2{}^k}+1)$ and this one works.

Let n be a positive integer. Show that the product of $ n$ consecutive positive integers is divisible by $ n!$

Click for solution Consider the binomial coefficient $\binom{m}{n} = \frac{m(m-1)...(m-n+1)}{n!}$. It is an integer for all m, so we are done for positive sequences of integers. Clearly this proof works also for strictly negative sequences, and in the case where one of the integers is 0, the product will be 0, and hence divisible by anything.

Prove that the number \[\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}\] is not divisible by $5$ for any integer $n\geq 0$.

Click for solution Peter wrote: Prove that the number \[\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}\] is not divisible by $5$ for any integer $n\geq 0$. [Observation] We evaluate the the combinatorial sum \[B_{n}= \sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{3k}\] by finding a non-cominatorial expression. By Binomial Theorem, setting \[P_{n}= \sum_{0 \leq i \leq 2n+1, \; i \tex{: \;odd}}\binom{2n+1}{i}\left( 2^{\frac{3}{2}}\right)^{i}\;\; \text{and}\;\; G_{n}= \sum_{0 \leq k \leq 2n+1, \; i \tex{: \;even}}\binom{2n+1}{i}\left( 2^{\frac{3}{2}}\right)^{i},\] we obtain \[\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}= P_{n}+G_{n}= 2^{\frac{3}{2}}B_{n}+G_{n}\] and \[\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}=P_{n}-G_{n}=2^{\frac{3}{2}}B_{n}-G_{n}.\] Adding these two identities and multiplying $2^{-\frac{5}{2}}$, we obtain \[B_{n}= 2^{-\frac{5}{2}}\left(\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}+\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}\right).\] The right hand side is the desired non-combinatorial expression. [Solution] Our aim is to show that $B_{n}$ is not congruent to $0$ modulo $5$. We need his 'integral' girl friend $G_{n}$. Multiplying the above two indentities, we obtain \[7^{2n+1}=\left( 2^{\frac{3}{2}}+1 \right)^{2n+1}\left( 2^{\frac{3}{2}}-1 \right)^{2n+1}= 8{B_{n}}^{2}-{G_{n}}^{2}.\] Our next job is, of course, to read the above equation modulo $5$. Since $7^{2n+1}\equiv (7^{2})^{n}\cdot 7 \equiv (-1)^{n}\cdot 2 \; (mod \; 5)$, we obtain \[\pm 2 \equiv 8{B_{n}}^{2}-{G_{n}}^{2}\; (mod \; 5).\] From this, we see that $B_{n}\not\equiv 0 \; (mod \; 5)$. Indeed, $B_{n}\equiv 0 \;(mod \; 5)$ and the above congruence imply that \[\pm 2 \equiv-{G_{n}}^{2}(mod \; 5).\] However, this is a contradiction. Even Homer Simpson can check that $l^{2}\equiv-1, 0, 1 (mod \; 5)$ holds for all $l \in \mathbf{Z}$.

(Wolstenholme's Theorem) Prove that if \[1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}\] is expressed as a fraction, where $p \ge 5$ is a prime, then $p^{2}$ divides the numerator.

Click for solution We will treat rational numbers, which have their denominator relatively prime to $p$, as residues mod $p$. From the Fermat's Little Theorem: $\frac{1}{i} \equiv i^{p-2} \mod{p}$ So we see that: $\sum_{i=1}^{p-1} \frac{1}{i} \equiv \sum_{i=1}^{p-1} i^{p-2} = \sum_{i=1}^{\frac{p-1}{2}} i^{p-2} + (p-i)^{p-2} \equiv \sum_{i=1}^{\frac{p-1}{2}} p(p-2)i^{p-3} = p(p-2) \sum_{i=1}^{\frac{p-1}{2}} i^{p-3} \mod{p^2}$ The last congruence comes from the fact that the rest term vanishes mod $p^2$. We are left with proving that: $\sum_{i=1}^{\frac{p-1}{2}} i^{p-3} \equiv 0 \mod{p}$ or (one more time from FTL): $\sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i^2} \equiv 0 \mod{p}$ Now if $i, j \leq \frac{p-1}{2}$ and $\frac{1}{i^2} \equiv \frac{1}{j^2} \mod{p}$ then also $(i-j)(i+j) \equiv 0 \mod{p}$ but since $i, j \leq \frac{p-1}{2}$ we must have $i=j$. So the numbers: $\frac{1}{i^2}$ for $i=1,2,...,\frac{p-1}{2}$ are all different quadratic residues (and there are exactly $\frac{p-1}{2}$ quadratic residues), as well as the numbers $i^2$ for $i=1,2,...,\frac{p-1}{2}$ so: $\sum_{i=1}^{\frac{p-1}{2}} \frac{1}{i^2} \equiv \sum_{i=1}^{\frac{p-1}{2}} i^2 = \frac{p(p-1)(p+1)}{24} \equiv 0 \mod{p}$ which ends the proof.

Let $p>3$ is a prime number and $k=\lfloor\frac{2p}{3}\rfloor$. Prove that \[{p \choose 1}+{p \choose 2}+\cdots+{p \choose k}\] is divisible by $p^{2}$.

Show that ${2n \choose n} \; \vert \; \text{lcm}(1,2, \cdots, 2n)$ for all positive integers $n$.

Click for solution Since $ n! = \prod_{p_{i}\text{ prime}}p_{i}^{\sum^{\lfloor\log_{p_{i}}(n)\rfloor}_{k = 1}\left\lfloor\frac {n}{p_{i}^k}\right\rfloor}$ and $ \text{lcm}(1,\ldots,n) = \prod_{p_{i}\text{ prime}}p_{i}^{\lfloor\log_{p_{i}}(n)\rfloor}$, there is to prove that \[ \binom{2n}{n} = \prod_{p_{i}\text{ prime}}p_{i}^{\sum^{\lfloor\log_{p_{i}}(2n)\rfloor}_{k = 1}\left\lfloor\frac {2n}{p_{i}^k}\right\rfloor - 2\left\lfloor\frac {n}{p_{i}^k}\right\rfloor}\left|\prod_{p_{i}\text{ is prime}}p_{i}^{\lfloor\log_{p_{i}}(2n)\rfloor}\right. = \text{lcm}(1,\ldots,2n),\] so it suffices to show that $ \sum^{\lfloor\log_{p_{i}}(2n)\rfloor}_{k = 1}\left\lfloor\frac {2n}{p_{i}^k}\right\rfloor - 2\left\lfloor\frac {n}{p_{i}^k}\right\rfloor\le\lfloor\log_{p_{i}}(2n)\rfloor$, which is obvious since $ \left\lfloor\frac {2n}{p_{i}^k}\right\rfloor - 2\left\lfloor\frac {n}{p_{i}^k}\right\rfloor\in\{0,1\}$. [Moderator edit: fixed some typos. - darij]

Let $m$ and $n$ be arbitrary non-negative integers. Prove that \[\frac{(2m)!(2n)!}{m! n!(m+n)!}\] is an integer.

Click for solution Here is an short proof for the inequalities: $ \lfloor 2x\rfloor + \lfloor 2y\rfloor \geq \lfloor x\rfloor + \lfloor y\rfloor + \lfloor x + y\rfloor ,\forall x,y > 0$ We has : $ \lfloor 2x\rfloor = \lfloor x\rfloor + \lfloor x + \frac {1}{2}\rfloor$ Then the inequalities equivalent: $ \lfloor x + \frac {1}{2}\rfloor + \lfloor y + \frac {1}{2}\rfloor \geq \lfloor x + y\rfloor$ $ \lfloor \{x\} + \frac {1}{2}\rfloor + \lfloor \{y\} + \frac {1}{2}\rfloor \geq \lfloor \{x\} + \{y\}\rfloor$ It is true. In the same method we can prove that exist infinite $ (m,n)\in N$ for $ \frac {(2m)!(2n)!}{m!n!(m + n)!}$ is an even number.

Show that the coefficients of a binomial expansion $(a+b)^n$ where $n$ is a positive integer, are all odd, if and only if $n$ is of the form $2^{k}-1$ for some positive integer $k$.

Click for solution Firstly, suppose $n=2^k-1$. Then $\binom{n}{m}=\frac{(2^k-1)(2^k-2)....(2^k-m)}{1*2*......*m}$. For any $a,b$ with $b<k$, $a \equiv -(2^k-a) \mod{2^b}$, so in particular, if one is zero, the other is zero also. Therefore, comparing factors in the numerator and the denominator, all the powers of two will cancel out exactly, leaving an odd binomial coefficient, completing the sufficiency part of the proof. Now, suppose $n=2^k-l$ with $1<l\leq2^{k-1}$. Consider the binomial coefficient $\binom{2^k-l}{2^{k-1}-1}=\frac{(2^k-l)!}{(2^{k-1}-1)!(2^{k-1}-l+1)!}=\frac{(2^k-l)(2^k-l-1)....2^{k-1}}{(2^{k-1}-l+1)!}$ Factoring out, this becomes $\frac{2^{k-1}}{2^{k-1}-l+1}\binom{2^k-l}{2^{k-1}-l}$, which is clearly even by choice of l.

Prove that the expression \[\frac{\gcd(m, n)}{n}{n \choose m}\] is an integer for all pairs of positive integers $(m, n)$ with $n \ge m \ge 1$.

For which positive integers $k$, is it true that there are infinitely many pairs of positive integers $(m, n)$ such that \[\frac{(m+n-k)!}{m! \; n!}\] is an integer?

Click for solution piever wrote: Let $ n\ge k+1$ and $ m=n!-1$ \[ {\frac{(m+n-k)!}{m!n!}=\frac{(m+n-k)!(m+1)!}{(m+1)!m!n!}=\frac{(m+n-k)!(m+1)}{(m+1)!n!}=\frac{(m+n-k)!}{(m+1)!}\in\mathbb{Z}}\]

Show that if $n \ge 6$ is composite, then $n$ divides $(n-1)!$.

Click for solution Or alternatively, If $n$ is composite, unless it is the square of a prime, there exist naturals $a,b$ such that $n=ab$, where $a,b<n, a\not=b$. But $(n-1)!=(n-1)(n-2)....a.....b...2$ so we are done. If $n=p^2$, $(n-1)!=(p^2-1)...p(p-1)...p(p-2)....p$ and so for p>2 clearly is divisible by $p^2$.

Show that there exist infinitely many positive integers $n$ such that $n^{2}+1$ divides $n!$.

Click for solution Let $ n=4k^{2}+2k+1$ $ n^{2}+1=(4k^{2}+1)^{2}+2(4k^{2}+1)2k+(2k)^{2}+1=2(4k^{2}+1)(2k^{2}+2k+1)$. If we suppose $ 2<2k^{2}+2k+1<4k^{2}+1$, then $ 2(4k^{2}+1)(2k^{2}+2k+1)$ divides $ (4k^{2}+2k+1)!$

Let $ a$ and $ b$ be natural numbers such that \[ \frac{a}{b}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots-\frac{1}{1318}+\frac{1}{1319}. \] Prove that $ a$ is divisible by $ 1979$.

Click for solution 1979 is prime. $ 1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots-\frac{1}{1318}+\frac{1}{1319}\#=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{1318}+\frac{1}{1319}-2(\frac{1}{2}+\frac{1}{4}+\cdots+\frac{1}{1318}) \#=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots+\frac{1}{1318}+\frac{1}{1319}-(1+\frac{1}{2}+\cdots+\frac{1}{659})\#=\frac{1}{660}+\frac{1}{661}+\cdots+\frac{1}{1319}\#=(\frac{1}{660}+\frac{1}{1319})+(\frac{1}{661}+\frac{1}{1318}) \cdots+( \frac{1}{989}+\frac{1}{990}) =1979 \frac{d}{c}$ (where $ c, d$ are relative prime.) Because $ c$ is not multiple of 1979, $ 1979 \mid a$

Let $a,b,x\in \mathbb{N}$ with $b>1$ and such that $b^{n}-1$ divides $a$. Show that in base $b$, the number $a$ has at least $n$ non-zero digits.

Let $p_{1}, p_{2}, \cdots, p_{n}$ be distinct primes greater than $3$. Show that \[2^{p_{1}p_{2}\cdots p_{n}}+1\] has at least $4^{n}$ divisors.

Click for solution Set $m=p_1 p_2 ... p_n$. It's well knwon that $2^{p_i}+1 | 2^m+1$. If $p,q$ are different odd primes, we have that $\gcd(2^p+1,2^q+1) | \gcd(2^{2p}-1,2^{2q}-1) = 2^2-1=3$. For all primes $p,q>3$ we get that $\frac{2^p+1}3, \frac{2^q+1}3$ are coprime (and clearly $>0$). We set $s_i=\frac{2^{p_i}+1}3$. For each $p_i$ we choose a prime $q_i$ with $q_i|s_i$. Then we set $r_i = \frac{s_i}{q_i}$. Now $r_i \neq q_i$ because otherwise $2^{p_i}+1=2q_i^2$, impossible $\mod 4$. Consider the set $S_i := \{1,q_i,r_i,s_i\}$: As we've seen, it really has four different elements, and elements from different sets are coprime. Thus we get a total number of $4^n$ different products $\prod x_i$ with $x_i \in S_i$. And every such product divides $2^m+1$.

Let $p \ge 5$ be a prime number. Prove that there exists an integer $a$ with $1 \le a \le p-2$ such that neither $a^{p-1} -1$ nor $(a+1)^{p-1} -1$ is divisible by $p^2$.

Let $n$ and $q$ be integers with $n \ge 5$, $2 \le q \le n$. Prove that $q-1$ divides $\left\lfloor \frac{(n-1)!}{q}\right\rfloor $.

If $n$ is a natural number, prove that the number $(n+1)(n+2)\cdots(n+10)$ is not a perfect square.

Let $p$ be a prime with $p>5$, and let $S=\{p-n^2 \vert n \in \mathbb{N}, {n}^{2}<p \}$. Prove that $S$ contains two elements $a$ and $b$ such that $a \vert b$ and $1<a<b$.

Click for solution We show that the smallest possible $a$ works. Let $n= \lfloor \sqrt p \rfloor$. If $n^2+1=p$, then we set $a=p-(n-1)^2=n^2+1-n^2+2n-1=2n$ and $b=p-1^2=n^2$. This works, because surely $p$ is odd, so $2|n$ giving $a=2n|n^2=b$. In all other cases we can set $a=p-n^2>1$. There are three cases: a) $n^2+n > p$: Then we set $c=n^2+n-p>0$. Additionally $n^2 < p$ gives $c=n^2-p+n<n$. b) $n^2+n=p$: this implies $n|p$, impossible. c) $n^2+n < p$: Then we set $c=p-n^2-n>0$. Additionally $p < (n+1)^2$ gives $c=p-n^2-n=p-(n+1)^2+n+1<n+1$. If $c=n$, then we would have $n=p-n^2-n$ giving $n|p$, impossible. So again $c<n$. In all possible cases, we now set $b=p-c^2$ and get $b=p-c^2 \equiv p- (\pm n)^2 \equiv p-n^2 \equiv 0 \mod (p-n^2)$, being the result.

Let $n$ be a positive integer. Prove that the following two statements are equivalent. $n$ is not divisible by $4$ There exist $a, b \in \mathbb{Z}$ such that $a^{2}+b^{2}+1$ is divisible by $n$.

Determine the greatest common divisor of the elements of the set \[\{n^{13}-n \; \vert \; n \in \mathbb{Z}\}.\]

Show that there are infinitely many composite numbers $n$ such that $3^{n-1}-2^{n-1}$ is divisible by $n$.

Click for solution Peter wrote: Show that there are infinitely many composite numbers $n$ such that $3^{n-1}-2^{n-1}$ is divisible by $n$. We prove that for any positive integer $m$ the number $n=3^{2^{m}}-2^{2^{m}}$ satisfies the problems condition. Indeed, we have that if $a|b$ then $3^{a}-2^{a}|3^{b}-2^{b}$ so to prove that $n|3^{n-1}-2^{n-1}$ it is sufficent to prove that $2^{m}|n-1$,that is $2^{m}|(3^{2^{m}}-1)-2^{2^{m}}$. Since $2^{m}\geq m$, then $2^{m}|2^{2^{m}}$ and we only need to verify that $2^{m}|3^{2^{m}}-1$. It is easy to see that \[3^{2^{m}}-1=(3-1)(3+1)(3^{2}+1)...(3^{2^{m-1}}+1)\] which shows that $3^{2^{m}}-1$ is a product of $8=(3-1)(3+1)$ and $m-1$ even numbers and thus is divisible by $2^{m}$(actually we have proved that it is divisible by $2^{m+2}$).

Suppose that $2^n +1$ is an odd prime for some positive integer $n$. Show that $n$ must be a power of $2$.

Click for solution When $n$ is odd, the relation $x^{n}+1 = (1+x)(1-x+x^{2}-\ldots+x^{n-1})$ yields \[\forall x \in \mathbb{N}, \forall n \in \mathbb{N}, n \text{ odd}, \ \ (x+1)|(x^{n}+1). \ \ \ (*)\] If $n$ is not a power of $2, n$ has at least one odd factor $p > 1.$ Let us write $n=pq$ with $q \in \mathbb{N}.$ The integer $2^{n}+1 = (2^{q})^{p}+1$ is divisible by $(2^{q}+1)$ thanks to $(*),$ hence composite. Therefore, $n$ has to be a power of $2.$

Suppose that $p$ is a prime number and is greater than $3$. Prove that $7^{p}-6^{p}-1$ is divisible by $43$.

Click for solution By the well-known fact that $ x^2 + x + 1|x^{2k} + x^k + 1$ for every $ k\equiv 1,2 \pmod{3}$ we have that $ 6^2 + 6 + 1|6^{2p} + 6^p + 1$ because 3 does not divide p. So $ 6^{2p} + 6^p + 1\equiv 0 \pmod{43}$. Also we have that $ 6\cdot 7\equiv - 1\pmod{43}$ so $ (6\cdot 7)^p\equiv - 1\pmod{43}$ because p is odd. $ 6^{2p} + 6^p + 1\equiv6^{2p} + 6^p - (6*7)^p\equiv6^p*(6^p + 1 - 7^p)\equiv0\pmod{43}$ Because $ \gcd(6,43) = 1$ we have that $ 43|7^p - 6^p - 1$

Suppose that $4^{n}+2^{n}+1$ is prime for some positive integer $n$. Show that $n$ must be a power of $3$.

Let $b,m,n\in\mathbb{N}$ with $b>1$ and $m\not=n$. Suppose that $b^{m}-1$ and $b^{n}-1$ have the same set of prime divisors. Show that $b+1$ must be a power of $2$.

Let $a$ and $b$ be integers. Show that $a$ and $b$ have the same parity if and only if there exist integers $c$ and $d$ such that $a^2 +b^2 +c^2 +1 = d^2$.

Click for solution zakor wrote: Let $ a$ and $ b$ such that there exist $ c,d$ with $ a^{2}+b^{2}+c^{2}+1=d^{2}$. Assume that $ a$ and $ b$ have different parity. Then $ d^{2}-c^{2}$ is 2 mod 4, impossible. Now, for the converse, observe that $ a^{2}+b^{2}+1$ is either $ 4k+1$ or $ 4k+3$. Therefore we may take $ (c,d)=(2k, 2k+1)$ or $ (c,d)=(2k+1, 2k+2)$. Hope I'm right because this is my first post

Let $n$ be a positive integer with $n>1$. Prove that \[\frac{1}{2}+\cdots+\frac{1}{n}\] is not an integer.

Let $n$ be a positive integer. Prove that \[\frac{1}{3}+\cdots+\frac{1}{2n+1}\] is not an integer.

Prove that there is no positive integer $n$ such that, for $k=1, 2, \cdots, 9,$ the leftmost digit of $(n+k)!$ equals $k$.

Click for solution For $ m\in\mathbb{N}$, be $ f(m)=m\cdot 10^{r}$ with $ r$ the unique integer for which $ 1\le f(m)<10$ (i.e. the first digit of $ m$). Then for $ 2\le i\le9$ we have $ i<f((N+i)!)<i+1$, such that \[ 1 < f(N+i) = f\left(\frac{(N+i)!}{(N+i-1)!}\right) <\frac{i+1}{i-1}\le 3.\] So $ f(N+i)<f(N+i-1)$ and thus $ 1 < f(N+2) < f(N+3) < ... < f(N+9) <\frac{5}4$. Since obviously $ f(ab)\le f(a)f(b)$, is \[ f((N+4)!)\le f((N+1)!)f(N+2)f(N+3)f(N+4)< 2\left(\frac{5}4\right)^{3}< 4,\] contradiction.

Show that every integer $k>1$ has a multiple less than $k^4$ whose decimal expansion has at most four distinct digits.

Click for solution For $ k\le10000$ the problem is trivial, since $ k$ itself does the job. For $ k > 10000$, we have an $ n < k$ such that $ 10^{n}< k^{4}< 16^{n}$ (and thus $ 2^{n}> k$). For this $ n$, consider \[ S=\{k\in\mathbb{N}|10^{n}\le k<10^{n+1}\text{ and }k\text{ only consists of digits }0\text{ and }1\text{.}\},\] then $ |S| = 2^{n}> k$ and therefor contains two elements $ s_{1}> s_{2}$ with same remainder modulo $ k$. So, $ k|s_{1}-s_{2}$, and $ s_{1}-s_{2}< 10^{n}< k^{4}$. On the other hand, differences of two numbers in $ S$ have only digits $ 0,1,8,9$, so we're done.

Let $a,b,c$ and $d$ be odd integers such that $0<a<b<c<d$ and $ad=bc$. Prove that if $a+d=2^{k}$ and $b+c=2^{m}$ for some integers $k$ and $m$, then $a=1$.

Click for solution nicetry007 wrote: We can write $ d = 2^{k} - a$ and $ c = 2^{m} - b$. $ ad = bc \Rightarrow a(2^{k} - a) = b(2^{m} - b) \Rightarrow b^{2} - a^{2} = 2^{m}b - 2^{k}a \Rightarrow (b + a)\;(b - a) = 2^{m}b - 2^{k}a$ (*) Claim: $ m \leq k$. $ b\; < \; d,\; c\; < \; d\; \Rightarrow\; 2^{m}\; = \; b + c\; < \; 2d\; < \;2^{k + 1}\; \Rightarrow\; m\; < \; k + 1$. Using $ m \leq k$ in (*), we get $ (b + a)\;(b - a) = 2^{m}\;(b - 2^{k - m}a) \;\Rightarrow\; 2^{m}| (b + a)\;(b - a)$ Both $ b + a$ and $ b - a$ are even. $ gcd(b + a,\;b - a) = gcd(b + a - (b - a),b - a) = gcd(2a, b - a) = 2\cdot gcd(a, (b - a)/2)$. The highest power of $ 2$ that divides both $ b + a$ and $ b - a$ is $ 2$ as $ a$ is an odd integer. In other words, one of $ \{b + a, \;b - a\}$ is divisible by $ 2$ and the other is divisible by $ 2^{m - 1}$. Claim: $ b < 2^{m - 1}$ $ 2b < b + c = 2^{m}\Rightarrow b \; < \; 2^{m - 1}$. Hence, $ b - a \; < \;2^{m - 1}$ and $ 2^{m - 1}\;|\;(b + a)$. But $ b + a \; < \; b + c = 2^{m}\Rightarrow b + a = 2^{m - 1}\Rightarrow b + c + a = 2^{m - 1} + c \Rightarrow 2^{m} + a = 2^{m - 1} + c \Rightarrow c - a = 2^{m - 1}$ $ ad = bc \Rightarrow ad = (2^{m - 1} - a)c \Rightarrow a(d + c) = 2^{m - 1}c$. Suppose $ a > 1$. Since $ a$ is an odd integer $ a | c$. Let $ c = pa$. Now $ c - a = 2^{m - 1}\Rightarrow a(p - 1) = 2^{m - 1}\Rightarrow a | 2^{m - 1}$. But $ a$ is an odd integer greater than $ 1$. Hence, our assumption that $ a \; > \;1$ is wrong. $ a = 1, \;b = 2^{m - 1} - 1,\; c = 2^{m - 1} + 1$ and $ d = 2^{2(m - 1)} - 1$. mod: checked and found correct 20071102,0:51:04

Let $d$ be any positive integer not equal to 2, 5, or 13. Show that one can find distinct $a$ and $b$ in the set $\{2,5,13,d\}$ such that $ab - 1$ is not a perfect square.

Click for solution nicetry007 wrote: Let $ 2d-1 = x^{2}$, $ 5d-1 = y^{2}$ and $ 13d-1 = z^{2}$. Suppose $ d$ is even. This would imply $ 2d-1 = 3 ( mod \; 4)$. But a perfect square is either $ 0$ or $ 1 (mod \; 4)$. Hence, $ d$ is odd. This implies that $ x$ is odd and $ y$ and $ z$ are even. $ y^{2}-z^{2}= 8d \Rightarrow y^{2}= z^{2}(mod \;8)$. Since the perfect square of an even number is either $ 0$ or $ 4 (mod \; 8)$, $ y^{2}$ and $ z^{2}$ are either both $ 0(mod\; 8)$ or $ 4 (mod \; 8)$. Suppose $ y^{2}= 0 (mod \; 8)$ and $ z^{2}= 0 (mod \; 8)$. If the square of an integer is divisible by $ 8$, then it is also divisible by $ 16$. Hence, it follows that $ y^{2}= 0 (mod \; 16)$ and $ z^{2}= 0 (mod \; 16)$. This, in turn, implies that $ y^{2}-z^{2}= 0 (mod \;16)$. But $ y^{2}-z^{2}= 8d$ and $ d$ is odd. Hence, we arrive at a contradiction. Suppose $ y^{2}= 4 (mod \; 8)$ and $ z^{2}= 4 (mod \; 8)$. Let $ y^{2}= 4p^{2}$ and $ z^{2}= 4q^{2}$ where $ p,q$ are odd. $ y^{2}-z^{2}= 4(p^{2}-q^{2}) = 4(p-q)\;(p+q)$. Since $ (p-q)$ and $ (p+q)$ are both even, $ y^{2}-z^{2}$ is divisible by $ 16$. But $ y^{2}-z^{2}= 8d$ and $ d$ is odd. We observe that in both cases we arrive at a contradiction. Hence, the result follows.

Suppose that $x, y,$ and $z$ are positive integers with $xy=z^2 +1$. Prove that there exist integers $a, b, c,$ and $d$ such that $x=a^2 +b^2$, $y=c^2 +d^2$, and $z=ac+bd$.

A natural number $n$ is said to have the property $P$, if whenever $n$ divides $a^{n}-1$ for some integer $a$, $n^2$ also necessarily divides $a^{n}-1$. Show that every prime number $n$ has the property $P$. Show that there are infinitely many composite numbers $n$ that possess the property $P$.

Click for solution Peter wrote: A natural number $n$ is said to have the property $P$, if whenever $n$ divides $a^{n}-1$ for some integer $a$, $n^{2}$ also necessarily divides $a^{n}-1$. Show that every prime number $n$ has the property $P$. Show that there are infinitely many composite numbers $n$ that possess the property $P$. (a) We have that $n=p$ is a prime number. From Fermat's theorem $p|a^{p-1}-1$ and $p|a^{p}-1$, then $p|a^{\gcd(p;p-1)}-1$ so $p|a-1$. We got that $a=pk+1$ for some $k$ then \[a^{n}-1=(pk+1)^{n}-1 \equiv C_{n}^{p-1}(pk)=p^{2}k\equiv 0(mod p^{2})\] (b) Let us prove that the number $n=pq$ possess the property $P$, for every different primes $p$ and $q$. Indeed, we have that if $pq|a^{pq}-1$ then $p|(a^{q})^{p}-1$ thus from (a) follows that $p^{2}|a^{pq}-1$ and similarly we can prove that $q^{2}|a^{pq}-1$. Therefore ,whenever $pq|a^{pq}-1$ then $(pq)^{2}|a^{pq}-1$.

Show that for every natural number $n$ the product \[\left( 4-\frac{2}{1}\right) \left( 4-\frac{2}{2}\right) \left( 4-\frac{2}{3}\right) \cdots \left( 4-\frac{2}{n}\right)\] is an integer.

Click for solution Peter wrote: Show that for every natural number $ n$ the product \[ \left( 4 - \frac {2}{1}\right) \left( 4 - \frac {2}{2}\right) \left( 4 - \frac {2}{3}\right) \cdots \left( 4 - \frac {2}{n}\right) \] is an integer. We have that \[ \prod_{i = 1}^{n}{(4 - \frac {2}{i})} = \frac {\prod_{i = 1}^{n}{2(2i - 1)}}{n!} = \frac {2^{n}(2n - 1)!!}{n!} = \frac {(2n)!}{n!n!} = C_{2n}^{n} \] Where $ C_{2n}^{n}$ is a binomial coefficient and, as we know, it is a positive integer.

Let $a, b$, and $c$ be integers such that $a+b+c$ divides $a^2 +b^2 +c^2$. Prove that there are infinitely many positive integers $n$ such that $a+b+c$ divides $a^n +b^n +c^n$.

Click for solution nicetry007 wrote: We will show that $ a+b+c$ divides $ a^{2^{k}}+\; b^{2^{k}}+\; c^{2^{k}}$ for $ k \in \{0\;,\; 1\;,\; 2\; \cdots \;\}$. It is given in the problem that the result holds for $ k \;= \;0$ and $ k \;= \;1$. We will extend it to every positive integer by induction on $ k$. Suppose $ a+b+c$ divides $ a^{2^{n-1}}+\; b^{2^{n-1}}+\; c^{2^{n-1}}$ and $ a^{2^{n}}+\;b^{2^{n}}+\;c^{2^{n}}$. We then have $ a+b+c \; |\;\left(a^{2^{n-1}}+\; b^{2^{n-1}}+\; c^{2^{n-1}}\right)^{2}-\left(a^{2^{n}}+\;b^{2^{n}}+\;c^{2^{n}}\right)\; = \; 2\left(a^{2^{n-1}}b^{2^{n-1}}+b^{2^{n-1}}c^{2^{n-1}}+c^{2^{n-1}}a^{2^{n-1}}\right)$. $ 2\;\left(a^{2^{n-1}}b^{2^{n-1}}+b^{2^{n-1}}c^{2^{n-1}}+c^{2^{n-1}}a^{2^{n-1}}\right)^{2}$ $ = 2\;\left(a^{2^{n}}b^{2^{n}}+\; b^{2^{n}}c^{2^{n}}+\; c^{2^{n}}a^{2^{n}}+\;2\;\left(a^{2^{n-1}}b^{2^{n}}c^{2^{n-1}}+\;a^{2^{n-1}}b^{2^{n-1}}c^{2^{n}}+\; a^{2^{n}}b^{2^{n-1}}c^{2^{n-1}}\;\right)\; \right)$ $ = 2\;\left(a^{2^{n}}b^{2^{n}}+\; b^{2^{n}}c^{2^{n}}+\; c^{2^{n}}a^{2^{n}}+\;2\;a^{2^{n-1}}b^{2^{n-1}}c^{2^{n-1}}\;\left(a^{2^{n-1}}+\;b^{2^{n-1}}+\; c^{2^{n-1}}\;\right)\; \right)$ Since $ a+b+c \; |\;2\left(a^{2^{n-1}}b^{2^{n-1}}+b^{2^{n-1}}c^{2^{n-1}}+c^{2^{n-1}}a^{2^{n-1}}\right)\;$, we have $ a+b+c \; |\;2\left(a^{2^{n-1}}b^{2^{n-1}}+b^{2^{n-1}}c^{2^{n-1}}+c^{2^{n-1}}a^{2^{n-1}}\right)^{2}$ $ \Rightarrow a+b+c \; |\;2\;\left(a^{2^{n}}b^{2^{n}}+\; b^{2^{n}}c^{2^{n}}+\; c^{2^{n}}a^{2^{n}}+\;2\;a^{2^{n-1}}b^{2^{n-1}}c^{2^{n-1}}\;\left(a^{2^{n-1}}+\;b^{2^{n-1}}+\; c^{2^{n-1}}\;\right)\; \right)$ $ \Rightarrow a+b+c \; |\;2\;\left(a^{2^{n}}b^{2^{n}}+\; b^{2^{n}}c^{2^{n}}+\; c^{2^{n}}a^{2^{n}}\; \right)\;$ (as $ a+b+c \;|\; a^{2^{n-1}}+\; b^{2^{n-1}}+\; c^{2^{n-1}}$ ) $ \Rightarrow a+b+c \; |\;\left(a^{2^{n}}+\; b^{2^{n}}+\; c^{2^{n}}\right)^{2}-2\;\left(a^{2^{n}}b^{2^{n}}+\; b^{2^{n}}c^{2^{n}}+\; c^{2^{n}}a^{2^{n}}\; \right)\;$ ( as $ a+b+c \;|\; a^{2^{n}}+\; b^{2^{n}}+\; c^{2^{n}}$ ) (i.e.) $ a+b+c \; |\;a^{2^{n+1}}+\; b^{2^{n+1}}+\; c^{2^{n+1}}$. Hence, $ a+b+c \; |\;a^{2^{k}}+\; b^{2^{k}}+\; c^{2^{k}}$ for all $ k \in \{0\;,\; 1\;,\; 2\; \cdots \;\}$.

Prove that for every $n \in \mathbb{N}$ the following proposition holds: $7|3^n +n^3$ if and only if $7|3^{n} n^3 +1$.

Click for solution Suppose $ 7\; |\; 3^{n}+n^{3}$. This implies $ 7$ does not divide $ n$. This, in turn, implies that $ n^{6}= 1 (mod \; 7)$. $ 7\; |\; 3^{n}+n^{3}\;\Rightarrow \;7\; |\; n^{3}(3^{n}+n^{3}) \;\Rightarrow \;7\; |\; n^{3}3^{n}+n^{6}\;\Rightarrow\; 7\; |\; n^{3}3^{n}+1+n^{6}-1\; \Rightarrow \;7\; |\; n^{3}3^{n}+1$ (since $ 7\;|\; n^{6}-1$). Suppose $ 7\; |\; n^{3}3^{n}+1$. This implies $ 7$ does not divide $ n$ which, in turn, implies that $ n^{6}= 1 (mod \; 7)$. $ 7\; |\; n^{3}3^{n}+1 \;\Rightarrow \;7\; |\; n^{3}(n^{3}3^{n}+1) \;\Rightarrow \;7\; |\; n^{6}3^{n}+n^{3}\;\Rightarrow\; 7\; |\; (n^{6}-1)3^{n}+3^{n}+n^{3}\; \Rightarrow \;7\; |\; 3^{n}+n^{3}$ (since $ 7\;|\; n^{6}-1$). Hence, $ 7\; |\; 3^{n}+n^{3}$ if and only if $ 7\; |\; n^{3}3^{n}+1$.

Let $k\ge 14$ be an integer, and let $p_k$ be the largest prime number which is strictly less than $k$. You may assume that $p_k\ge \tfrac{3k}{4}$. Let $n$ be a composite integer. Prove that if $n=2p_k$, then $n$ does not divide $(n-k)!$, if $n>2p_k$, then $n$ divides $(n-k)!$.

Suppose that $n$ has (at least) two essentially distinct representations as a sum of two squares. Specifically, let $n=s^{2}+t^{2}=u^{2}+v^{2}$, where $s \ge t \ge 0$, $u \ge v \ge 0$, and $s>u$. Show that $\gcd(su-tv, n)$ is a proper divisor of $n$.

Click for solution nicetry007 wrote: Let $ n = s^{2}+t^{2}= u^{2}+v^{2}$. Since $ s \;>\; u$ and $ v\;\geq \; 0$, we have $ v \;>\; 0$, which , in turn, implies that $ u \;>\; 0$ as $ u\;\geq \;v\;$. $ n^{2}\;=\; (s^{2}+t^{2})\; ( u^{2}+v^{2}) \;=\; (su-tv)^{2}\;+\;(sv+tu)^{2}\; = \; (su+tv)^{2}\;+\;(sv-tu)^{2}$ $ \Rightarrow \; |su-tv| \leq n\;,\; |su+tv| \leq n$ (i) $ s^{2}u^{2}\;-\; t^{2}v^{2}\;= \;s^{2}u^{2}\;+\; t^{2}u^{2}\;-\; t^{2}u^{2}\;-\; t^{2}v^{2}\; =\; (s^{2}\;+\; t^{2})\;u^{2}\;-\; (u^{2}\;+\;v^{2})\;t^{2}\;= \;nu^{2}\;-\; nt^{2}\; =\; 0 (mod \; n)$ $ \Rightarrow n \;|\; (su \;+\; tv)(su\;-\; tv)$ (ii) If we strengthen (i) by showing that $ 1 \;\leq \; |su-tv| \;< \;n$ and $ 1 \;\leq \; |su+tv| \;< \;n$, then it follows that $ n$ cannot divide $ |su-tv|$ or $ |su+tv|$. This along with (ii) would imply that $ 1 \;< \;gcd(su-tv \;, \;n)\;<\; n$. In other words, $ gcd(su-tv \;, \;n)$ is a proper divisor of $ n$. Case(a) Suppose $ su \;-\; tv \;=\; 0$. Since $ s \;\geq \; t\; \geq \;0$ and $ u \;\geq \; v\;>\;0$, we have $ su \; \geq \; tv\;\geq \;0 \;\Rightarrow \; su \;-\; tv\; \geq \; 0$. But $ su \;-\; tv = 0$. Hence, we have $ s\; =\; t$ and $ u\; = \; v \;\Rightarrow \; n\; = \;2s^{2}\; =\; 2u^{2}\; \Rightarrow \;s\; = \;u\;$, which is a contradiction. Case(b) Suppose $ su \;+\; tv \;=\; 0$. Since $ s\; \geq \; t\; \geq \;0$ and $ s \;>\; u\; \geq \;v\;> \;0\;$, we have $ su \;+\; tv \;>\; 0$, which contradicts $ su \;+\; tv \;=\; 0$. Case(c) Suppose $ |\;su \;-\; tv \;|\;=\; n$. This implies $ sv+tu \;= \;0$. Since $ s \;\geq \; t\; \geq \;0$ and $ s \;>\;u \;\geq \; v\;> \;0$, we have $ sv+tu \;> \;0$ which contradicts $ sv+tu \;= \;0$. Case(d) Suppose $ |\;su \;+\; tv \;|\;=\; n$. This implies $ sv-tu \;= \;0$. Since $ s \;>\; u\; >\;0$ and $ v \;>\;0$, it follows that $ t \;>\; v\; >\;0 \;\Rightarrow \; s^{2}+t^{2}\;> \; u^{2}+v^{2}$, which contradicts $ s^{2}+t^{2}\;= \; u^{2}+v^{2}$. Hence, we have $ 1 \;\leq \; |su-tv| \;< \;n$ and $ 1 \;\leq \; |su+tv| \;< \;n$. Therefore, it follows that the $ gcd(su-tv \;, \;n)$ is a proper divisor of $ n$.

Prove that there exist an infinite number of ordered pairs $(a,b)$ of integers such that for every positive integer $t$, the number $at+b$ is a triangular number if and only if $t$ is a triangular number.

Click for solution Peter wrote: Prove that there exist an infinite number of ordered pairs $ (a,b)$ of integers such that for every positive integer $ t$, the number $ at+b$ is a triangular number if and only if $ t$ is a triangular number. Let $ \mathcal{T}$ be the set of triangular numbers: \[ \mathcal{T}=\left\{\frac{n(n+1)}{2}\;\vert\; n\in\mathbb{N}_{\geq 0}\right\}.\] We prove the following proposition. Suppose that $ d$ is an odd integer (so that $ d^{2}\equiv 1\; (mod\; 8)$). Let $ t$ be a positive integer. Then, $ t\in\mathcal{T}$ if and only if $ d^{2}t+\frac{d^{2}-1}{8}\in\mathcal{T}$. {Proof} $ (\Rightarrow)$ Assume that $ t\in\mathcal{T}$ so that $ t =\frac{\alpha(\alpha+1)}{2}$ for some $ \alpha\in\mathbb{N}_{\geq 0}$. Set $ l =\frac{d (2\alpha+1)-1}{2}$. Since $ d$ is odd, we see that $ l\in\mathbb{N}_{\geq 0}$. One may easily check that \[ d^{2}t+\frac{d^{2}-1}{8}=d^{2}\frac{\alpha(\alpha+1)}{2}+\frac{d^{2}-1}{8}=\frac{l(l+1)}{2}\in\mathcal{T}.\] $ (\Leftarrow)$ Assume that $ d^{2}t+\frac{d^{2}-1}{8}\in\mathcal{T}$ so that \[ d^{2}t+\frac{d^{2}-1}{8}=\frac{l(l+1)}{2}\] for some $ l\in\mathbb{N}_{\geq 0}$. It follows that \[ (8t+1) d^{2}=(2l+1)^{2}\] so that $ 8t+1$ is a square of an odd integer $ 2\alpha+1$, where $ \alpha\in\mathbb{N}_{\geq 0}$. Therefore, $ t =\frac{\alpha(\alpha+1)}{2}\in\mathcal{T}$.

For any positive integer $n>1$, let $p(n)$ be the greatest prime divisor of $n$. Prove that there are infinitely many positive integers $n$ with \[p(n)<p(n+1)<p(n+2).\]

Let $p(n)$ be the greatest odd divisor of $n$. Prove that \[\frac{1}{2^{n}}\sum_{k=1}^{2^{n}}\frac{p(k)}{k}> \frac{2}{3}.\]

Click for solution nicetry007 wrote: In the set $ \{1, 2, \cdots, 2^{n}\}$, the number of positive integers that are divisible by $ 2^{k}$, $ 1 \leq k \leq n-1$ is $ 2^{n-k}$. Of these $ 2^{n-k}$, exactly half of them have $ 2^{k}$ as the higest power of $ 2$ dividing them. For these numbers, the ratio $ \frac{p(m)}{m}= \frac{1}{2^{k}}$. The contribution of these numbers towards the sum is $ \;\frac{1}{2}2^{n-k}\frac{1}{2^{k}}= \frac{1}{2^{2k-n+1}}$. The contribution from odd numbers is $ 1\cdot 2^{n-1}$. Finally, the contribution from $ 2^{n}$ is $ \frac{1}{2^{n}}$. Taking the sum of all the contributions, we get $ \frac{1}{2^{n}}\sum_{k=1}^{2^{n}}\frac{p(k)}{k}\; =\; \frac{1}{2^{n}}\left(2^{n-1}\;+\;\frac{1}{2^{n}}\;+\;\sum_{k = 1}^{n-1}\frac{1}{2^{2k-n+1}}\right)$ $ =\; \frac{1}{2^{n}}\left(\;\frac{1}{2^{n}}\;+\;\sum_{k = 0}^{n-1}\frac{1}{2^{2k-n+1}}\right)\; =\; \frac{1}{2^{n}}\left(\frac{1}{2^{n}}\;+\; 2^{n-1}\sum_{k = 0}^{n-1}\frac{1}{2^{2k}}\right)\;=\; \frac{1}{2^{n}}\left(\frac{1}{2^{n}}\;+\; 2^{n-1}\left(\frac{1\;-\; \frac{1}{2^{2n}}}{1 \;-\; \frac{1}{2^{2}}}\right)\right)\;= \;\frac{1}{2^{n}}\left(\frac{1}{2^{n}}\;+\; 2^{n+1}\left(\frac{1\;-\; \frac{1}{2^{2n}}}{3}\right)\right)$ $ = \;\frac{2}{3}\;+\;\frac{1}{2^{n}}\left(\frac{1}{2^{n}}\;-\; \frac{2}{3}\left(\frac{1}{2^{n}}\right)\right) \;=\; \frac{2}{3}\;+\; \;\frac{1}{4^{n}}\left(1\;-\; \frac{2}{3}\right)\; =\; \frac{2}{3}\;+\; \;\frac{1}{3 \cdot 4^{n}}\; > \; \frac{2}{3}$

There is a large pile of cards. On each card one of the numbers $1$, $2$, $\cdots$, $n$ is written. It is known that the sum of all numbers of all the cards is equal to $k \cdot n!$ for some integer $k$. Prove that it is possible to arrange cards into $k$ stacks so that the sum of numbers written on the cards in each stack is equal to $n!$.

Click for solution For $ n = 1$ this is obvious, so assume by induction it is true for $ n-1$. We make piles of sum $ mn$, $ m < n$. As long as there are at least $ n$ cards $ a_{1},...,a_{n}$, either the set $ \{a_{1},a_{1}+a_{2},a_{1}+a_{2}+a_{3},...\}$ contains a multiple of $ n$, or - by pigeonhole - two have the same remainder $ \mod n$, so their differences form a subset with sum divisible by $ n$. So we have such a set When there are less than $ n$ left, the remaining cards form such a set Applying the induction hypothesis with the values for $ m$ as card numbers we have $ k$ piles of $ n(n-1)! = n!$ as desired.

The last digit of the number $x^2 +xy+y^2$ is zero (where $x$ and $y$ are positive integers). Prove that two last digits of this numbers are zeros.

Click for solution Peter wrote: The last digit of the number $ x^{2}+xy+y^{2}$ is zero (where $ x$ and $ y$ are positive integers). Prove that two last digits of this numbers are zeros. The above proof has a straighfoward generalization. Let $ \left(\frac{a}{p}\right)$ denote the Legendre symbol. We first prove two facts. Lemma. Let $ p$ be an odd prime with $ p>3$. Then, we obtain \[ \left(\frac{-3}{p}\right) =\begin{cases}1, & p\equiv 1\; (mod\; 3) ,\\ -1, & p\equiv-1\; (mod\; 3).\\ \end{cases}\] Proof Using well-known properties of Legendre symbol, we compute \[ \left(\frac{-3}{p}\right) =\left(-1\right)^{\frac{p-1}{2}}\left(\frac{3}{p}\right) =\left(-1\right)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)\left(-1\right)^{\left(\frac{3-1}{2}\right)\left(\frac{p-1}{2}\right)}=\left(\frac{p}{3}\right).\] Proposition Let $ p$ be a prime with $ p\equiv-1\; (mod\; 3)$ and let $ f(x,y)=x^{2}+xy+y^{2}$. Whenever $ f(x,y)$ is divisible by $ p$ for some pairs $ (x,y)$ of integers, both $ x$ and $ y$ are divisible by $ p$. Hence, $ f(x,y)$ is divisible by $ p^{2}$. Proof Simple parity arguments kill the case $ p=2$. Now assume that $ p\equiv-1\; (mod\; 3)$. Suppose that $ p\;\vert\; f(x,y)$ for some integers $ x$ and $ y$. In the view of the identity \[ f(x,y)=\left( x+\frac{y}{2}\right)+\frac{3}{4}y^{2}=\frac{1}{4}\left( (2x+y)^{2}+3y^{2}\right) ,\] we have \[ (2x+y)^{2}\equiv-3y^{2}\; (mod\; p).\] We first show that $ y$ is divisibly by $ p$. Assume to the contrary that $ y\not\equiv 0\; (mod\; p)$. Multiplying the inverse of $ y$ modulo $ p$, we obtain \[ (2xy^{-1}+1)^{2}\equiv-3\; (mod\; p).\] Since $ p\equiv-1\; (mod\; 3)$, we find that $ p\neq 3$ so that $ 2xy^{-1}+1\not\equiv 0\; (mod\; p)$. Hence, it says that $ -3$ is a quadratic residue modulo $ p$. Since $ p\equiv-1\; (mod\; 3)$, we apply Lemma 1.1 to obtain \[ \left(\frac{-3}{p}\right)=-1.\] This means that $ -3$ is a quadratic nonresidue modulo $ p$. This is a contradiction. We therefore conclude that $ y\equiv 0\; (mod\; p)$. It follows that $ 0\equiv f(x,y)\equiv x^{2}+xy+y^{2}\equiv x^{2}\; (mod\; p)$ so that $ x\equiv 0\; (mod\; p)$. Now, here goes the solution. Since the last digit of $ x^{2}+xy+y^{2}$ is zero, we find that $ x^{2}+xy+y^{2}$ is divisibly by $ 2\cdot 5$. Applying Proposition, we conclude that $ x^{2}+xy+y^{2}$ is divisibly by $ 2^{2}\cdot 5^{2}$ so that two lastdigits of $ x^{2}+xy+y^{2}$ are zeros.

Clara computed the product of the first $n$ positive integers and Valerid computed the product of the first $m$ even positive integers, where $m \ge 2$. They got the same answer. Prove that one of them had made a mistake.

Click for solution This is a complicated way of asking to solve $ n!=2^{m}m!$ for $ m\ge2$. Looking at the power of $ 3$ in both sides, we see that $ n<m+3$ (otherwise $ m!$ has a factor 3 more than the $ n!$), so either $ n=m+1$ (then $ m+1=2^{m}$ implies $ m=1$) or $ n=m+2$ (then $ (m+1)(m+2)=2^{m}$ implies $ m=0$). So no solutions.

(Four Number Theorem) Let $a, b, c,$ and $d$ be positive integers such that $ab=cd$. Show that there exists positive integers $p, q, r,s$ such that \[a=pq, \;\; b=rs, \;\; c=ps, \;\; d=qr.\]

Click for solution Peter wrote: (Four Number Theorem) Let $ a, b, c,$ and $ d$ be positive integers such that $ ab = cd$. Show that there exists positive integers $ p, q, r,s$ such that \[ a=pq,\;\; b=rs,\;\; c=ps,\;\; d=qr.\] We use the following observation. Fact. If $ q$ is a positive rational number, then we can write $ q=\frac{m}{n}$ for some positive integers with $ \gcd(m,n)=1$. Since $ \frac{a}{c}=\frac{d}{b}$, one can find $ q, s\in\mathbb{N}$ such that $ \gcd(q,s)=1$ and \[ \frac{a}{c}=\frac{d}{b}=\frac{q}{s}.\] Since $ \frac{a}{c}=\frac{q}{s}$ and since $ \gcd(q,s)=1$, we can write \[ a=qp,\; c=sp\] for some positive integer $ p$. Also, since $ \frac{d}{b}=\frac{q}{s}$ and since $ \gcd(q,s)=1$, we can write \[ d=qr,\; b=sr\] for some positive integer $ r$.

Prove that $2n \choose n$ is divisible by $n+1$.

Click for solution Peter wrote: Prove that $ 2n\choose n$ is divisible by $ n+1$. One may slightly generize the argument of mathmanman. Proposition. Let $ N$ and $ k$ are positive integers with $ N\geq k$ and $ \gcd(N+1, k+1)=1$. Then, $ N\choose k$ is divisible by $ k+1$. Proof. It is well-known that \[ (N+1){N\choose k}= (k+1){{N+1}\choose{k+1}}.\] Hence, $ (N+1){N\choose k}$ is divisible by $ k+1$. Since $ \gcd(N+1, k+1)=1$, this implies that $ N\choose k$ is divisible by $ k+1$.

Suppose that $S=\{a_{1}, \cdots, a_{r}\}$ is a set of positive integers, and let $S_{k}$ denote the set of subsets of $S$ with $k$ elements. Show that \[\text{lcm}(a_{1}, \cdots, a_{r})=\prod_{i=1}^{r}\prod_{s\in S_{i}}\gcd(s)^{\left((-1)^{i}\right)}.\]

Click for solution To prove equality, we will look at the exponent of any prime $ p$. If this is equal for any $ p$, both sides are equal. Terms $ a_{i}$ that do not divide $ p$ clearly don't affect this on both sides. So we can assume either only terms divisible by $ p$, or no terms divisible by $ p$. Since $ \sum_{i=1}^{r}(-1)^{i}\binom{r}{i}=1$, cancelling a factor $ p$ from all $ a_{i}$ leaves the equality invariant. So we can assume that no terms divide $ p$. But then there stands $ 1=1$ for the exponent of $ p$, so we're done.

Prove that if the odd prime $p$ divides $a^{b}-1$, where $a$ and $b$ are positive integers, then $p$ appears to the same power in the prime factorization of $b(a^{d}-1)$, where $d=\gcd(b,p-1)$.

Suppose that $m=nq$, where $n$ and $q$ are positive integers. Prove that the sum of binomial coefficients \[\sum_{k=0}^{n-1}{ \gcd(n, k)q \choose \gcd(n, k)}\] is divisible by $m$.

Determine all integers $n > 1$ such that \[\frac{2^{n}+1}{n^{2}}\] is an integer.

Determine all pairs $(n,p)$ of nonnegative integers such that $p$ is a prime, $n<2p$, $(p-1)^{n} + 1$ is divisible by $n^{p-1}$.

Click for solution If $ p = 2$ then $ (p - 1)^{n} + 1 = 2$ so $ n = 2$. If $ n = 1$ then $ (p - 1)^{n} + 1$ is divisible by $ n^{p - 1}$ for any prime $ p$. If $ n = 2$, then $ (p - 1)^{n} + 1$ must be even so $ (p - 1)^{n}$ is odd so $ p$ is even but it is prime therefore $ p = 2$. This gives the solutions $ (1,p)$ and $ 2,2$ when $ n\leq 3$ or $ p\leq 3$. Now look at the case when $ p,n\geq 3$. Because then $ p$ is odd, $ (p - 1)^{n} + 1$ is odd so $ n$ is odd. Let $ x$ be the greatest prime divisor of $ n$, then we have $ x|n|n^{p - 1}|((p - 1)^{n} + 1)$ so $ (p - 1)^{n}\equiv - 1\pmod x$. Now because $ x|n$ then $ x - 1$ and $ n$ are coprime so there will exist positive integers $ a,b$ such that $ an = b(x - 1) + 1$. Because $ n$ is odd, $ x$ is odd so $ b(x - 1)$ is odd so $ b(x - 1) + 1$ is even hence $ a$ is odd. But then, if $ (p - 1)^{n}\equiv - 1\pmod x$, $ (p - 1)^{an}\equiv - 1\pmod x$ therefore $ (p - 1)^{b(x - 1)}*(p - 1)\equiv - 1\pmod x$. But by Fermat's Little Theorem $ (p - 1)^{x - 1}\equiv 1\pmod x$ because $ x$ and $ p - 1$ are coprime (otherwise, it would be impossible to have $ n^{p - 1}|((p - 1)^{n} + 1)$ as $ x|n$. Then, $ (p - 1)^{b(x - 1)}*(p - 1)\equiv - 1\pmod x$ gives $ (1)^{b}*(p - 1)\equiv - 1\pmod x$ so $ p - 1\equiv - 1\pmod x$ so $ x|p$ so $ x = p$. But $ x|n$ and $ n < 2p$ so $ n = p$. Then $ n^{p - 1}|((p - 1)^{n} + 1)$ is equivalent to $ p^{p - 1 }|((p - 1)^{p} + 1)$ but if we expand $ (p - 1)^{p} + 1$ we get: $ p^{p - 1}| p^{p} - p^{p - 1}*\binom{p}{1} + p^{p - 2}*\binom{p}{2} + ... + p*\binom{p}{1} - 1 + 1$ or: $ p^{p - 1}|p^{2}(p^{p - 2} - p^{p - 3}*\binom{p}{1} + ... + \binom{p}{p - 2} + 1)$ and therefore $ p^{p - 1}|p^{2}$ because the expression in brackets is not divisible by $ p$ hence the only solution possible is if $ p - 1\leq 2$ so $ p\leq 3$. But we assumed $ p\geq 3$ so $ p = 3$ so $ n = 3$. So the solutions are $ (1,p), (2,2), (3,3)$

Determine all pairs $(n,p)$ of positive integers such that $p$ is a prime, $n>1$, $(p-1)^{n} + 1$ is divisible by $n^{p-1}$.

Find an integer $n$, where $100 \leq n \leq 1997$, such that \[\frac{2^{n}+2}{n}\] is also an integer.

Find all triples $(a,b,c)$ of positive integers such that $2^{c}-1$ divides $2^{a}+2^{b}+1$.

Find all integers $\,a,b,c\,$ with $\,1<a<b<c\,$ such that \[(a-1)(b-1)(c-1)\hspace{0.2in}\text{is a divisor of}\hspace{0.2in}abc-1.\]

Find all positive integers, representable uniquely as \[\frac{x^{2}+y}{xy+1},\] where $x$ and $y$ are positive integers.

Click for solution Rust wrote: Let $ n = \frac {x^2 + y}{xy + 1} > 1$, then $ x(x - ny) = n - y$ or $ y = \frac {x^2 - n}{nx - 1}$. From last we get $ x > n$. Other method: From : $ y = \frac {x^2 - n}{nx - 1}$ The equation has solution if and only if $ nx - 1|x^2 - n$ $ \Longleftrightarrow nx - 1|n^2(x^2 - n)$ $ \Longleftrightarrow nx - 1|n^3 - 1$ Case 1:$ n > 1$ $ \Longrightarrow nx - 1 = \frac {n^3 - 1}{d}$ $ \Longrightarrow nx = \frac {n^3 - 1 + d}{d}$ Imply that $ n|d - 1$ If $ d\geq n + 1$ then $ x < n$ (tradition!) So $ d = 1$ Imply that $ x = n^2,y = n$ Case 2 $ n = 1$ $ (y,x) = (t + 1,t)$

Determine all ordered pairs $(m, n)$ of positive integers such that \[\frac{n^{3}+1}{mn-1}\] is an integer.

Click for solution nicetry007 wrote: $ gcd(nm-1,\; nm) = 1 \;\Rightarrow\; gcd(nm-1,\; m) = 1 \;\Rightarrow \;gcd(nm-1,\; m^{3}) = 1$ $ \frac{n^{3}\;+\;1}{mn \;-\;1}\in Z \;\Leftrightarrow \;\frac{(mn)^{3}\;+\;m^{3}}{mn \;-\;1}\in Z\; \Leftrightarrow \;\frac{(mn)^{3}\;-\;1\;+\;m^{3}\;+\;1}{mn \;-\;1}\in Z \;\Leftrightarrow\; \frac{m^{3}\;+\;1}{mn \;-\;1}\in Z$ This implies that if $ (n,m)$ is a solution, then $ (m,n)$ is also a solution. Suppose $ n = m$. $ \frac{n^{3}\;+\;1}{n^{2}\;-\;1}\;=\; n \;+\; \frac{n \;+\;1}{n^{2}\;-\;1}\;=\; n \;+\; \frac{1}{n \;-\;1}\in Z \;\Leftrightarrow \;n \; = \; 2$ Suppose $ n < m$. [Note: Since $ (n,m)$ and $ (m,n)$ are both solutions, it is enough to consider $ n < m$] $ \frac{n^{3}\;+\;1}{mn \;-\;1}\in Z \;\Leftrightarrow\; \frac{mn^{3}\;+\;m}{mn \;-\;1}\in Z \;\Leftrightarrow\; \frac{mn^{3}\;-\;n^{2}\;+\;n^{2}\;+\;m}{mn \;-\;1}\in Z\; \Leftrightarrow \;\frac{n^{2}\;+\;m}{mn \;-\;1}\in Z$ Since $ \frac{n^{2}\;+\;m}{mn \;-\;1}\in Z$, $ n^{2}\;+\;m \;\geq \;mn \;-\;1 \;\Leftrightarrow\;\frac{n^{2}\;+\;1}{n \;-\;1}\;\geq\; m$ (i.e.) $ \;m \;\leq\; n\;+\;1 \;+\;\frac{2}{n\;-\;1}\;\Rightarrow\; m \;\leq\; n\;+\;3$. We need to consider 3 cases $ (i)\; m = n+1, \;(ii)\; m = n+2$ and $ (iii)\; m = n+3$. Plugging $ m = n+1, \; n+2$ and $ n+3$ in $ \frac{n^{2}\;+\;m}{mn \;-\;1}$, we get $ (n,m)$ that satisfy the relation. The pairs $ (n,m)$ that satisfy the relation are $ (2,2),\;(1,2),\;(2,1),\;(1,3), \;(3,1),\;(3,5),\;(5,3), \;(2,5),\;(5,2)$.

Determine all pairs of integers $(a, b)$ such that \[\frac{a^{2}}{2ab^{2}-b^{3}+1}\] is a positive integer.

Find all pairs of positive integers $m, n \ge 3$ for which there exist infinitely many positive integers $a$ such that \[\frac{a^{m}+a-1}{a^{n}+a^{2}-1}\] is itself an integer.

Click for solution Ok, I see now. Let me reword your first paragraph a bit. As the polynomial $ x^{m} + x - 1 \mod x^{n} + x^{2} - 1$ is zero for infinitely many $ x$'s, it is the zero polynomial. So $ x^{n} + x^{2} - 1|x^{m} + x - 1 = (x^n + x^2 - 1)x^k - (x - 1)(x^{k + 1} + x^k - 1)$, and since $ x = 1$ is not a root of $ x^{n} + x^{2} - 1$, it follows that $ x^{n} + x^{2} - 1|x^{k + 1} + x^k - 1$ (denote this $ f|g$). And then we continue mathmanman wrote: Now, it is clear that $ f$ has a root $ b \in ]0, 1[,$ and then $ b$ is a root of $ g,$ too. So we have $ b^n + b^2 - 1 = 0 = b^{k + 1} + b^k - 1.$ So we get (consider the degrees) that $ k \geq 2,$ and so $ b^n \geq b^{k + 1}$ and $ b^2 \geq b^k.$ Now, since $ 1 = b^n + b^2 \geq b^{k + 1} + b^k = 1,$ we must actually have $ k = 2, n = 3, m = 5.$ And finally the identity $ a^5 + a - 1 = (a^2 - a + 1)(a^3 + a^2 - 1)$ shows that the unique solution is the pair $ (m, n) = (5, 3).$

Determine all triples of positive integers $(a, m, n)$ such that $a^m +1$ divides $(a+1)^n$.

Which integers can be represented as \[\frac{(x+y+z)^{2}}{xyz}\] where $x$, $y$, and $z$ are positive integers?

Click for solution Among all positive integer triples satisfying $ \dfrac{(x + y + z)^2}{xyz} = k$ take the one with smallest $ \max\{x,y,z\}$. But Peter correctly got $ k\le9$. Consider the equation as a quadratic trinomial in $ x$. Then $ x^2 + x(2y + 2z - kyz) + (y + z)^2 = 0$. This has also the positive integer root $ kyz - 2y - 2z = \dfrac{(y + z)^2}x$. According to our choice of $ (x,y,z)$ we have $ z\le\dfrac{(x + y)^2}z$, hence $ z\le x + y$. Take now $ f(z) = \dfrac{(x + y + z)^2}{xyz} = z + \dfrac{(y + x)^2}{z} + 2(x + y)$. $ f'(z) = 1 - \dfrac{(x + y)^2}{z^2}$, thus the function attains its minimum at $ x + y$, hence it's decreasing on $ [y,x + y]$, from where $ k = f(z)\le\dfrac{(x + 2y)^2}{xy^2}$. Now, using $ x\le y$, we get $ k\le\dfrac{9y^2}{xy^2}\le9$, hence $ k\le9$. For $ k = 1,2,3,4,5,6,8,9$ we may use the examples Peter provided above. Let's handle $ k = 7$. Note that in the last inequality if $ 2\le x$ then we get $ k\le\dfrac92$. This means $ x = 1$. Now $ z\le 1 + y$ means $ z\in\{y,y + 1\}$. Both cases are handled easily leading to no solution.

Find all $n \in \mathbb{N}$ such that $ \lfloor \sqrt{n}\rfloor$ divides $n$.

Click for solution nicetry007 wrote: Suppose $ n = k^{2}$. Then $ \;\sqrt{n}\; = k$ and $ k \;| \;k^{2}$. Suppose $ k^{2}\;< \;n \;< \;(k+1)^{2}$ and $ n = k^{2}+c$. Then $ \lfloor \sqrt{n}\rfloor = k$. $ k\; |\; n\; \Leftrightarrow \;k\; |\; k^{2}+c \;\Leftrightarrow\; k\;|\; c \;\Leftrightarrow\; c = k$ or $ 2k$. Therefore, whenever $ n = k^{2}, \; k^{2}+k$ or $ k^{2}+2k\;$, $ \;\lfloor\sqrt{n}\rfloor\; |\; n$.

Determine all $n \in \mathbb{N}$ for which $n$ is not the square of any integer, $\lfloor \sqrt{n}\rfloor ^3$ divides $n^2$.

Find all $n \in \mathbb{N}$ such that $ 2^{n-1}$ divides $n!$.

Find all positive integers $(x, n)$ such that $x^{n}+2^{n}+1$ divides $x^{n+1}+2^{n+1}+1$.

Find all positive integers $n$ such that $3^{n}-1$ is divisible by $2^n$.

Find all positive integers $n$ such that $9^{n}-1$ is divisible by $7^n$.

Determine all pairs $(a, b)$ of integers for which $a^{2}+b^{2}+3$ is divisible by $ab$.

Determine all pairs $(x, y)$ of positive integers with $y \vert x^2 +1$ and $x^2 \vert y^3 +1$.

Determine all pairs $(a, b)$ of positive integers such that $ab^2+b+7$ divides $a^2 b+a+b$.

Let $a$ and $b$ be positive integers. When $a^{2}+b^{2}$ is divided by $a+b,$ the quotient is $q$ and the remainder is $r.$ Find all pairs $(a,b)$ such that $q^{2}+r=1977$.

Find the largest positive integer $n$ such that $n$ is divisible by all the positive integers less than $\sqrt[3]{n}$.

Find all $n \in \mathbb{N}$ such that $3^{n}-n$ is divisible by $17$.

Suppose that $a$ and $b$ are natural numbers such that \[p=\frac{b}{4}\sqrt{\frac{2a-b}{2a+b}}\] is a prime number. What is the maximum possible value of $p$?

Find all positive integers $n$ that have exactly $16$ positive integral divisors $d_{1},d_{2} \cdots, d_{16}$ such that $1=d_{1}<d_{2}<\cdots<d_{16}=n$, $d_6=18$, and $d_{9}-d_{8}=17$.

Suppose that $n$ is a positive integer and let \[d_{1}<d_{2}<d_{3}<d_{4}\] be the four smallest positive integer divisors of $n$. Find all integers $n$ such that \[n={d_{1}}^{2}+{d_{2}}^{2}+{d_{3}}^{2}+{d_{4}}^{2}.\]

Let $n$ be a positive integer with $k\ge22$ divisors $1=d_{1}< d_{2}< \cdots < d_{k}=n$, all different. Determine all $n$ such that \[{d_{7}}^{2}+{d_{10}}^{2}= \left( \frac{n}{d_{22}}\right)^{2}.\]

Let $n \ge 2$ be a positive integer, with divisors \[1=d_{1}< d_{2}< \cdots < d_{k}=n \;.\] Prove that \[d_{1}d_{2}+d_{2}d_{3}+\cdots+d_{k-1}d_{k}\] is always less than $n^{2}$, and determine when it divides $n^{2}$.

Find all positive integers $n$ such that $n$ has exactly $6$ positive divisors $1<d_{1}<d_{2}<d_{3}<d_{4}<n$ and $1+n=5(d_{1}+d_{2}+d_{3}+d_{4})$.

Find all composite numbers $n$ having the property that each proper divisor $d$ of $n$ has $n-20 \le d \le n-12$.

Click for solution nicetry007 wrote: Suppose $ n = a \cdot b$. We have $ n-20 \; \leq \; a \;\leq \; n-12$ $ n-20 \; \leq \; b \;\leq \; n-12$. multiplying the two inequalities, we get $ (n-20)^{2}\; \leq \; n \;\leq \; (n-12)^{2}$ The first inequality $ (n-20)^{2}\; \leq \; n$ gives us $ 16 \; \leq \; n \; \leq \;25$. The second inequality $ n \; \leq \;(n-12)^{2}$ gives us $ n\; \leq \;9$ or $ n \; \geq \;16$. Since we need to satisfy both the inequalities simultaneously, we get $ 16 \; \leq \; n \; \leq \;25$. Suppose $ n$ is even. Then we have $ n-20 \; \leq \; 2 \;\leq \; n-12$, which gives $ 14 \; \leq \; n \; \leq \;22$ and $ n-20 \; \leq \; \frac{n}{2}\;\leq \; n-12$, which gives $ 24 \; \leq \; n \; \leq \;40$. Since there is no $ n$ that satisfies both the inequalities, $ n$ cannot be even. This leaves us with $ n = 21$ and $ n=25$. It is easy to verify that both of them satisfy the required conditions.

Determine all three-digit numbers $N$ having the property that $N$ is divisible by $11,$ and $\frac{N}{11}$ is equal to the sum of the squares of the digits of $N.$

When $4444^{4444}$ is written in decimal notation, the sum of its digits is $ A.$ Let $B$ be the sum of the digits of $A.$ Find the sum of the digits of $ B.$ ($A$ and $B$ are written in decimal notation.)

A wobbly number is a positive integer whose $digits$ in base $10$ are alternatively non-zero and zero the units digit being non-zero. Determine all positive integers which do not divide any wobbly number.

Click for solution We show inductively for every $k$, there is a wobbly number $w_k$ having $2k-1$ digits such that $4^k$ divides it, but $2\cdot 4^k$ doesn't. $k=1$: just take $w_1=4$. For any $k$, we try to set $w_{k+1} = m_k\cdot 100^k+w_k$, $m_k \in \{1,2,...,9\}$. We want that $4^{k+1} \equiv w_{k+1} = m_k\cdot 100^k+w_k = m_k \cdot 4^k \cdot 25^k + 4^k w^\prime_k \mod 2\cdot 4^{k+1} $ (here $w_k=4^k w^\prime_k$ for some odd $w^\prime_k$). But that just means $4 \equiv m_k \cdot 25^k + w^\prime_k \mod 8$, which has a solution $m_k \mod 8$, meaning that we can choose our $m_k$ as required. Now if $s$ is some wobbly number and $n$ some integer coprime to $2,5$, then we find a multiple of $s$ being a wobbly number divisible by $sn$: Let $s$ have $2j-1$ digits and see that $s_k := \sum_{m=0}^{k-1} 100^{j\cdot m} s$ is wobbly again. But $s_k = s \cdot \frac{100^{kj}-1}{100^j-1}$, so we just have to take $k=\varphi((100^j-1)\cdot n)$ to get $100^{kj} \equiv 1 \mod ((100^j-1)\cdot n)$ and thus the result. The first two paragraphs show that for every integer $n$ coprime to $2,5$ we have that $n$, $5n$ ($s=5$ is wobbly) and $2^k n$ have multples being wobbly numbers. No wobbly number can be a multiple of $25$ because all multiples of that number end in $00,25,50,75$, not being allowed. Similar, no wobbly multiple of $10$ exists. As a result, exactly those $n$ have wobbly multiples that are not divisible by $10$ or $25$.

Find the smallest positive integer $n$ such that $n$ has exactly $144$ distinct positive divisors, there are ten consecutive integers among the positive divisors of $n$.

Click for solution Peter wrote: Out of curiosity, how do we have 10 consecutive positive divisors if $ 8\not|\ n$? I undestand second condition: exist divisors $ d_{k + 1} > d_k + 10.$ Among divisors $ d_{k}$ and $ d_{k + 1}$ had 10 consequitive numbers. If we have 10 consequitive divisors, then $ n=2^3*3^2*5^2*7*11$.

Determine the least possible value of the natural number $n$ such that $n!$ ends in exactly $1987$ zeros.

Click for solution As there are always more factors of 2 than 5 in $n!$ ($n \geq 2$), we need to find $n!$ with exactly $1987$ factors of 5 Now, amongst integers $\leq 8000$, there are- $1600$ multiples of $5$ $320$ multiples of $5^2=25$ $64$ multiples of $5^3=125$ $12$ multiples of $5^4=625$ $2$ multiples of $5^5=3215$. This totals 1998, which is 11 too many. So we have $n$ slightly less than 8000- if we reduce it to $7960$, then we have one fewer multiple of 125, two fewer multiples of 25 and 8 fewer multiples of 5, giving us $1987$ zeros on the end of $7960!$. We can't reduce this any further, because $7959!$ only has $1986$ zeros on the end, so the answer is $\boxed{7960}$

Find four positive integers, each not exceeding $70000$ and each having more than $100$ divisors.

Click for solution I will outline here an approach for the general problem: Find the positive integers $ n\in\overline{2,m}$ for which $ \tau(n)\ge t$, where $ \tau(n)$ represents the number of positive divisors of $ n$. Assume that $ n$ is a number satisfying the conditions. Write $ n = p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{r}^{\alpha_{r}}$, where $ p_{1}< p_{2}< ... < p_{r}$ are primes and $ \alpha_{1},\alpha_{2}, ...,\alpha_{r}$ are positive integers. So $ \tau(n) = (\alpha_{1}+1)(\alpha_{2}+1)\cdots (\alpha_{r}+1)\ge t$. Now, notice that $ m\ge n\ge p_{1}p_{2}...p_{r}\ge\mathcal{P}(r)$, where $ \mathcal{P}(r)$ is the product of the first $ r$ prime numbers. This gives a first upper bound for $ r$: denote it by $ r_{1}\in\mathbb{Z}$. Next, by AM-GM, $ \alpha_{1}+\alpha_{2}+...+\alpha_{r}\ge r(\sqrt [r]{t}-1)$, so $ m\ge n\ge 2^{\alpha_{1}+...+\alpha_{r}}\ge 2^{r(\sqrt [r]{t}-1)}$, which shows that $ r(\sqrt [r]{t}-1)\le\log_{2}(m)$. We infer some lower bound for $ r$, call it $ r_{0}\ge 1$. Now, we take each $ r\in [r_{0}, r_{1}]$ and try to find the corresponding set of solutions. One idea is to use the fact that $ m\ge n\ge p_{1}p_{2}...p_{r}\cdot 2^{\alpha_{1}+...+\alpha_{r}-r}$. Now we get that $ \alpha_{1}+\alpha_{2}+...+\alpha_{r}\le k$ for some positive integer $ k$ (for example, $ m = 70000$ and $ r = 4$ implies $ \alpha_{1}+...+\alpha_{r}\le 12$). Thus, if $ \beta_{1}, ...,\beta_{r}$ are the $ \alpha$s in increasing order, by the condition $ \tau(n)\ge t$ we see that $ (\beta_{1}, ...,\beta_{r})$ is in some set $ S$, and by rearrangement inequality $ m\ge n\ge q_{1}^{\beta_{r}}...q_{r}^{\beta_{1}}$, where $ q_{1}, ..., q_{r}$ are the first $ r$ primes, $ q_{1}< q_{2}< ... < q_{r}$. Eventually we will get a few $ r$-uples to deal with. In our case, $ m = 70000$, $ t = 100$, we get $ n\in\{ 45360, 50400, 55440, 60480, 65520, 69300\}$. The problem would be more suitable with lesser and more adequate bounds, still for the students not to try "computational" methods.

For each integer $n>1$, let $p(n)$ denote the largest prime factor of $n$. Determine all triples $(x, y, z)$ of distinct positive integers satisfying $x, y, z$ are in arithmetic progression, $p(xyz) \le 3$.

Click for solution You don't need Mihalescu, although it avoids a couple of lines of easy mod-bashing. Case 1: If b>1, the RHS is a multiple of 8, but the RHS is congruent 2 or 4 mod 8, so we cannot have a solution. Case 2: We have $1+2^{c-1}=3^b$ If $c\geq 3$, $b$ must be even considering mod 4, so let $b=2d$. Then $2^{c-1}=(3^d+1)(3^d-1)$ whence it is obvious that d=1 is the only solution, because only 4 and 2 are powers of two differing by 2.

Find all positive integers $a$ and $b$ such that \[\frac{a^{2}+b}{b^{2}-a}\text{ and }\frac{b^{2}+a}{a^{2}-b}\] are both integers.

Click for solution Let first $ a = b > 1$. Then $ a^{2} - a\mid a^{2} + a$ implies $ a^{2} - a\mid 2a$; hence $ a^{2} - a\leq 2a$ which is only possible for $ a\in\{2,3\}$. Simple checking shows that $ a = 2$ and $ a = 3$ are indeed solutions. Let's now assume that $ a\neq b$. Wlog assume that $ a > b$. Then $ a^{2} - b\mid b^{2} + a$ implies $ a^{2} - b\leq b^{2} + a$, so $ a(a - 1)\leq b(b + 1)$. Since $ a > b$, this is only possible for $ a = b + 1$ (in this case, we have equality). Now, $ b^{2} - a\mid a^{2} + b$ implies $ b^{2} - b - 1\mid b^{2} + 3b + 1$ and thus $ b^{2} - b - 1\mid 4b + 2$. This is true for $ b = 1$, for $ b\geq 2$, we have $ b^{2} - b - 1 > 0$ and hence we need $ b^{2} - b - 1\leq 4b + 2$, which is only possible for $ b\leq 5$. Simple checking shows that only $ b = 2$ and $ a = 3$ is actually a solution. We hence get the solutions \[ (a,b)\in \{ (2,2); (3,3); (1,2); (2,1); (2,3); (3;2)\}. \]

For each positive integer $n$, write the sum $\sum_{m=1}^n 1/m$ in the form $p_n/q_n$, where $p_n$ and $q_n$ are relatively prime positive integers. Determine all $n$ such that 5 does not divide $q_n$.

Find all natural numbers $n$ such that the number $n(n+1)(n+2)(n+3)$ has exactly three different prime divisors.

Prove that there exist infinitely many pairs $(a, b)$ of relatively prime positive integers such that \[\frac{a^{2}-5}{b}\;\; \text{and}\;\; \frac{b^{2}-5}{a}\] are both positive integers.

Click for solution Let $ b=2y,a=3y+x$, then $ a^2+b^2-5-3ab=x^2-5y^2-5=0$ give solution. $ x+y\sqrt 5 =(5+2\sqrt 5)(9+4\sqrt 5 )^k$ is solution.

Find all triples $(l, m, n)$ of distinct positive integers satisfying \[{\gcd(l, m)}^{2}= l+m, \;{\gcd(m, n)}^{2}= m+n, \; \text{and}\;\;{\gcd(n, l)}^{2}= n+l.\]

Click for solution The problem doesn't actually require $ m,n,l$ to be different. Anyway, this doesn't change anything. I will use $ (m,n)$ for $ \gcd(m,n)$ in this solution. Let $ (m,n) = a$, $ m = am'$. From $ m + n = a^2$, we get $ n = a^2 - am'$. In a similar way, let $ (m,l) = b$, $ m = bm''$ and $ l = b^2 - bm''$. Because $ (m',a - m') = 1$ and $ (m'',b - m'') = 1$ we have $ (a,m') = (b,m'') = 1$. From $ am' = bm''$ we deduce the existence of $ 4$ positive integers $ x,y,z,t$ pairwise coprime, such that $ a = xy$, $ m' = zt$, $ b = xz$, $ m'' = yt$. This is really a well-known fact; anyway, for showing it, start by taking $ \dfrac ab = \dfrac{m''}{m'} = \dfrac yz$, with $ (y,z) = 1$. Then $ n = a^2 - am' = x^2y^2 - xyzt$ and $ l = b^2 - bm'' = x^2z^2 - xyzt$. We have $ (n,l) = x(xy^2 - yzt,xz^2 - yzt) = x(xy - zt,xz - yt)$, because $ (y,xz^2) = (z,xy^2) = 1$. Then $ (n,l)^2 = n + l$ rewrites as $ x^2(xy - zt,xz - yt)^2 = x^2(y^2 + z^2) - 2xyzt$. This means $ 2xyzt$ is divisible by $ x^2$. But $ (x,yzt) = 1$, from where $ x|2$. Case 1 $ x = 2$. Because we're working with positive integers, $ xy - zt$ and $ xz - yt$ are positive, so $ 2y > zt$ and $ 2z > yt$, from where $ t = 1$. Then $ y^2 + z^2 - yz = (2y - z,2z - y)^2$. Suppose $ p^k||(2y - z,2z - y)$, where $ p$ is a prime number. Then $ p^k|4y - 2z + 2z - y$, or $ p^k|3y$. Similarly $ p^k|3z$. Since $ (y,z) = 1$, $ p = 3$ and $ k = 1$ or $ p$ doesn't exist at all. This means $ y^2 + z^2 - yz\in\{1,9\}$. The equation $ y^2 + z^2 - yz = 1$ has the only solution $ y = z = 1$. This case leads to $ m = n = l = 2$. Let's analyze $ y^2 + z^2 - yz = 9$. WLOG, let $ y\ge z > 0$ and let $ y = z + k$. Then the last equation becomes $ z^2 + zk + k^2 = 9$. The only solutions are $ z = 3$ and $ k = 0$. But then $ y = z = 3$ and $ (y,z)\neq1$. Case 2 $ x = 1$. Again, because we're working with positive integers, we must have $ xy > zt$ and $ xz > yt$, or $ y > zt$ and $ z > yt$, from where $ 1 > t$, impossible. The only such numbers are $ m = n = l = 2$.

What is the greatest common divisor of the set of numbers \[\{{16}^{n}+10n-1 \; \vert \; n=1,2,\cdots \}?\]

Click for solution Another way: $ 16^{n}+10 n-1\equiv (1+15)^{n}-15n-1\equiv\sum_{k = 2}^{n}{n\choose k}15^{k}\equiv 0\bmod 5^{2}$, for any $ n = 1, 2,\ldots$ Since $ 16^{1}+15\cdot 1-1 = 5^{2}$, the greatest common divisor we're looking for is exactly $ 5^{2}$.

Does there exist a $4$-digit integer (in decimal form) such that no replacement of three of its digits by any other three gives a multiple of $1992$?

Click for solution nicetry007 wrote: The multiples of 1992 less than 10000 are as follows:$ \{1992, 3984, 5976, 7968, 9960\}$. Essentially, we need to find a 4 digit number whose leading digit differs from the leading digit of all the multiples, whose second digit differs from the second digit of all the multiples and so on. The $ i$-th set in the following collection of sets is the set of feasible digits for the $ i$-th position. $ \{ \{2,4,6,8\}, \;\{0,1,2,3,4,5,6,7,8\}, \;\{0,1,2,3,4,5\}, \;\{1,3,5,7,9\}\}$. The smallest number satisfying the property is 2001 and there are $ 4 \cdot 9 \cdot 6 \cdot 5 = 1080$ numbers with the required property.

What is the smallest positive integer that consists base 10 of each of the ten digits, each used exactly once, and is divisible by each of the digits $2$ through $9$?

Find the smallest positive integer $n$ such that \[2^{1989}\; \vert \; m^{n}-1\] for all odd positive integers $m>1$.

Click for solution nicetry007 wrote: $ m^{n}\equiv 1 (mod \; 2^{1989})$ and $ gcd(m,2^{1989}) = 1$. We have $ m^{\phi(2^{1989})}\equiv 1 (mod \; 2^{1989})$. Since $ \phi(2^{1989}) = 2^{1988}$, $ m^{2^{1988}}\equiv 1 (mod \; 2^{1989})$. Hence, $ n \leq 2^{1988}$. Let $ p$ be the smallest positive integer such that $ m^{p}\equiv 1 (mod \; 2^{1989})$. Claim: $ p \;| \;2^{1988}$. Suppose not. $ 2^{1988}= pq+r$ where $ 0 < r < p$. We have $ m^{2^{1988}}\equiv 1 (mod \; 2^{1989})$ $ m^{pq+r}\equiv 1 (mod \; 2^{1989})$ $ (m^{p})^{q}\cdot m^{r}\equiv 1 (mod \; 2^{1989})$ $ m^{r}\equiv 1 (mod \; 2^{1989})$. This contradicts the minimality of $ p$. Hence , $ p | 2^{1988}$. Let $ p = 2^{k}$. $ m^{p}-1 = m^{2^{k}}-1 = (m^{2^{k-1}}+1)\; (m^{2^{k-2}}+1)\; \cdots \;(m^{2}+1)\; (m+1)\;(m-1)$. Each of the $ m^{2^{l}}+1$ is divisible by 2 but not by 4. $ (m+1)\;(m-1) = m^{2}-1$ is divisible by 8 and there exist $ m$ for which $ m^{2}-1$ is not divisible by 16 (for example, $ m = 3$). Hence, the highest power of 2 that divides $ m^{p}-1 = m^{2^{k}}-1$ is $ 2^{k-1+3}= 2^{k+2}$. This implies $ k = 1987$. In other words, the smallest $ n$ for which $ 2^{1989}\; | \; m^{n}-1$ is $ 2^{1987}$.

Determine the highest power of $1980$ which divides \[\frac{(1980n)!}{(n!)^{1980}}.\]