## MPMS Problem Solving Marathon

Latest News, Announcements, and Forum Rules
Posts: 1012
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

### MPMS Problem Solving Marathon

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: http://forum.matholympiad.org.bd/viewtopic.php?f=25&t=6

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

### Re: MPMS Problem Solving Marathon

For problem 1,if we substitute $a^2$=$4k$ where $k$ is an integer,we can easily find that $p$ |$a^2$+$1$.

Posts: 86
Joined: Fri Dec 28, 2012 8:35 pm

### Re: MPMS Problem Solving Marathon

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$.

Posts: 1012
Joined: Tue Nov 22, 2011 7:49 pm
Location: 127.0.0.1
Contact:

### Re: MPMS Problem Solving Marathon

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: http://forum.matholympiad.org.bd/viewtopic.php?f=25&t=6

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

### Re: MPMS Problem Solving Marathon

$\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.
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

### Re: MPMS Problem Solving Marathon

$\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: 48
Joined: Sun Dec 11, 2016 2:01 pm

### Re: MPMS Problem Solving Marathon

$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: 48
Joined: Sun Dec 11, 2016 2:01 pm

### Re: MPMS Problem Solving Marathon

$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: 48
Joined: Sun Dec 11, 2016 2:01 pm

### Re: MPMS Problem Solving Marathon

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$).