Is $77!$ divisible by $77^7$?

Question

Can $77!$ be divided by $77^7$?

Attempt:

Yes, because $77=11\times 7$ and $77^7=11^7\times 7^7$ so all I need is that the prime factorization of $77!$ contains $\color{green}{11^7}\times\color{blue} {7^7}$ and it does.

$$77!=77\times...\times66\times...\times55\times...\times44\times...\times33\times...\times22\times...\times11\times...$$

and all this $\uparrow$ numbers are multiples of $11$ and there are at least $7$ so $77!$ contains for sure $\color{green}{11^7}$

And $77!$ also contains $\color{blue} {7^7}:$

$$...\times7\times...\times14\times...\times21\times...\times28\times...\times35\times...42\times...49\times...=77!$$

I have a feeling that my professor is looking for other solution.

Answer 1

Your solution is right on!

You might be careful how you present it to your professor. I think it is fine, but here is other words saying the same thing. (I usually try to avoid too many $\dots$ in number theory proofs.)

$$ 11 = 1\cdot 11 \\ 22 = 2\cdot 11 \\ 33 = 3\cdot 11 \\ 44 = 4\cdot 11 \\ 55 = 5\cdot 11 \\ 66 = 6\cdot 11 \\ 77 = 7\cdot 11 $$ are all distinct factors in $77!$, so $11^7$ divides $77!$.

Likewise $$ 7 = 1\cdot 7 \\ 14 = 2\cdot 7 \\ 21 = 3\cdot 7 \\ 28 = 4\cdot 7 \\ 35 = 5\cdot 7 \\ 42 = 6\cdot 7 \\ 49 = 7\cdot 7. $$ are factors of $77!$, so $7^7$ divide $77!$

Now since $7$ and $11$ are coprime then also are $7^7$ and $11^7$, we conclude that $7^711^7$ divide $77!$.

Answer 2

Your solution is fine. For a more general case, you could see this question for the highest power of a prime dividing a factorial. If your professor had asked whether $2^{35}$ divides evenly into $77!$ hand counting would get very tedious.

Answer 3

If $p$ is a prime number, the largest number $n$ such that $p^n \mid N!$ is $\displaystyle n = \sum_{i=1}^\infty \left \lfloor \dfrac{N}{p^i}\right \rfloor$. Note that this is really a finite series since, from some point on, all of the $\left \lfloor \dfrac{N}{p^i}\right \rfloor$ are going to be $0$. There is also a shortcut to computing $\left \lfloor \dfrac{N}{p^{i+1}}\right \rfloor$ because it can be shown that

$$\left \lfloor \dfrac{N}{p^{i+1}}\right \rfloor = \left \lfloor \dfrac{\left \lfloor \dfrac{N} {p^i} \right \rfloor}{p}\right \rfloor$$

For $77!$, we get

$\qquad \left \lfloor \dfrac{77}{11}\right \rfloor = 7$

$\qquad \left \lfloor \dfrac{7}{11}\right \rfloor = 0$

So $11^7 \mid 77!$ and $11^8 \not \mid 77!$

Since $7 < 11$, it follows immediatley that $7^7 \mid 77!$. But we can also compute

$\qquad \left \lfloor \dfrac{77}{7}\right \rfloor = 11$

$\qquad \left \lfloor \dfrac{11}{7}\right \rfloor = 1$

$\qquad \left \lfloor \dfrac{1}{7}\right \rfloor = 0$

So $7^{12} \mid 77!$ and $7^{13} \not \mid 77!$

It follows that $77^7 = 7^{7} 11^7 \mid 77!$.

Added 3/9/2018

The numbers are small enough that we can show this directly

Multiples of powers of $7$ between $1$ and $77$

\begin{array}{|r|ccccccccccc|} \hline \text{multiple} & 7 & 14 & 21 & 28 & 35 & 42 & 49 & 56 & 63 & 70 & 77 \\ \hline \text{power} & 7 & 7 & 7 & 7 & 7 & 7 & 7^2 & 7 & 7 & 7 & 7 \\ \hline \end{array}

So $7^{12} \mid 77!$.

Multiples of powers of $11$ between $1$ and $77$

\begin{array}{|r|ccccccc|} \hline \text{multiple} & 11 & 22 & 33 & 44 & 55 & 66 & 77\\ \hline \text{power} & 11 & 11 & 11 & 11 & 11 & 11 & 11 \\ \hline \end{array}

So $11^7 \mid 77!$.

Hence $77^7 \mid 7^{12}11^7 \mid 77!$.

Answer 4

Although, the answer is already provided, I can't stress the usefulness of the Legendre's Theorem for resolving such class of problems. Especially the last one:

According to this really easy to grasp and remember result: $$\nu_7(77!)=\frac{77-5}{7-1}=12$$ $$\nu_{11}(77!)=\frac{77-7}{11-1}=7$$ Which means $$7^{12}\cdot 11^7 \mid 77!$$