Results 1 to 3 of 3

Math Help - [SOLVED] Jacobi Symbol

  1. #1
    Member
    Joined
    Jul 2008
    Posts
    119

    [SOLVED] Jacobi Symbol

    Regarding the Jacobi symbol, suppose I want to find which positive odd integers that relatively prime to a prime p such as 13 i.e.

     \left( \frac{13}{n} \right) = 1?

    =============
    I understand that to do composite integers such as  \left( \frac{10}{n} \right) = \left( \frac{2}{n} \right) \left( \frac{5}{n} \right) = 1

    From here, we want (2/p) = (5/p) = 1 or (2/p) = (5/p) = -1.

     \left( \frac{2}{p} \right) =\begin{cases}<br />
+1&\text{if } p \equiv \pm 1 \pmod{8}\\<br />
-1&\text{if } p \equiv \pm 3 \pmod{8} \end{cases}

    and

     \left( \frac{5}{p} \right) =\begin{cases}<br />
+1&\text{if } p \equiv \pm 1 \pmod{5}\\<br />
-1&\text{if } p \equiv \pm 2 \pmod{5} \end{cases}

    Then by the Chinese Remainder Theorem, then  p \equiv \pm 1 \equiv \pm 3 \equiv \pm 9 \equiv \pm 13 \pmod{40}

    =============

    Similarly, how would you solve for big numbers such as 1040 in the simplest way? i.e. which positive odd integers n such that (1040, n) = 1 and (1040/n) = 1?

    Thank you for reading. Any help is greatly appreciated.
    Last edited by Paperwings; December 12th 2008 at 04:59 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Paperwings View Post
    Regarding the Jacobi symbol, suppose I want to find which positive odd integers that relatively prime to a prime p such as 13 i.e.

     \left( \frac{13}{n} \right) = 1?
    Use a generalized version of quadradic reciprocity law of Jacobi symbols.
    If a,b are odd, relatively prime, positive integers, then (a/b) = (b/a) if either a\text{ or }b\equiv 1(\bmod 4) otherwise (a/b) = - (b/a).

    Therefore, (13/n) = (n/13).
    Thus, for (n/13) = 1 we want the squares mod 13 which are 1,3,4,9,10,12.
    Therefore, n\equiv \pm 1, \pm 3, \pm 4 (\bmod 13).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2008
    Posts
    119
    Ah, ok. I was doing it a long way plugging into n such that

    n^{(p-1)/2} \equiv 1 \pmod{p} \implies n^{(13-1)/2} \equiv n^6 \equiv 1 \pmod{13}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Jacobi Symbol Properties
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 15th 2010, 07:08 PM
  2. Jacobi Symbol
    Posted in the Number Theory Forum
    Replies: 12
    Last Post: March 8th 2010, 09:53 PM
  3. Jacobi Symbol
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: May 1st 2008, 08:04 PM
  4. [SOLVED] The symbol for |
    Posted in the LaTeX Help Forum
    Replies: 3
    Last Post: April 22nd 2008, 07:55 PM

Search Tags


/mathhelpforum @mathhelpforum