Mathematical Reflections 2012, Issue 1 - Problem J220

Problem:
Find the least prime $p$ for which $p=a^2_k+kb^2_k, k=1,\ldots,5$, for some $(a_k,b_k)$ in $\mathbb{Z} \times \mathbb{Z}$.

Proposed by Cosmin Pohoata.

Solution:

We have $p \equiv a^2_k \pmod{k}$ for $k=2,\ldots,5$, so $$\begin{array}{lll} p \equiv 1 \pmod{2} \\ p \equiv 1 \pmod{3} \\ p \equiv 1 \pmod{4} \\ p \equiv 1,4 \pmod{5}. \end{array}$$ Then $p=1+60n$ or $p=49+60n$ where $n \in \mathbb{N}$. Clearly $p \neq 1,49$. Moreover, $p \neq 61,109,121,169,181,229$ since $121,169$ are not primes and the equation
$$a^2_2+2b^2_2 \equiv 5 \pmod{8}$$ has no solution. We conclude that $p=241$ is the least prime which satisfies the given conditions, since
$$241=15^2+4^2=13^2+2\cdot6^2=7^2+3\cdot8^2=15^2+4\cdot2^2=14^2+5\cdot3^2.$$ 

Mathematical Reflections 2012, Issue 1 - Problem J219

Problem:
Trying to solve a problem, Jimmy used the following "`formula"': $\log_{ab} x = \log_a x \log_b x$,
where $a, b, x$ are positive real numbers different from $1$. Prove that this is correct only
if $x$ is a solution to the equation $\log_a x + \log_b x = 1$.

Proposed by Titu Andreescu.

Solution:

We have $\log_{ab} x = \dfrac{\log_a x}{1+\log_a b}$. So $$\log_{ab} x = \log_a x \log_b x \iff \dfrac{1}{1+\log_a b}=\log_b x \iff 1=\log_b x + \log_a b \log_b x.$$ Since $\log_b x = \dfrac{\log_a x}{\log_a b}$, we are done.

Mathematical Reflections 2012, Issue 1 - Problem J217

Problem:
If $a, b, c$ are integers such that $a^2 + 2bc = 1$ and $b^2 + 2ca = 2012$, find all possible values
of $c^2 + 2ab$.

Proposed by Titu Andreescu.

Solution:

