If n is not prime and not of the form pq where p and q are prime

almost same https://artofproblemsolving.com/community/q2h1677309p10687542

anthonyshinex wrote: If n is not prime and not of the form pq where p and q are prime This is not true. Try $n=5\cdot 7$. Indeed, both $5^2$,$7^2$ divide $34!$.

The question is which positive integers $n$ satisfies $(1) \;\; n^2 \mid (n-1)!$. Let us consider the following cases: Case 1: $n=p$ is a prime. The fact that $p | m!$ ($m \in \mathbb{N}$) iff $p \geq m$ implies $n$ do not satisfy condition (1). Case 2: $n=2^r$, where $r \geq 2$. Inserting this in (1), the result is $(2) \;\; 2^{2r} \mid (2^r - 1)!$. According to Legendres formula the multiplicity of 2 in $(2r - 1)!$ is $\nu_2((2r - 1)!) = \sum_{k=1}^{\infty} \bigg[ \frac{2^r - 1}{2^k} \bigg] \geq \bigg[ \frac{2^r - 1}{2} \bigg] + \bigg[ \frac{2^r - 1}{2^2} \bigg] = \bigg[ 2^{r-1} - \frac{1}{2} \bigg] + \bigg[ 2^{r-2} - \frac{1}{4} \bigg] = (2^{r-1} - 1) + (2^{r-2} - 1) = 3 \cdot 2^{r-2} - 2 $. Now we have $3 \cdot 2^{r-2} - 2 \geq 2r$ for all $r \geq 4$, which means (2) is satisfied when $r \geq 4$. Checking we find that (2) is satisfied when $r \in \{2,3\}$. Case 3: $n = 2^r \cdot m$, where $r \geq 0$ and $m>1$ is an odd integer. Assume $r > 1$. Set $a=2^r$ and $b=m$. Then $ab=n$, yielding $(3) \;\; 2a = \frac{2n}{m} \leq \frac{2n}{3} < n$ and $(4) \;\; 2b = \frac{2n}{a} \leq \frac{2n}{2^2} = \frac{n}{2} < n$. Combining (3) and (4) with the fact that $b \neq 2a$ (since $b=m$ is odd) we find that $a,2a,b,2b$ are four distinct positive integers less than $n$. Hence $a \cdot (2a) \cdot b \cdot (2b) = 4(ab)^2 = 4n^2$ is a divisor of $(n - 1)!$, which give us $n^2 \mid (n - 1)!$. Assume $r=1$. If $m=p$ is a (odd) prime, then $p^2 \mid (2p - 1)!$ by (1), which is impossible since $2p - 1 < 2p < p^2$. Consequently $n = 2p$ do not satisfy condition (1). Finally assume $m$ is not an odd prime. Let $q$ be the smallest (odd) prime divisor if $m$. Set $a=2q$ and ${\textstyle b = \frac{m}{q}}$. Then $ab=n$ with $b \geq 3$, yielding $(5) \;\; 2a = \frac{2n}{b} \leq \frac{2n}{3} < n$ and $(6) \;\; 2b = \frac{2n}{a} = \frac{2n}{2q} = \frac{n}{q} \leq \frac{n}{3} < n$. Combining (5) and (6) with the fact that $b \neq 2a$ (since $b$ is odd) we find that $a,2a,b,2b$ are four distinct positive integers less than $n$. Hence $a \cdot (2a) \cdot b \cdot (2b) = 4(ab)^2 = 4n^2$ is a divisor of $(n - 1)!$, which give us $n^2 \mid (n - 1)!$. Conclusion: $n^2 \mid (n - 1)!$ iff $n$ is not a prime, $n \not \in \{4,8\}$ or $n \neq 2p$, where $p$ is an odd prime.

This question is highly similar to a past INMO problem, which stated Find all $n$ such that $n^2$ doesn't divide $(n-2)!$

Clearly $n=1$ is a solution and no prime $n$ works, as then $n$ does not divide any of $1$, $2$, $\ldots$, $n-1$. Suppose $n=ab$ for some integers $a\geq b \geq 2$. Firstly we look at $a>b$. If it happens that $(ab-1)!$ contains as distinct multipliers $a$, $b$, $2a$ and $2b$, it would follow that $(n-1)! = (ab-1)!$ is divisible by $a^2b^2 = n^2$. For this it suffices to have $ab - 1 \geq 2a$ and $a\neq 2b$, the former being true for $b\geq 3$. If $n=2b^2$, then direct check gives that $b=2$ does not work and for $b\geq 3$ we have $2b^2 - 1 \geq 4b$ and the multipliers $2$, $b$, $2b$, $3b$ and $4b$ are distinct, whence $(2b^2-1)!$ is divisible by $4b^4 = n^2$. The only remaining scenario here is when $b=2$ and $a\geq 3$ is prime (if $a\neq 4$ is not prime, then we have a representation $cd$ with $c\geq d>2$) and in this case the divisibility does not hold since $a^2$ divides $n^2$, but not $(2a-1)!$ (which contains $a$ only once as a multiplier). It remains to consider $a=b$, i.e. $n=a^2$ for integer $a\geq 2$. Direct check shows that $a=2$ and $a=3$ do not work and that $a=4$ works; let $a\geq 5$. Then the multipliers $a$, $2a$, $3a$ and $4a$ are distinct and appear in $(a^2-1)!$ (clearly $a^2 - 1 \geq 4a$ for $a\geq 5$), whence $a^4 = n^2$ divides $(a^2-1)! = (n-1)!$. Therefore all non-working $n$ are $6$, $8$, $p$ and $2p$ where $p$ is any prime.

Is n prime? Or just a positive integer

zaidova wrote: Is n prime? Or just a positive integer Positive integer