# Jacobi Symbol

• Apr 16th 2008, 01:35 AM
milfner
Jacobi Symbol
(Angry)
• Apr 16th 2008, 08:00 AM
ThePerfectHacker
Quote:

Originally Posted by milfner
Use the fast computation method without factoring (except for removing 2’s) to determine the Jacobi symbol (13925 / 3927611)

Mention all formulas you apply as you apply them

(13925/3927611) = (3927611/13925) = (761/13925) = (13925/761) = (227/761) = (761/227) = (80/227) = (5/227) = (227/5) = (2/5) = -1

(Whew)
• Apr 21st 2008, 08:31 PM
milfner
(Angry)
• Apr 21st 2008, 08:34 PM
ThePerfectHacker
Quote:

Originally Posted by milfner

Explain which steps you cannot follow.
• Apr 22nd 2008, 07:08 PM
milfner
• Apr 22nd 2008, 08:13 PM
ThePerfectHacker
The Jabobi symbol is a generalization of the Legendre symbol. Given two integers $a,b$ where $b>1$ and odd. Define $(a/b) = (a/p_1)...(a/p_m)$ where $b=p_1...p_m$ is a factorization of not necessarily distinct primes (here the RHS is the regular Legendre symbol).

Here are some simple properties.
• $(a_1/b) = (a_2/b)$ if $a_1\equiv a_2(\bmod b)$
• $(2/b) = (-1)^{(b^2-1)/8}$
• $(a_1a_2/b) = (a_1/b)(a_2/b)$
• $(a/b)(b/a) = (-1)^{(a-1)/2\cdot (b-1)/2}$ where $a$ is odd and > 1

All of these were used. Figure out which ones.
• May 1st 2008, 08:04 PM
milfner
(Angry)