Re: Fast Modular Factorial?

[Jim choate <ravage@bga.com>]

> 
> If (n!)mod x = 0 then there is a factor of x which is less than n.  If
> you can solve modular factorials, then you can solve for the largest
> factor of x in logarithmic time.  Obviously, nobody has found a method
> to do either.
> 
Just some thoughts...

If x < n then (n!)modx will always be 0. Since n! is simply the product of
the numbers 1...n and is always a integer product dividing by x simply
removes the factor m such that we have the product of 1...m-1,m+1...n.

If x>n and x is not a prime then the result will again always be 0 since
we can break x down into factors smaller than n and the previous argument
removes the various factors.

If x is prime and x>n then we will get a result that is non-zero.

Take care.