1
$\begingroup$

I have to compute the Legendre symbol $4307 \choose 7549$, so I have to factorize $4307$ into prime numbers. Is there any mathematical shortcut to do it?

$\endgroup$
7
  • $\begingroup$ Using what means? Wolfram|Alpha? Code? A calculator? Only your mind? $\endgroup$
    – joriki
    Jul 7 '16 at 6:52
  • 4
    $\begingroup$ Check for divisibility by primes up to $61$. There are only $18$ of them. $\endgroup$
    – David
    Jul 7 '16 at 6:53
  • 1
    $\begingroup$ I am looking for a mathematical shortcut, anyways I noticed that the way to do this is by directly applying the law of quadratic reciprocity on the Legendre symbol $\endgroup$ Jul 7 '16 at 6:54
  • $\begingroup$ Maybe there isn't a shortcut. And how much shorter than (potentially) $18$ divisions do you want? $\endgroup$
    – David
    Jul 7 '16 at 6:55
  • 2
    $\begingroup$ $4307=66^2-7^2$ $\endgroup$ Jul 7 '16 at 7:02
4
$\begingroup$

Of course, use the Jacobi symbol instead. The Jacobi agrees with the Legendre symbol for prime values, and also satisfies similar reciprocity laws. Specifically, for odd $m$ and $n$, we have $$\left(\frac{m}{n}\right)=(-1)^{\frac{(m-1)(n-1)}{4}}\left(\frac{n}{m}\right)$$and $$\left(\frac{2}{n}\right)=(-1)^{\frac{n^2-1}{8}}$$

Calculating $\left(\frac{4307}{7549}\right)$ becomes similar to the Euclidean Algorithm.

$\left(\frac{4307}{7549}\right)=(-1)^{\frac{(4306)(7548)}{4}}\left(\frac{7549}{4307}\right)=\left(\frac{3242}{4307}\right)=\left(\frac{2}{4307}\right)\left(\frac{1621}{4307}\right)=(-1)^{\frac{4307^2-1}{8}}(-1)^{\frac{(1620)(4306)}{4}}\left(\frac{4307}{1621}\right)=$

$-\left(\frac{1065}{1621}\right)=-(-1)^{\frac{(1064)(1620)}{4}}\left(\frac{1621}{1065}\right)=-\left(\frac{556}{1065}\right)=-\left(\frac{4}{1065}\right)\left(\frac{139}{1065}\right)=-(-1)^{\frac{(138)(1064)}{4}}\left(\frac{1065}{139}\right)=-\left(\frac{92}{139}\right)=-\left(\frac{4}{139}\right)\left(\frac{23}{139}\right)=-(-1)^{\frac{(22)(138)}{4}}\left(\frac{139}{23}\right)=-(-1)\left(\frac{1}{23}\right)=1$

The advantage here is that $m$ and $n$ do not need to be prime, and it will still agree with the symbol when the original values were prime. Also, the Euclidean algorithm is known to run very fast: $O(\log n)$

$\endgroup$
2
  • $\begingroup$ But reciprocity shows the Jacobi symbol $(5|21)=1$, even though 5 is a quadratic nonresidue modulo 21. $\endgroup$ Jul 7 '16 at 9:04
  • 1
    $\begingroup$ @GerryMyerson Yes, but since 7549 is prime, the first character can be regarded as the Legendre symbol, and the rest can just be regarded as a series of steps to get to the answer. Like I said, the Jacobi symbol agrees with the Legendre symbol for prime values. Had the original inputs both been composite, then an answer of $+1$ would be ambiguous, but that was not the case. $\endgroup$
    – JasonM
    Jul 7 '16 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.