Introduction to Subfactorial Modulo Prime

The concept of a subfactorial, denoted as !n , is an important topic in combinatorics. It represents the number of derangements (permutations such that no element appears in its original position) of a set of n objects. When combined with number theory, specifically modular arithmetic with primes, the study of subfactorial modulo prime, !n mod p , introduces a fascinating area with diverse applications in cryptography, algorithm design, and theoretical computer science.

Derangement: Understanding Subfactorials

A derangement is a permutation of elements where no element appears in its initial position. The subfactorial !n can be calculated using the formula:

$$!n = n! \sum\_{i=0}^{n} \frac{(-1)^i}{i!}$$

This alternately adds and subtracts the reciprocals of factorials, resulting in the number of derangements for a set size n .

Subfactorial Modulo a Prime

The task of computing !n mod p where p is a prime number involves considering not only the derangements but also applying modular arithmetic. This interplay helps simplify expressions and manage large numbers efficiently.

Example Calculation

Let's compute !4 mod 5 .

First, calculate !4 : • Using the formula: 4! = 24

• Hence: $$!4 = 24 \left(\frac{(-1)^0}{0!} + \frac{(-1)^1}{1!} + \frac{(-1)^2}{2!} + \frac{(-1)^3}{3!} + \frac{(-1)^4}{4!}\right)$$ • Compute the sum: $$\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} = 0 + 0.5 - 0.166... + 0.04166... = 0.375$$

Then, !4 = 24 × 0.375 = 9 .

Finally, compute 9 mod 5 : • 9 mod 5 = 4

Thus, !4 mod 5 = 4 .

Fermat's Little Theorem and Its Role

Fermat's Little Theorem asserts that for any integer a not divisible by a prime p , $a^{p-1} \equiv 1 \ (\mathrm{mod} \ p)$. This property can simplify calculations in modular arithmetic. Specifically, the theorem provides a basis for simplifying powers and, consequently, helps in evaluating factorials and subfactorials modulo a prime:

If p is a prime and n < p , then:

• $n!^{p-1} \equiv 1 \ (\mathrm{mod} \ p)$

This simplification aids computational efficiency, especially when involving large numbers.

Wilson's Theorem

Wilson’s Theorem provides that for a prime number p , (p-1)! ≡ -1 (mod p) . It implies:

• For n = p - 1 , !n mod p becomes a special case considering this theorem.

Properties and Computational Considerations

1. Output Periodicity: The sequence !n mod p often shows periodic behaviors due to the repetition in modular reductions.
2. Computational Challenges: Large values of n require efficient algorithms to compute factorials and subfactorials. Modular arithmetic mitigates overflow and reduces computational complexity.
3. Pre-computable Tables: For fixed primes and manageable n , tables can be pre-computed to quickly reference !n mod p .

Table: Subfactorial Modulo Prime for Small n

and p

Conclusion

The study of subfactorials modulo a prime number accommodates significant insights into permutations and their properties, intersecting combinatorial mathematics and number theory. The use of classic theorems such as Fermat's Little Theorem and Wilson's Theorem fortifies practical implementations and fosters further exploration in both theoretical and applied contexts.