Subtracting the two given equations, we have $(b-a)(b+a-2c)=2011$, so we get $$\left\{ \begin{array}{lll} b & = & a \pm 1 \\ 2c & = & b+a \mp 2011 \end{array} \right. \qquad \left\{ \begin{array}{lll} b & = & a \pm 2011 \\ 2c & = & b+a \mp 1. \end{array} \right.$$
Substituting these values into the equation $a^2+2bc=1$, we obtain the four equations

(i) $3a^2-2008a-2011=0$
(ii) $3a^2+2008a-2011=0$
(iii) $3a^2+6032a+2010\cdot2011-1=0$
(iv) $3a^2-6032a+2010\cdot2011-1=0$.

Equation (i) gives $(a+1)(3a-2011)=0$, so $a=-1, b=0, c=-1006$.
Equation (ii) gives $(a-1)(3a+2011)=0$, so $a=1, b=0, c=1006$.
Equations (iii) and (iv) have no solution since their discriminant is negative.
In conclusion, $c^2+2ab=1006^2=1012036$.

Mathematical Reflections 2011, Issue 6 - Problem O213

Problem:
Let $n$ be a positive integer and let $z$ be a complex number such that $z^{2^n-1}-1=0$. Evaluate
$$\prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right).$$

Proposed by Titu Andreescu.

Solution:

It's clear that if $z=1$, then $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=1$. Assume that $z \neq 1$. We have $$z^{2^n-1}-1=(z-1)(z^{2^n-2}+z^{2^n-3}+\ldots+z+1)=0,$$ so $z^{2^n-2}+z^{2^n-3}+\ldots+z+1=0$. Then,
$$\begin{array}{lll} \displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right) & = & \displaystyle \prod_{k=0}^{n-1}\left(z^{2^{k+1}}-z^{2^k}+1\right) \\  & = & \displaystyle  \prod_{k=0}^{n-1} \dfrac{z^{3\cdot2^k}+1}{z^{2^k}+1}.\end{array}$$ Clearly, $$\displaystyle \prod_{k=0}^{n-1} (z^{2^k}+1) = \sum_{k=0}^{2^n-1} z^k = z^{2^n-1} + \sum_{k=0}^{2^n-2} z^k = 1.$$ Let $n$ be odd. Since $\gcd(2^n-1,3)=1$, then $z^{3i} \neq z^{3j} \quad \forall i \not \equiv j \pmod{2^n-1}$. So, $$\displaystyle \prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = z^{3 (2^n-1)} + \sum_{k=0}^{2^n-2} z^{3k} = 1 + \sum_{k=0}^{2^n-2} z^k = 1,$$ which gives $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=1$. Now, let $n$ be even. Then $$z^{2^n-1}-1=(z^3-1)(z^{2^n-4}+z^{2^n-7}+\ldots+z^3+1)=0.$$ If $z$ is a third root of unity, then $z^3=1$ and
$$\prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = 2^n,$$ which gives $\displaystyle \prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=2^n$. If $z$ is not a third root of unity, since $z^{2^n-(3k+1)}=z^{3(2^n-1-k)}$, then
$$\prod_{k=0}^{n-1} (z^{3\cdot2^k}+1) = \sum_{k=0}^{2^n-1} z^{3k} = z^{3k(2^n-1)} + \sum_{k=1}^{2^n-1} z^{3(2^n-1-k)} = 1 + 3 \sum_{k=1}^{\frac{2^n-1}{3}} z^{2^n-(3k+1)} = 1.$$
In summary,
$$\prod_{k=0}^{n-1}\left(z^{2^k}+\dfrac{1}{z^{2^k}}-1\right)=\left\{ \begin{array}{lll} 2^n & \textrm{if } n \textrm{ is even and } z = e^{\frac{2i\pi}{3}},e^{\frac{4i\pi}{3}} \\ 1 & \textrm{otherwise.} \end{array} \right.$$

Mathematical Reflections 2011, Issue 6 - Problem O212

Problem:
Let $f_0(i)=1$ for all $i \in \mathbb{N}$ and let $f_k(n)=\displaystyle \sum_{i=1}^n f_{k-1}(i)$ for $k \geq 1$. Prove that
$$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j)=F_n,$$ where $F_n$ is the $n$-th Fibonacci number.

Proposed by Ivan Borsenco.

