MPMS Problem Solving Marathon

Latest News, Announcements, and Forum Rules
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
MPMS Problem Solving Marathon

Unread post by Phlembac Adib Hasan » 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)
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

aritra barua
Posts:57
Joined:Sun Dec 11, 2016 2:01 pm

Re: MPMS Problem Solving Marathon

Unread post by aritra barua » 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$.

User avatar
Zawadx
Posts:90
Joined:Fri Dec 28, 2012 8:35 pm

Re: MPMS Problem Solving Marathon

Unread post by Zawadx » 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$.

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: MPMS Problem Solving Marathon

Unread post by Phlembac Adib Hasan » 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.
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

dshasan
Posts:66
Joined:Fri Aug 14, 2015 6:32 pm
Location:Dhaka,Bangladesh

Re: MPMS Problem Solving Marathon

Unread post by dshasan » Sun Jun 04, 2017 10:45 pm

$\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
The study of mathematics, like the Nile, begins in minuteness but ends in magnificence.

- Charles Caleb Colton

dshasan
Posts:66
Joined:Fri Aug 14, 2015 6:32 pm
Location:Dhaka,Bangladesh

Re: MPMS Problem Solving Marathon

Unread post by dshasan » Mon Jun 05, 2017 10:32 am

$\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.
The study of mathematics, like the Nile, begins in minuteness but ends in magnificence.

- Charles Caleb Colton

aritra barua
Posts:57
Joined:Sun Dec 11, 2016 2:01 pm

Re: MPMS Problem Solving Marathon

Unread post by aritra barua » 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.

aritra barua
Posts:57
Joined:Sun Dec 11, 2016 2:01 pm

Re: MPMS Problem Solving Marathon

Unread post by aritra barua » 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.
Last edited by aritra barua on Mon Jun 05, 2017 2:13 pm, edited 1 time in total.

aritra barua
Posts:57
Joined:Sun Dec 11, 2016 2:01 pm

Re: MPMS Problem Solving Marathon

Unread post by aritra barua » 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$).

User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:

Re: MPMS Problem Solving Marathon

Unread post by Phlembac Adib Hasan » 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?
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

Post Reply