From: Jim choate <ravage@bga.com>
Date: Fri, 23 Sep 94 10:56:02 PDT
To: mg5n+@andrew.cmu.edu (Matthew J Ghio)
Subject: Re: Fast Modular Factorial?
In-Reply-To: <EiUkmS600awSE3EGMO@andrew.cmu.edu>
Message-ID: <199409231755.MAA03386@zoom.bga.com>
MIME-Version: 1.0
Content-Type: text


> 
> 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.