I have a task in which I need to prove whether $n!$ is divisible by any integer $i$.
I already know that if $n!$ can be divided by $i$, then $n+1!$ can also be divided by $i$, so I really only need to find the lowest factorial divisible by i.
Also, evaluations such as "is $5!$ divisible by $4$?" are easy.
$5! = 5 * 4 * 3 * 2 * 1$ The fact that $4$ is a factor clearly means that $5!$ is divisible by $4$.
The problem comes when finding if $n!$ is divisible by an $i$ bigger than $n$.
For example, where $n = 21$ and $i = 560$.
The problem I've got specifies that I must be able to test values up to $2^{32}$ which is $4,294,967,296$.
This task is for a computer programming class. The point of the task was to get around the memory space issue raised by big numbers, and $4294967296!$ is a pretty big number (at least in terms of bits of data). Most computers will run out of space unless you import some special tools. My task was to work this out without using special tools.
I delved into the internet and found this:
$y = y * a \pmod i$
Start with $y = 1$ and increase $a$ by $1$ each time you perform the calculation. Example:
$y * a \pmod {560} = y$
$1 * 1 \pmod {560} \equiv 1$
$1 * 2 \pmod {560} \equiv 2$
$2 * 3 \pmod {560} \equiv 6$
$6 * 4 \pmod {560} \equiv 24$
$24 * 5 \pmod {560} \equiv 120$
$120 * 6 \pmod {560} \equiv 160$
$160 * 7 \pmod {560} \equiv 0$
If $y \equiv 0$ and $a$ is less than or equal to $n$, we know that $a!$ is divisible by $i$.
If $a$ goes above $n$ without $y$ ever reaching $0$, then we know that $n!$ is not divisible by $i$.
Indeed, $7! = 5040$ and $5040 / 560 = 9$
I should probably apologise:
I'm not from a mathematical background, so I struggle to read equations / formulas / proofs beyond the very basic. This either means I may have already used wrong symbols etc. or that I may not understand a particularly technical answer.
The last two hours I've spent googling don't tell me much except that this does work, rather than why or how.
The significance of this formula appears to be in taking the modulus of a previous operation and using that for the new operation, but why the modulus? Why exactly does that number allow us to always reach a conclusion?
EDIT
I have seen a post or two regarding Legendre's formula (also known as de Polignac's formula) suggesting this is a more efficient way for dealing with my problem.
I understand the workings, but am not sure how I use it?
For example, when finding out if 10,000 will divide 20!…?
According to Legendre's Formula I do the following:
$\nu_2 (20!) = \lfloor\frac{20}{2^1}\rfloor + \lfloor\frac{20}{2^2}\rfloor + \lfloor\frac{20}{2^3}\rfloor + \lfloor\frac{20}{2^4}\rfloor = 18$
$\nu_3 (20!) = \lfloor\frac{20}{3^1}\rfloor + \lfloor\frac{20}{3^2}\rfloor = 8$
$\nu_5 (20!) = \lfloor\frac{20}{5^1}\rfloor = 4$
$\nu_7 (20!) = \lfloor\frac{20}{7^1}\rfloor = 2$
$\nu_9 (20!) = \lfloor\frac{20}{9^1}\rfloor = 2$
$\nu_{11} (20!) = \lfloor\frac{20}{11^1}\rfloor = 1$
$\nu_{13} (20!) = \lfloor\frac{20}{13^1}\rfloor = 1$
$\nu_{17} (20!) = \lfloor\frac{20}{17^1}\rfloor = 1$
$\nu_{19} (20!) = \lfloor\frac{20}{19^1}\rfloor = 1$
Which then leaves us with:
$ 20! = 2^{18} \cdot 3^8 \cdot 5^4 \cdot 7^2 \cdot 9^2 \cdot 11^1 \cdot 13^1 \cdot 17^1 \cdot 19^1$
How do I get from here to deciding that 20! is divisible by 10,000?…
Best Answer
The short answer is: because the modulus tells us whether one number divides another.
Some elaboration on that cannot hurt, of course. So let us elaborate. The notation
$$a \equiv b \pmod{c},$$
where $a,b,c$ are integers, by definition means that $c$ divides $a-b$, i.e. there is an integer $k$ such that $a-b = k\cdot c$. Hence $c$ divides $a$ if and only if $a \equiv 0 \pmod{c}$, and to see whether $i$ divides $n!$, we must check whether $n! \equiv 0 \pmod{i}$. The thing that makes this feasible for large $n$ (and $i > n$, it's trivially true for $i \leqslant n$) is that we do not need to compute $n!$ to see what remainder that would leave when divided by $i$. The property that allows this is that for all integers $m$ we have the implication
$$\bigl(a \equiv b \pmod{c}\bigr) \implies \bigl( ma \equiv mb \pmod{c}\bigr).\tag{$\ast$}$$
This is easy to see: since $a\equiv b \pmod{c}$ means $a-b = k\cdot c$ for some integer $k$, it follows that $ma - mb = m(a-b) = mk\cdot c$ for that same $k$, and $mk$ is of course an integer. So $c$ divides $ma - mb$, i.e. $ma \equiv mb \pmod{c}$.
And your algorithm is just applying $(\ast)$ at each step in the calculation of the factorial. Inductively, if $k! \equiv r_k \pmod{i}$, then by $(\ast)$ we have
$$(k+1)! = (k+1)\cdot k! \equiv (k+1)\cdot r_k \pmod{i}.$$
And then $r_{k+1}$ is the remainder of $(k+1)\cdot r_k$ upon division by $i$.
And clearly, if $r_k = 0$, then $r_{k+1} = 0$ too, so if we ever have a remainder of $0$ before reaching $n$, then we also have $r_n = 0$, i.e. $i$ divides $n!$.
Reducing modulo $i$ at each step solves the space problem, since none of the intermediate results is larger than $i^2$. But it's not the most efficient algorithm, since it typically requires $O(n)$ multiplications and divisions (reductions modulo $i$). It is more efficient to find the prime factorisation of $i$ (in the range up to $2^{32}$ that is still efficiently done by trial division), and then check whether each prime dividing $i$ occurs with a high enough exponent in the prime factorisation of $n!$. The exponent of a prime $p$ in the factorisation of $n!$ is quickly found using de Polignac's formula.