1
$\begingroup$

I'm trying to use FLINT (Fast Library for Number Theory) to calculate the Legendre Symbol of the following:

$$\left(\frac{n! + 1}{p}\right)$$

In my case, $p$ is a positive, odd prime (specifically $1,000,000,000,039 $), so I should be able to use the Jacobi symbol in its place when attempting to compute it.

How do I simplify the numerator if $n$ is a very large number, specifically $208,463,325,489$?

My current thought is that I would need to calculate n! mod p (which I believe is just a running product modulo p) and then add 1 before computing the symbol.

The value of n! mod p that I computed using FLINT is $133,008,788,325$, but I'm not sure if that's the correct value that I should be using in place of n! when computing the symbol.

Is it possible to simplify this mathematically so that I can verify that my computation is correct?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ So the question is actually about computing factorials modulo a prime, not Legendre symbols specifically $\endgroup$
    – Wojowu
    Commented Jun 10, 2019 at 20:41
  • $\begingroup$ @Wojowu That depends if computing a factorial modulo a prime is the correct method to use when computing the Legendre symbol, which is what I'm confused about. I'm having a lot of trouble finding any information about this online, so I'm just looking for a straight answer. $\endgroup$
    – Jacob G.
    Commented Jun 10, 2019 at 20:43
  • 1
    $\begingroup$ If it was just the factorial in the numerator, you probably could use multiplicativity of Legendre symbol. But with the $+1$, I see no way to proceed but to compute $n!+1\pmod p$... $\endgroup$
    – Wojowu
    Commented Jun 10, 2019 at 20:47
  • 2
    $\begingroup$ Yes, I realised it and deleted the comment ;-) $\endgroup$
    – Aurel
    Commented Jun 10, 2019 at 21:47
  • 1
    $\begingroup$ It seems that some people want to close this question reasoning "I don't see a good answer and I don't think that a good answer exists". Which I cannot agree with. $\endgroup$
    – Jan-Christoph Schlage-Puchta
    Commented Jun 12, 2019 at 10:50

0

Reset to default

You must log in to answer this question.