Solution:
First we show that if $n,k \geq 1$, then
\begin{equation}\label{identity1}
\sum_{i=k}^{n} {i \choose k} = {n+1 \choose k+1}. \qquad (1)
\end{equation}
By Pascal's Identity,
$$\begin{array}{lll} \displaystyle \sum_{i=k}^{n} {i \choose k} & = &  \displaystyle {k \choose k+1} + \sum_{i=k}^{n} {i \choose k}\\
& = & \displaystyle {k+1 \choose k+1} + \sum_{i=k+1}^{n} {i \choose k} \\ & = & \displaystyle {k+2 \choose k+1} + \sum_{i=k+2}^{n} {i \choose k} \\ & = & \displaystyle \vdots \\ & = & \displaystyle {n+1 \choose k+1}. \end{array}$$
Now, we prove by induction on $k \geq 1$ that $f_k(n)=\displaystyle {n+k-1 \choose k}$ for any $n \in \mathbb{N}$.
For $k=1$ we have $f_1(n)=\displaystyle \sum_{i=1}^n f_{0}(i)=n$, so the equality holds. Suppose that the equality is true for $k$. Then
$$f_{k+1}(n)=\sum_{i=1}^n f_{k}(i)=\sum_{i=1}^n {i+k-1 \choose k} = {n+k \choose k+1}$$ by (1). Now, it is clear that $$\sum_{j=0}^{\lfloor \frac{n}{2} \rfloor} f_j(n-2j) = \sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j}.$$ So, we only have to prove that $$\sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j}=F_n,$$ where $F_n$ is the $n$-th Fibonacci number. This can be done by induction on $n$. For $n=1$ and $n=2$ is obvious. Suppose that the equality holds for every $m$ such that $1 \leq m \leq n$. Since $\lfloor \frac{n-1}{2}  \rfloor + 1 = \lfloor \frac{n+1}{2} \rfloor$, we have
$$\begin{array}{lll} F_{n-1}+F_{n} & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n-1}{2}  \rfloor} {n-j-2 \choose j} + \sum_{j=0}^{\lfloor \frac{n}{2}  \rfloor} {n-j-1 \choose j} \\ & = & \displaystyle {n-1 \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2}  \rfloor}\left[{n-j-1 \choose j-1} + {n-j-1 \choose j}\right] \\ & = & \displaystyle
{n \choose 0} + \sum_{j=1}^{\lfloor \frac{n+1}{2}  \rfloor} {n-j \choose j} \\ & = & \displaystyle \sum_{j=0}^{\lfloor \frac{n+1}{2}  \rfloor} {n-j \choose j} = F_{n+1}, \end{array}$$ as we wanted to prove.

Mathematical Reflections 2011, Issue 6 - Problem O211

Problem:
Prove that for any positive integer $n$ the number $(2^n+4^n)^2+4(6^n+9^n+12^n)$ has at least $9$ positive divisors.

Proposed by Titu Andreescu.

Solution:
Rewriting,
$$(2^n+4^n)^2+4\cdot3^n(2^n+4^n)+4\cdot9^n = (2^n+4^n+2\cdot3^n)^2 = 2^2(2^{n-1}+2^{2n-1}+3^n)^2.$$ Since $4$ has three positive divisors and $2^{n-1}+2^{2n-1}+3^n \neq 2^k, k \in \mathbb{N}$ for every positive integer $n$, then $2^{n-1}+2^{2n-1}+3^n$ has one prime divisor $p > 2$. So, there are at least $3 \cdot 3 = 9$ positive divisors for the given number, namely $$\{1,2,4,p,2p,4p,p^2,2p^2,4p^2\}.$$

Mathematical Reflections 2011, Issue 6 - Problem U212

Problem: 
Let $G$ be a finite abelian group such that $G$ contains a subgroup $K \neq \{e\}$ with the
property that $K \subset H$ for each subgroup $H$ of $G$ such that $H \neq \{e\}$. Prove that $G$ is a
cyclic group.

Proposed by Daniel Lopez Aguayo.

Solution:

We use the following  

Lemma.
A finite abelian group is not cyclic if and only if it contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ for some prime $p$.

Proof.
Let $G$ be a finite abelian group. If $G$ contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ (which is not cyclic) then $G$ can't be cyclic since every subgroup of a cyclic group is cyclic. Conversely, if $G$ is a finite abelian group which is not cyclic then (by Fundamental Theorem of Finitely Generated Abelian Groups) $G$ contains a subgroup isomorphic to $\mathbb{Z}_{p^a} \times \mathbb{Z}_{p^b}$, because if all the components in the direct product correspond to distinct primes, then $G$ would be cyclic. So, the subgroup $(p^{a-1}) \times (p^{b-1})$ of $\mathbb{Z}_{p^a} \times \mathbb{Z}_{p^b}$ is isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$.

Now, suppose that $G$ is not a cyclic group. Then $G$ contains a subgroup isomorphic to $\mathbb{Z}_p \times \mathbb{Z}_p$ and this subgroup, by Cauchy's Theorem, contains a subgroup $H$ which is isomorphic to $\mathbb{Z}_p$. If $K \neq \{e\}$ is a proper subgroup of $H$, then, by Lagrange's Theorem, $|K|$ divides $|H|$, i.e. $|K|$ divides $p$. So $K=\{e\}$ or $K=H$, contradiction.

