Page 1 of 2

### MPMS Problem Solving Marathon

Posted: Wed May 24, 2017 12:15 am
This is a general problem solving marathon for members of Mymensingh Parallel Math School (MPMS). However, feel free to participate, even if you are not a member.

PROBLEM 1:
$p$ is a prime number of the form $4k+1$. Prove that there exists an integer $a$ so that $a^2+1$ is divisible by $p$.

PROBLEM 2:
For every pair of positive integers $(m, n)$, prove that there exists integers $x$, and $y$ such that not both of them are zero, $-\sqrt{n} \leq x \leq \sqrt{n}$, $-\sqrt{n} \leq y \leq \sqrt{n}$, and $x-my$ is divisible by $n$.

BONUS PROBLEM:
Prove that every prime $p$ of the form $4k+1$ can be written as a sum of two squares.
(This result is known as Fermat's Two Square Theorem)

### Re: MPMS Problem Solving Marathon

Posted: Mon May 29, 2017 3:53 pm
For problem 1,if we substitute $a^2$=$4k$ where $k$ is an integer,we can easily find that $p$ |$a^2$+$1$.

### Re: MPMS Problem Solving Marathon

Posted: Mon May 29, 2017 5:02 pm
aritra barua wrote:For problem 1,if we substitute $a^2$=$4k$ where $k$ is an integer,we can easily find that $p$ |$a^2$+$1$.
For this you need to have $4k$ a perfect square, which isn't true for all $k$.

### Re: MPMS Problem Solving Marathon

Posted: Fri Jun 02, 2017 1:59 pm
PROBLEM 3:
Find all *odd* integers $n$ for which $4n^2-6n+45$ is a perfect square.

PROBLEM 4:
Find all positive integers $m$ and $n$ such that $7^m+11^n$ is a perfect square.

### Re: MPMS Problem Solving Marathon

Posted: Sun Jun 04, 2017 10:45 pm
$\text{Problem 1}$

### Re: MPMS Problem Solving Marathon

Posted: Mon Jun 05, 2017 10:32 am
$\text{Problem 3}$

### Re: MPMS Problem Solving Marathon

Posted: Mon Jun 05, 2017 1:17 pm
$Alternative Solution to 3$:It is obvious that if $4n^2$-$6n$+$45$ is a perfect square,then $4n^2$-$6n$+$45$ $\equiv$ $1$ (mod $2$) $\Rightarrow$ $4n^2$-$6n$+$45$ $\equiv$ $1$ (mod $4$) $\Rightarrow$ $1$-$6n$ $\equiv$ $1$ (mod $4$) $\Rightarrow$ $n$ $\equiv$ $0$ (mod $2$);so $n$ cannot be odd.

### Re: MPMS Problem Solving Marathon

Posted: Mon Jun 05, 2017 1:47 pm
$Problem 4$: If $7^m$+$11^n$ is a perfect square,then $m$ must be even and $n$ must be odd. (By using mod $3$ and mod $4$);let $m$=$2q$ and $n$=$2k$+$1$ and $49^q$+$121^k.11$=$a^2$ $\Rightarrow$ ($x$+$7^q$)($x$-$7^q$)=$121^k$.$11$.Now make a total of $2$ cases along with $6$ subcases each.$1$ case would be assuming $q$ to be odd and another even and use mod $6$ to check the subcases.In each case,we get a contradiction.So,there is no such $m$ and $n$ which satisfies the aforementioned condition.

### Re: MPMS Problem Solving Marathon

Posted: Mon Jun 05, 2017 2:09 pm
Simplier solution to problem $1$,I used this after getting to know what Wilson's Theorem is from dshasan's post.Let, $a$=$1$ . $2$...... $2k$.Telescope $a^2$ as $1$ . $2$.... $2k$.($-2k$)....($-2$)($-1$).From the telescoping,it follows $a^2$ $\equiv$ $1$.$2$....$2k$($p-2k$)....($p-2$)($p-1$) (mod $p$) $\Rightarrow$ $a^2$ $\equiv$ ($p-1$)! $\equiv$ $-1$ (mod $p$).So,$a^2+1$ $\equiv$ $0$ (mod $p$).

### Re: MPMS Problem Solving Marathon

Posted: Mon Jan 07, 2019 8:01 pm
Problem 5
A Hydra has $2019$ heads and is immune to damage from conventional weapons. However, with one blow of a magical sword, Hercules can cut off its $9, 10, 11$ or $12$ heads. In each of these cases, $5, 18, 7$ and $0$ heads grow on its shoulder. The Hydra will die only if all the heads are cut off. Can Hercules kill the Hydra with his sword?