# What's the least positive integer that is not a factor of 25! and is not a prime number?

It's more of a question of what's the definition of factor. To my understanding, for a number 25, 1,5,25 would be the factor because 1*25=25and 5*5=25. It is a question from GRE official guide book and the answer is 58. I don't have difficulty in understanding what the answer is doing, it says 58 is the least number that is not a prime and doesn't contain factors from 1 to 25. What makes me feel uncomfortable is how this answer is related to the question. Obviously the factor of 25! will be 1,2,...,25. And the least that is not a prime would be 4 because I remember we don't count 1 as a prime. Even if the answer is 58, shouldn't the question be framed as something like:

What is the least integer that is not a prime and has no factors same to the factor of 25!?

In fact, I put 26 as the answer because I think 25! has factor 1,2,...,25 but 26 is not one of these factors and it is also a prime. I think I misunderstood what the question is asking about but I can't figure out what exactly is the problem.

• The question asked for a non-factor of 25!, not a factor. Sep 19, 2019 at 17:26
• and BTW 58 does have a factor equal to a factor of 25!, namely 2. Sep 19, 2019 at 17:27
• $26$ is a factor of $25!$ because notice $25!=1\cdot \color{red}{2}\cdot 3\cdot 4\cdots 12\cdot \color{red}{13}\cdot 14\cdots 24\cdot 25$, so $25! = 26\cdot (1\cdot 3\cdot 4\cdots 11\cdot 12\cdot 14\cdot 15\cdots 24\cdot 25)$ Sep 19, 2019 at 17:36

Being "not a factor of" and "having no factors the same" are two very different statements.

For positive integers $$a,b$$ the following statements are equivalent:

• $$a$$ is a factor of $$b$$
• $$a$$ divides $$b$$
• $$b$$ is a multiple of $$a$$
• $$\dfrac{b}{a}$$ is an integer
• There exists some integer $$k$$ such that $$b = ka$$
• $$b\pmod{a}=0$$
• $$\vdots$$

On the other hand "Shares a factor with" is something completely different. $$a$$ shares a factor with $$b$$ means that $$\gcd(a,b)>1$$.

It is also worth reminding you that $$25!=1\cdot 2\cdot 3\cdot 4\cdots 23\cdot 24\cdot 25$$ and that $$25!$$ has many factors greater than $$25$$., for example $$2250$$ is a factor of $$25!$$ since $$2250 = 9\cdot 10\cdot 25$$ and $$(9\cdot 10\cdot 25)\cdot (1\cdot 2\cdots 7\cdot 8\cdot 11\cdot 12\cdots 23\cdot 24) = 25!$$

• Oh yea, thank you for your side note. I think now I know where's the problem.
– JoZ
Sep 19, 2019 at 17:38

Certainly $$25!$$ is divisible by all of $$1,\ldots,25$$. If $$n$$ is between $$26$$ and $$50$$ and not prime, it can be written as $$ab$$ where $$a (except for $$n=49$$) and so divides $$25!$$. The same is true for $$51,52,54,55,56$$ and $$57$$. And $$49\mid (7\times 14)\mid 25!$$. So the only numbers from $$26$$ to $$57$$ inclusive not dividing $$25!$$ are primes. Of course $$58$$ has the prime factor $$29$$ and so cannot divide $$25!$$.

The least prime that is not a factor of $$25!$$ is $$29$$. Since we want it to be a composite, so the least composite number that is not a factor of $$25!$$ is $$2 \times 29=58$$.

• It might be good in a complete solution to also consider prime powers exceeding the number of factors in $25!$, e.g. $2^{(12+6+3+1)+1}$, $3^{(8+2)+1}$, $5^{(5+1)+1}$, $7^{3+1}$, $11^{2+1}$, $13^2$, $\ldots$, $23^2$ and verify they also all exceed 58. Sep 19, 2019 at 17:31