Secondary Special Camp 2011: NT P 3

For discussing Olympiad Level Number Theory problems
User avatar
Moon
Site Admin
Posts:751
Joined:Tue Nov 02, 2010 7:52 pm
Location:Dhaka, Bangladesh
Contact:
Secondary Special Camp 2011: NT P 3

Unread post by Moon » Fri Apr 22, 2011 10:36 am

Problem 3: Prove that $y^2 = x^3 + 7$ has no integer solutions.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Secondary Special Camp 2011: NT P 3

Unread post by Masum » Sun Apr 24, 2011 9:49 am

Again a well-known problem, but it's solution is very nice because it uses the idea of quadratic congruence.
If $x$ even, $y^2\equiv-1\pmod 4$, so contradiction!
Therefore, $x$ odd. Then $y^2+1=(x+2)(x^2-2x+4)$

$\text{Lemma}$ : It is a very useful one in number theory.
Every odd prime divisor of $n^2+1$ is of the form $4k+1$.

$\text{ Proof}$ :
$n^2\equiv-1\pmod p\Longrightarrow n^4\equiv1\pmod p$.
Also, by Fermat's little theorem, $n^{p-1}\equiv1\pmod p$.
Thus, $4|p-1\Longrightarrow p\equiv1\pmod 4$.

$\text{Corollary}$ :
If $p|a^2+b^2$ with $p\equiv3\pmod 4$, then $p|a,p|b$.


Now, come back to the original problem.
Consider two cases.
$\#1$. $x\equiv1\pmod 4$.
Then $x+2\equiv3\pmod 4$ but it will have an odd prime of the form $4k-1$ an odd times, contradiction!
$\#2$. If $x\equiv1\pmod 4,x^2-2x+4\equiv-1\pmod4$, again contradiction.
But $4k-1\not| 1$, according to the corollary a contradiction follows and thus the equation has no solution in $\mathbb{N}$
One one thing is neutral in the universe, that is $0$.

User avatar
Zzzz
Posts:172
Joined:Tue Dec 07, 2010 6:28 am
Location:22° 48' 0" N / 89° 33' 0" E

Re: Secondary Special Camp 2011: NT P 3

Unread post by Zzzz » Tue May 10, 2011 4:14 pm

Masum wrote:...
$\text{Lemma}$ : It is a very useful one in number theory.
Every odd prime divisor of $n^2+1$ is of the form $4k+1$.

$\text{ Proof}$ :
$n^2\equiv-1\pmod p\Longrightarrow n^4\equiv1\pmod p$.
Also, by Fermat's little theorem, $n^{p-1}\equiv1\pmod p$.
Thus, $4|p-1\Longrightarrow p\equiv1\pmod 4$.

$\text{Corollary}$ :
If $p|a^2+b^2$ with $p\equiv3\pmod 4$, then $p|a,p|b$.
...
Would you please give the proof of the corollary?
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

User avatar
Moon
Site Admin
Posts:751
Joined:Tue Nov 02, 2010 7:52 pm
Location:Dhaka, Bangladesh
Contact:

Re: Secondary Special Camp 2011: NT P 3

Unread post by Moon » Tue May 10, 2011 10:24 pm

Masum wrote:$\text{Corollary}$ :
If $p|a^2+b^2$ with $p\equiv3\pmod 4$, then $p|a,p|b$.
Otherwise, $a^2\equiv -b^2 \pmod{p}$. Raising power to $\dfrac{p-1}{2} \equiv 1 \pmod{2}$ gives $a^{p-1}\equiv (-1)^{\frac{p-1}{2}}b^{p-1} \iff 1 \equiv -1 \pmod{p}$. Contradiction, unless $p|a,p|b$.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

User avatar
Zzzz
Posts:172
Joined:Tue Dec 07, 2010 6:28 am
Location:22° 48' 0" N / 89° 33' 0" E

Re: Secondary Special Camp 2011: NT P 3

Unread post by Zzzz » Wed May 11, 2011 7:49 am

Thank you :)
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: Secondary Special Camp 2011: NT P 3

Unread post by Masum » Wed May 11, 2011 2:02 pm

Zzzz wrote:
Masum wrote:...
$\text{Lemma}$ : It is a very useful one in number theory.
Every odd prime divisor of $n^2+1$ is of the form $4k+1$.

$\text{ Proof}$ :
$n^2\equiv-1\pmod p\Longrightarrow n^4\equiv1\pmod p$.
Also, by Fermat's little theorem, $n^{p-1}\equiv1\pmod p$.
Thus, $4|p-1\Longrightarrow p\equiv1\pmod 4$.

$\text{Corollary}$ :
If $p|a^2+b^2$ with $p\equiv3\pmod 4$, then $p|a,p|b$.
...
Would you please give the proof of the corollary?
In fact it is obvious since otherwise we have already got a contradiction that every prime factor of $a^2+b^2$ is of the form $4k+1$.
One one thing is neutral in the universe, that is $0$.

Post Reply