Mathematical Reflections 2011, Issue 6 - Problem U211

Problem:
On the set $M=\mathbb{R}-\{3\}$ the following binary law is defined:
$$x \ast y = 3(xy-3x-3y)+m,$$ where $m \in \mathbb{R}$. Find all possible values of $m$ such that $(M, \ast)$ is a group.

Proposed by Bogdan Enescu.

Solution:

First we observe that $x \ast y = 3(x-3)(y-3)+m-27$.
We want that $\ast$ satisfies the group axioms.

(i) Closure: For every $x,y \in M$, $x \ast y \in M$. It must be $3(x-3)(y-3)+m-27 \neq 3$, i.e. $3(x-3)(y-3)+m \neq 30$ and this is clearly satisfied for $m=30$.

(ii) Associativity: For every $x,y,z \in M, (x \ast y) \ast z = x \ast (y \ast z)$. It must be
$$\begin{array}{lll} [3(x-3)(y-3)+m-27] \ast z = 3[(3(x-3)(y-3)+m-27)-3][z-3]+m-27 \\
= 9xyz-27(xy+yz+zx)+3(27x+27y+(m-3)z)-8m \end{array}$$
and
$$\begin{array}{lll} x \ast [3(y-3)(z-3)+m-27] = 3(x-3)[3(y-3)(z-3)+m-27-3]+m-27 \\
= 9xyz-27(xy+yz+zx)+3((m-3)x+27y+27z)-8m, \end{array}$$
so the associativity holds if and only if $m=30$.

(iii) Identity element: There exists $e \in M$ such that for every $x \in M$, $x \ast e = e \ast x = x$. It must be
$$3(x-3)(e-3)+3=x \iff 3e(x-3)=10(x-3) \iff e=\dfrac{10}{3}.$$

(iv) Inverse element: For each $x \in M$, there exists $y \in M$ such that $x \ast y = y \ast x = e$. It must be
$$3(x-3)(y-3)+3=\dfrac{10}{3} \iff (x-3)(y-3)=\dfrac{1}{9} \iff y=\dfrac{1}{9(x-3)}+3.$$
So $(M,\ast)$ is a group if and only if $m=30$.

Mathematical Reflections 2011, Issue 6 - Problem S213

Problem:
Let $a,b,c$ be positive real numbers such that $a^2 \geq b^2+bc+c^2$. Prove that
$$a > \min(b,c) + \dfrac{|b^2-c^2|}{a}.$$

Proposed by Titu Andreescu.

Solution:
Without loss of generality, suppose that $\min(b,c)=c$. If $a \geq b+c$, then
$$a^2-ac \geq ab > (b+c)(b-c)=b^2-c^2.$$ If $a<b+c$, then
$$a^2-ac > a^2-(b+c)c \geq b^2 > b^2-c^2.$$ So, for any $a,b,c$ satisfying the required conditions, we have $a > \min(b,c) + \dfrac{|b^2-c^2|}{a}$.

Mathematical Reflections 2011, Issue 6 - Problem J215

Problem:
Prove that for any prime $p>3$, $\dfrac{p^6-7}{3}+2p^2$ can be written as sum of two perfect cubes.

Proposed by Titu Andreescu.

Solution:

We have
$$\begin{array}{lll} \dfrac{p^6-7}{3}+2p^2 & = & \dfrac{p^6+6p^2-7}{3}\\ & = & \dfrac{9p^6+54p^2-63}{27}\\
 & = & \dfrac{(p^6-12p^4+48p^2-64)+(8p^6+12p^4+6p^2+1)}{27} \\ & = & \left(\dfrac{p^2-4}{3}\right)^3 + \left(\dfrac{2p^2+1}{3}\right)^3\end{array}$$ and it is clear that the two summands on the right hand side are integers, since if $p > 3$, $p^2 \equiv 1 \pmod 3$.