# How to factorize a number into prime numbers

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?

• Using what means? Wolfram|Alpha? Code? A calculator? Only your mind? Jul 7 '16 at 6:52
• Check for divisibility by primes up to $61$. There are only $18$ of them. Jul 7 '16 at 6:53
• 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 Jul 7 '16 at 6:54
• Maybe there isn't a shortcut. And how much shorter than (potentially) $18$ divisions do you want? Jul 7 '16 at 6:55
• $4307=66^2-7^2$ Jul 7 '16 at 7:02

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)$
• But reciprocity shows the Jacobi symbol $(5|21)=1$, even though 5 is a quadratic nonresidue modulo 21. Jul 7 '16 at 9:04
• @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. Jul 7 '16 at 18:22