Secondary Special Camp 2011: NT P 3
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.
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.
Re: Secondary Special Camp 2011: NT P 3
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}$
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$.
Re: Secondary Special Camp 2011: NT P 3
Would you please give the proof of the corollary?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$.
...
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)
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)
Re: Secondary Special Camp 2011: NT P 3
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$.Masum wrote:$\text{Corollary}$ :
If $p|a^2+b^2$ with $p\equiv3\pmod 4$, then $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.
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.
Re: Secondary Special Camp 2011: NT P 3
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)
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)
Re: Secondary Special Camp 2011: NT P 3
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$.Zzzz wrote:Would you please give the proof of the corollary?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$.
...
One one thing is neutral in the universe, that is $0$.