11
$\begingroup$

Find the smallest integer $a$ such that $P = a\cdot1!\cdot2!\cdot3!\cdot4!\cdot5!....\cdot18!$ is a perfect square.

This is a multiple-choice problem for a time-tight exam so I need to be as fast as possible. This is how I did:

Let $Q = 2!\cdot3!\cdot4!\cdot5!....17!\cdot18!$

All primes from $2$ to $18$ are $2, 3, 5, 7, 11, 13, 17.$

The goal is to determine whether the power of each prime is odd or even, and I do this by considering the multiples of each prime in $Q$.

There are $2$ instances of $17$ in $Q$ (from $17!$ and $18!).$ There are no other positive multiple of $17$ that is less than $18$, so the power of $17$ in $Q$ is even, and I can remove $17$ from my consideration. Similarly, I could quickly remove $13, 11.$

There are $12$ instances of $7$ in $Q$ (from $7!, 8!,...,18!$), $5$ instances of $14$ (from $14!, 15!,...,18!$), so we need one more $7$ to make the power even as each $14$ only contains one $7.$

At this point, I also noticed that since $18$ is even, if the multiple under consideration is odd, I have an even number of instances of that multiple, and if even, an odd number of instances (e.g. as shown above, there are $5$ instances of $14$). This helps speed up the evaluation.

Also, I would ignore multiples that contain an even power of the prime under consideration (e.g. $9 = 3^2$), as even while the number of instances is odd, the prime power it carries remains even.

Doing this, I could figure out that only prime $5$ contains an odd power in the remaining primes. So the answer is $a = 5\cdot7 = 35.$

It was the best way I could think of. I'm aware of a method to obtain the power of a certain prime $p$ in number $n!,$ but I couldn't find any better use of it other than to find the power of each prime in almost 18 numbers, which would take a very long time even with the help of a calculator. In the exam, I'm allowed to use a calculator like the one below, so I'd like to hear if there is a faster method to obtain the answer. Thank you! enter image description here

$\endgroup$
12
  • 3
    $\begingroup$ Your answer is correct $\endgroup$ Commented Jun 2, 2024 at 18:16
  • 1
    $\begingroup$ I should read the question, yes. By the way, we don't need a calculator for it. $\endgroup$ Commented Jun 2, 2024 at 18:18
  • 2
    $\begingroup$ To answer MC questions quickly it is often a good idea to develop a strategy based on the options presented (you have not included them) $\endgroup$ Commented Jun 2, 2024 at 18:37
  • 4
    $\begingroup$ I'm honestly baffled as to why my question is being downvoted and even suggested to be closed. I've been asking on this site in the same style and often with indication that I'm preparing for an exam in almost all of my previous posts without issues. Some of them are also with the elementary number theory tag. I'd appreciate it if someone could explain why. $\endgroup$ Commented Jun 2, 2024 at 18:47
  • 3
    $\begingroup$ Sorry, I can't think of a faster way, and I don't know why this question is getting down- and close-votes $\endgroup$ Commented Jun 2, 2024 at 19:01

2 Answers 2

Reset to default
12
$\begingroup$

A faster way might be to pair up adjacent factors: $$\prod_{k=1}^{18} k! = \prod_{k=1}^{9} (2k-1)!(2k)! = \prod_{k=1}^{9} (2k-1)!^2 (2k),$$ so you can equivalently consider $$2 \prod_{k=1}^{9} k = 2^8 \cdot 3^4 \cdot 5^1 \cdot 7^1,$$ and examining the odd powers yields $a=5\cdot 7$.

$\endgroup$
5
  • 3
    $\begingroup$ This is the way. $17!\cdot18! =18n^2$ for some $n$. $\endgroup$ Commented Jun 2, 2024 at 20:56
  • 2
    $\begingroup$ That... actually is faster... I'm impressed (not like the OP was anything one accurately call "slow") $\endgroup$ Commented Jun 2, 2024 at 23:02
  • 1
    $\begingroup$ Hmm... it boils down to how quickly you can factorize $2^9\cdot 9!$ and not make silly errors of dropping or adding terms with your note-taking. But $4$ multiples of $2$ (even) two multiples of $4$. Even. one multiple of $8$ odd, but match with $2^9$. Three multiples of $3$ odd but one of $9$ so matched. And one each of $5$ and $7$ both unmatched. So $a=5\cdot 7$ to match. Very nice! I doubt we can get faster. $\endgroup$ Commented Jun 2, 2024 at 23:32
  • $\begingroup$ Thank you very much! This is so brilliant! $\endgroup$ Commented Jun 3, 2024 at 4:49
  • $\begingroup$ @RobPratt I hit 'enter' by accident (reaching for the shift key) as I was typing my response. When I checked my thinking with regard to my fuller comment, I realized that $k$ was in fact the correct term. $\endgroup$ Commented Jun 3, 2024 at 15:16
2
$\begingroup$

A quick approach (after calculus) can be with p-adic valuation.

It is clear that primes in $a$ must be in $\{2,3,5,7,11,13,17\}$.

With Legendre rules for $p$ prime:

$$v_p(n!)=\sum_{k=1}^\infty \lfloor n/p^k \rfloor $$

and for $a,b$ integers:

$$ v_p(ab)=v_p(a)+v_p(b)$$

Noting $Q = P/a$ \begin{align} v_2(Q)&= 134 \\ v_3(Q)&= 62 \\ v_5(Q)&= 27 \\ v_7(Q)&= 17 \\ v_{11}(Q)&= 8 \\ v_{13}(Q)&= 6 \\ v_{17}(Q)&= 2 \end{align}

The only odd valuations are for $p=5$ and $p=7$ so $a=5\cdot7$ to complete $Q$ as a square.

$\endgroup$
3
  • $\begingroup$ Thanks I added it $\endgroup$ Commented Jun 3, 2024 at 0:06
  • $\begingroup$ Hi, thank you for your solution. I must admit, I don't yet have the necessary knowledge of the techniques you mentioned (i.e. p-adic valuation and Legendre's rules), so I'm finding it difficult to understand your answer. However, I plan to expand my knowledge of number theory in college, and I'm looking forward to revisiting your explanation and learning from it then! $\endgroup$ Commented Jun 3, 2024 at 4:53
  • 2
    $\begingroup$ Hi @ten_to_tenth thanks for your answer. I fully understand that now you may not have the full knowledge. Furthermore, I would indeed be a good idea to go forward and to discover the powerful tools of arithmetic such as modulo and p-adic valuation (as well as prime decomposition). All of these concepts are easily understandable ! Have a good path through this and more overall have fun ! $\endgroup$ Commented Jun 3, 2024 at 8:06

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.