Jacobi Symbol

**ThePerfectHacker** · April 16th 2008, 07:00 AM

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

**milfner** · April 21st 2008, 07:31 PM

**ThePerfectHacker** · April 21st 2008, 07:34 PM

Originally Posted by milfner

Thanks for your reply. Can you please show me how you got the answer...

Explain which steps you cannot follow.

**milfner** · April 22nd 2008, 06:08 PM

All of them

**ThePerfectHacker** · April 22nd 2008, 07:13 PM

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.