Page 1 of 2

MPMS Problem Solving Marathon

Posted: Wed May 24, 2017 12:15 am
by Phlembac Adib Hasan
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
by aritra barua
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
by Zawadx
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
by Phlembac Adib Hasan
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
by dshasan
$\text{Problem 1}$
Stronger claim: There exists an integer $a$ and prime $p$ such that $p|a^2 + 1$ if and only if $ p\equiv 1(mod 4)$

Proof: For the first part, we have

$a^2 + 1 \equiv -1(mod p)$

$\Rightarrow (a^2)^{\dfrac{p-1}{2}} \equiv -1^{\dfrac{p-1}{2}}(mod p)$

$\Rightarrow 1 \equiv -1^{\dfrac{p-1}{2}}(mod p)$

That is only possible when $p \equiv 1(mod 4)$

Now, for the second part, we have by Wilson's theorem,
$(p - 1)! \equiv -1(mod p)$

$\Rightarrow -1 \equiv (1)(p-1)(2)(p-2).......[(\dfrac{p-1}{2})(\dfrac{p+1}{2})] (mod p)$

$\Rightarrow -1 \equiv (1)(-1)(2)(-2).......[(\dfrac{p-1}{2})(-\dfrac{p-1}{2})] (mod p)$

$\Rightarrow -1 \equiv -1^{\dfrac{p-1}{2}}[(\dfrac{p-1}{2})!]^2 (mod p)$

$\Rightarrow -1 \equiv [(\dfrac{p-1}{2})!]^2 (mod p)$

Therefore, setting $a = [(\dfrac{p-1}{2})!]$, we get $p | a^2 + 1$, as desired. :D

Re: MPMS Problem Solving Marathon

Posted: Mon Jun 05, 2017 10:32 am
by dshasan
$\text{Problem 3}$
Let $4n^2 - 6n + 45 = (2k+1)^2$

$\Rightarrow (2n-3)^2 +36 + 6n = (2k + 1)^2 $

$\Rightarrow 36 + 6n = (2k + 1)^2 - (2n-3)^2$

$\Rightarrow 6(6 + n) = (2k + 2n -2)(2k -2n + 4)$

$\Rightarrow 3(6 + n) = (k + n -1)(k - n + 2)$

Now, for odd $n$, $3(6 + n)$ is odd. And $(k + n -1)$ and $(k - n + 2)$ both have different parity. Therefore
$(k +n +1)(k - n + 2)$ is even, so contradiction.

Re: MPMS Problem Solving Marathon

Posted: Mon Jun 05, 2017 1:17 pm
by aritra barua
$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
by aritra barua
$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
by aritra barua
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
by Phlembac Adib Hasan
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?