From: Jim choate <ravage@bga.com>
Date: Fri, 23 Sep 94 16:39:29 PDT
To: elton@sybase.com (Elton Wildermuth)
Subject: Re: Fast Modular Factorial?
In-Reply-To: <9409231852.AA05749@fnord.sybgate.sybase.com>
Message-ID: <199409232338.SAA21725@zoom.bga.com>
MIME-Version: 1.0
Content-Type: text


> 
> >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.
> 
> Unless I misunderstand you, this isn't true.  Any non-prime containing
> more prime factors than n! doesn't satisfy this test; nor does any
> non-prime containing factors > n.
>
Will think on this. It seems to me that if you have a even number of prime
factors you can multiply them out and get an even number which you should
be able to remove easily. Do you mean that the number of prime factors is
greater than n! or greater than the number of prime factors of n!? Also,
consider that in the case of a x>>n you might actually run out of enough
factors smaller than n to remove. This is one case I didn't have time to
look at earlier. Right now I am looking at behaviour where x>(n)^1/2 and
also when x>(n!)^1/2. 


> 	 6! == 2 * 3 * (2*2) * 5 * (2*3) == 720
> 	116 == 2 * 2 * 29
> 	 27 == 3 * 3 * 3
> 
> 	720 mod 116 == 24
> 	720 mod 27  == 18
> 
> 

        6!= 2 * 3 * 4 * 5 * 6 = 720

        116 is > 6 so this does not disprove my assertion. The factor which
is left over, ie 29, is prime.

        27 is > 6 so this does not seem to disprove it either since in 6!
there is a 3 * 3 which removes one of the factors and you are left with 3
which is prime.

Consider x=n again, this means that n! is really n(n-1)! and the mod of
(n!)modx is equivalent to n(n-1)!modx which leave us with a multiplicitive
factor of (n-1)! and a remainder of 0.           

One other point that may be irrelevant is that n! is always an even number.
The reason is that the very last multiplier is 2.