Show $\nexists k:3^7\mid k!$ but $3^8\nmid k!$

Question

Show $\nexists k:3^7\mid k!$ but $3^8\nmid k!$

Ideas:

I need to find integer $m$ such that $m=\frac{k!}{3^7}$ and $m\neq\frac{k!}{3^8}$, but I have 2 unknowns so don't know how to proceed from here.

Hints to start would be appreciated- thanks!

Answer 1

The first prime factor $3$ in $k!$ occurs when $k=3$, then there is $1$ such factor.

The next time a new factor $3$ is added is when $k=2*3=6$, so then there are $2$.

The next time is when $k=3*3=9$, so then there are $4$

The next time is when $k=4*3=12$, so then there are $5$

$k=5*3$: $6$

$k=6*3=2*3*3$: $8$

So you cannot just have $7$ factors $3$.

Answer 2

$k<18\implies3^7\not|k!$

$k\geq18\implies3^8|k!\implies3^7|k!$

Answer 3

Let's see how many times the factor $3$ appears on $k!$, for growing $k$.

If $k=1,2$, then $k!$ is not divisible by $3$.

If $k=3,4,5$ then $k!$ is divisible by $3$, but not by $3^2$.

If $k=6,7,8$ then $k!$ is divisible by $3^2$, but not by $3^3$.

If $k=9,10,11$ then $k!$ is divisible by $3^4$, but not by $3^5$.

If $k=12,13,14$ then $k!$ is divisible by $3^5$, but not by $3^6$.

If $k=15,16,17$ then $k!$ is divisible by $3^6$, but not by $3^7$.

If $k=18,19,20$ then $k!$ is divisible by $3^8$, but not by $3^9$.

For $k \geq 21$, $k!$ is divisible by $3^9$. So, we have that $3^7$ divides $k!$ if and only if $3^8$ divides $k!$.

Answer 4

It's just a matter of tracking the exponents of $3$ in the prime factorization of $k!$ and taking note of the "jumps" at multiples of $9$ to see if you can find $7$ as an exponent for $3$.

• $5! = 2^3 \times 3 \times 5$
• $6! = 2^4 \times 3^2 \times 5$
• $9! = 2^7 \times 3^4 \times 5 \times 7$

$7!$ and $8!$ do nothing to move $3$'s exponent, but when we get to $9$, it jumps from $2$ to $4$: that's because $9 = 3^2$. So then $12! = 3^5 j$ (where $j$ is some number not divisible by $3$ which we don't care about at the moment), and $15! = 3^6 j$. Since $18 = 2 \times 3^2$ then $18! = 3^8 j$, and so we skip over $3^7$.

This means that if $3^7 | k!$ then so does $3^8$.

Answer 5

You have two "unknowns," but the situation is greatly simplified by the fact that there are "bounds" on $k$. Express $k!$ as $k! = 3^\alpha x$, where $\alpha$ and $x$ are both integers (yeah, more unknowns, bear with me). We're looking for which $k$ gives us $6 < \alpha < 8$. This should give us hopefully a few numbers such that $\alpha = 7$.

Verify that $17! = 2^{15} \times 3^6 \times 5^3 \times 7^2 \times 11 \times 13 \times 17$. Then $18! = 2^{16} \times 3^8 \times 5^3 \times 7^2 \times 11 \times 13 \times 17$. Whoops! What happened? We've found $\alpha = 6$ and we've found $\alpha = 8$. If we decrease $k$ from $17$, then $\alpha$ will stay at $6$ or decrease. And if we increase $k$ from $18$, then $\alpha$ will stay at $8$ or increase.

Therefore there is no $k$ such that $3^7|k$ is true but $3^8|k$ is false. Either both $3^7|k$ and $3^8|k$ are false or they're both true.