Jim choate <ravage@bga.com> wrote:
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.
And there will always be such a value for m equal to kx where k is an integer less than n/x If x is non-prime, there may be factors f and g such that f*g=x. In that case, if n>f and n>g then n=0, hence finding the smallest value of n such that (n!)mod x =0, will yeild a factor of x. In that case, dividing by x would remove the factors f and g, yeilding a zero remainder.
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.
Yes, but if x is not prime, and x>n, (n!)mod x will not necessarily be zero, unless x>n>x/2 A few examples: mod 7: n 1 2 3 4 5 6 7 8 9 10 n! 1 2 6 3 1 6 0 0 0 0 mod 15: n 1 2 3 4 5 6 7 8 9 10 n! 1 2 6 9 0 0 0 0 0 0 Note that for mod 15, n=>5 produces only zeros, revealing the factor 5.