Results 1 to 3 of 3

Thread: Prime & Congruences

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    405

    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]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by kingwinner View Post


    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 $\displaystyle 1 \leq k \leq \lfloor \sqrt{p} \rfloor$ and $\displaystyle m$ such that $\displaystyle |\frac{kx}{p} - m| \leq \frac{1}{\lfloor \sqrt{p} \rfloor + 1} < \frac{1}{\sqrt{p}}.$ which gives us $\displaystyle |kx - mp| < \sqrt{p}.$

    now put $\displaystyle a=|kx - mp|$ and $\displaystyle b=k$ and show that $\displaystyle p \mid a^2 + 2b^2$ and $\displaystyle 0 < a^2 + 2b^2 < 3p.$
    Last edited by NonCommAlg; Feb 22nd 2010 at 12:03 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    405
    Quote Originally Posted by NonCommAlg View Post
    by Dirichlet's approximation theorem there exist integers $\displaystyle 1 \leq k \leq \lfloor \sqrt{p} \rfloor$ and $\displaystyle m$ such that $\displaystyle |\frac{kx}{p} - m| \leq \frac{1}{\lfloor \sqrt{p} \rfloor + 1} < \frac{1}{\sqrt{p}}.$ which gives us $\displaystyle |kx - mp| < \sqrt{p}.$

    now put $\displaystyle a=|kx - mp|$ and $\displaystyle b=k$ and show that $\displaystyle p \mid a^2 + 2b^2$ and $\displaystyle 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Oct 22nd 2011, 12:37 PM
  2. Replies: 1
    Last Post: Jun 19th 2011, 12:56 PM
  3. Replies: 6
    Last Post: Aug 27th 2010, 11:44 PM
  4. Some congruences
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jan 3rd 2010, 03:42 PM
  5. congruences
    Posted in the Number Theory Forum
    Replies: 13
    Last Post: Mar 30th 2008, 10:11 AM

Search Tags


/mathhelpforum @mathhelpforum