# Prime & Congruences

• Feb 21st 2010, 03:19 AM
kingwinner
Prime & Congruences

I know x^2 ≡ -2 (mod p) means that p|(x^2 -2), but I can't figure out how to continue with this.
Any help is appreciated!

[also under discussion in math links forum]
• Feb 22nd 2010, 12:35 AM
NonCommAlg
Quote:

Originally Posted by kingwinner

I know x^2 ≡ -2 (mod p) means that p|(x^2 -2), but I can't figure out how to continue with this.
Any help is appreciated!

[also under discussion in math links forum]

by Dirichlet's approximation theorem there exist integers $1 \leq k \leq \lfloor \sqrt{p} \rfloor$ and $m$ such that $|\frac{kx}{p} - m| \leq \frac{1}{\lfloor \sqrt{p} \rfloor + 1} < \frac{1}{\sqrt{p}}.$ which gives us $|kx - mp| < \sqrt{p}.$

now put $a=|kx - mp|$ and $b=k$ and show that $p \mid a^2 + 2b^2$ and $0 < a^2 + 2b^2 < 3p.$
• Feb 22nd 2010, 03:57 AM
kingwinner
Quote:

Originally Posted by NonCommAlg
by Dirichlet's approximation theorem there exist integers $1 \leq k \leq \lfloor \sqrt{p} \rfloor$ and $m$ such that $|\frac{kx}{p} - m| \leq \frac{1}{\lfloor \sqrt{p} \rfloor + 1} < \frac{1}{\sqrt{p}}.$ which gives us $|kx - mp| < \sqrt{p}.$

now put $a=|kx - mp|$ and $b=k$ and show that $p \mid a^2 + 2b^2$ and $0 < a^2 + 2b^2 < 3p.$

hmm...I haven't learnt that theorem yet...
Is it possible to solve this problem with more basic concepts?

thanks.