Modular Factorial

[plasmid]

Find all positive integers n such that (n-1)! modulo n = n-1.

More importantly, prove your answer.

This was something I noticed back in grade school while bored and playing around with a calculator, and only recently found out is an actual theorem that doesn't seem to be used for anything. But the proof is neat.

[robo]

This is true for each prime number n.

Working on a proof...

[robo]

For a non-prime n, the number (n-1)! will have n's factors. So (n-1)! modulo n will be 0. So it has to be a prime number that satisfies the equation.

What remains to prove is that for a prime n, the modulo is equal to n-1.

[Guest]

For a non-prime n, the number (n-1)! will have n's factors. So (n-1)! modulo n will be 0. So it has to be a prime number that satisfies the equation.

What remains to prove is that for a prime n, the modulo is equal to n-1.

For n=4 this does not work.

(n-1)!=6

6 modulo 4 = 2

what do you mean when you say (n-1)! will have n's factors?

Edited November 17, 2011 by thoughtfulfellow

[Guest]

n = (n-1)!

n = 0 + 1 + 2 + 3 + 4 + ..... + (n-1)

n = (n-n) + (n-(n-1)) + ................ + (n-3) + (n-2) + (n-1)

n = n^2 - n!

n = n^2 - n(n+1)/2 .......... n! = n(n+1)/2

2 = 2n - (n+1) .......... multiplying b.s. by 2/n

2 = 2n - n - 1

2 = n - 1

3 = n

n = 3

[plasmid]

Robo is correct about which numbers will satisfy this equation. Now it's just a matter of proving it.

Welcome to brainden wasim. This problem uses mudulo arithmetic, which often isn't taught in school (at least it wasn't for me). It essentially means considering only the remainder of a number after it's divided by another number. For example to calculate 17 modulo 5: 17 divided by 5 would be 3 with a remainder of 2, so 17 mod 5 = 2. That's what makes this problem tricky.

[Guest]

For a non-prime n, the number (n-1)! will have n's factors. So (n-1)! modulo n will be 0. So it has to be a prime number that satisfies the equation.

What remains to prove is that for a prime n, the modulo is equal to n-1.

I think what he means is that

Every composite number(n) other than a square of a prime will have at least four factors,

1, a, b, and n (where a and b are distinct and less than n and a*b=n)

As a, b are both less than n, they will be present in (n-1)!. We can take them out and as a*b=n, (n-1)! is divisible by n.

So remainder is 0.

Squares of primes will have three factors.

1, a, n (where a*a=n)

For squares of prime numbers greater than or equal to 3, a and 2a will be present in (n-1)!

(For example when n=9, a=3 and 2a=6 are present in 8!

n=25, a=5 and 2a=10 are present in 24!)

We can take both the a's out and as a*a=n, (n-1)! is again divisible by n.

So remainder=0 is true for all composite numbers except 4.

For 4, remainder is not 0, but it is not (n-1) either.

So the property (n-1)! modulo n = n-1 can only be satisfied by prime numbers.

Edited November 17, 2011 by SMV

[Guest]

Wilson's theorem states that a natural number n > 1 is a prime number if and only if (n-1)! is congruent to -1 mod n.

Since n is congruent to 0 mod n, we get (n-1)! is congruent to n-1 mod n.

[Guest]

by Euclid's multiplication theorem (not sure its real name) if you multiply by a series of numbers and add one, the new number will not be divisible by any of the numbers you multiplied by. therefore, it is either itself prime, or divisible by a prime not in the multiplication.

[plasmid]

jpf is correct about the name of the theorem, proofs of which can be found by googling if you give up on trying to work it out