11
$\begingroup$

I have a proof of this simple problem, but I feel that the last step is rather clunky:

For $n=1,2,3,4$ we have $n!+5=6,7,11,29$ respectively, none of which are square. Now assume that $n\geq 5$, then: $$\begin{aligned} n! +5 & \;=\; n(n-1)\cdots 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 + 5 \\[0.2cm] & \;=\; 5\left[ \frac{}{} n(n-1)\cdots 6\cdot 4 \cdot 3 \cdot 2 \cdot 1 + 1 \right] \\[0.2cm] &\;=\; 5(3k+1) \end{aligned}$$ for some $k\in\mathbb{N}$. Since $5(3k+1)=15k+5\equiv 5\,\text{mod} \, 15$ and all perfect squares are congruent either $0,1,4,6, 9$ or $10\,\text{mod}\,15$, the result follows. $\;\blacksquare$

It took a pretty tedious exhaustive search of squares modulo 15 in the last step; is there a theorem I am missing that means the last step follows immediately? Your comments are much appreciated!

$\endgroup$
  • 1
    $\begingroup$ How do you conclude $n(n−1)⋯6⋅4⋅3⋅2⋅1$ is a multiple of 5? It is not true when $n<10$. $\endgroup$ – pisco Aug 12 '17 at 7:30
  • $\begingroup$ Ah you're absolutely right @pisco125! I have edited it accordingly - does it make better sense doing it using this method? Though your proof below is a lot more simple and elegant. $\endgroup$ – AloneAndConfused Aug 12 '17 at 9:13
  • 1
    $\begingroup$ It does make sense now :). However, a number which is 5 modulo 15 is automatically 2 modulo 3, so you can choose to modulo 3 instead of modulo 15 in your work. $\endgroup$ – pisco Aug 12 '17 at 9:17
  • 1
    $\begingroup$ My edit was for a typo: In the 2nd line "$n=6,7..."$ should have been $n!+5=6,7..."$. $\endgroup$ – DanielWainfleet Aug 13 '17 at 18:33
25
$\begingroup$

When $n\geq 3$ $$n!+5 \equiv 2 \pmod{3}$$ So it cannot be a perfect square when $n\geq 3$.

$\endgroup$
5
$\begingroup$

As you can see from pisco125's brilliant answer, the step in which you deduce $n! + 5 = 15k + 5$ for $n \geq 5$ is in this case unnecessary.

With factorials you can usually rely on the fact that $d \mid n!$ for all $n \geq d$. This means $n!$ is divisible by 5 for all $n \geq 5$. Then, although 25 is a bigger modulo than 3 or 15, it's very convenient here, because if $m \equiv 5 \pmod{10}$, then $m^2 \equiv 0 \pmod{25}$. That is to say, 5 is not a square modulo 25. Of course this way you still have to check $n < 10$, whereas pisco's way you need only check $n < 3$.

$\endgroup$
3
$\begingroup$

It's rarely the most elegant way, but with factorials the most intuitive way is by looking at them modulo a power of $10$, such as $100$ or $1000$.

Thus $n! + 5 \equiv 5 \pmod{100}$ for $n > 9$. We know, since it is obvious, that $x^2 \equiv 5 \pmod{100}$ has no solution in integers.

Like I said, it's not elegant, because we still have to look at $n < 10$. We have $$6, 7, 11, 29, 25, 25, 45, 65, 25, 5$$ of which some of them might be squares (the $25$s), but turn out not to be very soon after we think about them.

$\endgroup$
3
+100
$\begingroup$

If $n! + p = k^2$ for some prime it's not too difficult to conclude $n < p$ and $k$ has no prime factors less than $p$, or $p \le n < 2p$, $\frac {n!}p + 1$ is divisible by $p$ and $\frac {\frac {n!}p + 1}p$ is a perfect square to no prime factors less than $p$[$*$].

We can go a bit further. $(p-1)! \equiv -1 \mod p$ by Wilson's Theorem so for $p \le n < 2p$ with $\frac {n!}p + 1\equiv 0 \mod p$ we can conclude $\frac {n!}p = (p-1)!\prod (p + k) \equiv -1 \mod p$ so $(n-p)! \equiv 1 \mod p$. And $n = p+1$ or $n = p + (p-2)= 2p-2$ so only two cases to check, if $n \ge p$.

So if $n < 5$ and $n! + 5 = k^2$ then $n! + 5 \ge 7^2$ which is simply not possible for $n\le 4; n! \le 24$

If $5\le n < 10$. then $\frac {n!}5 \equiv -1 \mod 5$. If $n = 5+k$ then $\frac {n!}5 = 4!*(6....n) \equiv 4!*k! \equiv -k! \equiv -1$ so $k! \equiv 1\mod 5$. So $k =1, 3$ and $n=6,8$. Which can be checked.

Which is probably much more clunky than your proof. But it could be useful for generalizing.

====

[$*$] $k \le n$ implies $k|n!$ so $k\not \mid n! +p$ unless $k = p$. If so $p|n! + p$ and $n! + p = p(\frac {n!}p + 1)$. If $n \ge 2p$ then $p|\frac {n!}p$ and $p \not \mid \frac{n!}p + 1$. If $n! + p$ is a perfect square and $p|n! + p$ then $p^2|n!+p$ and so $p \le n < 2p$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.