[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected] (Elton Wildermuth)*Subject*: Re: Fast Modular Factorial?*From*: Jim choate <[email protected]>*Date*: Fri, 23 Sep 1994 18:38:46 -0500 (CDT)*Cc*: [email protected]*In-Reply-To*: <[email protected]> from "Elton Wildermuth" at Sep 23, 94 11:52:02 am*Sender*: [email protected]

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

- Prev by Date:
**CPs write Bumper Stickers** - Next by Date:
**Re: Fast Modular Factorial?** - Prev by thread:
**Re: Fast Modular Factorial?** - Next by thread:
**Re: Fast Modular Factorial?** - Index(es):