0
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ The question asked for a non-factor of 25!, not a factor. $\endgroup$
    – 79037662
    Sep 19, 2019 at 17:26
  • $\begingroup$ and BTW 58 does have a factor equal to a factor of 25!, namely 2. $\endgroup$
    – 79037662
    Sep 19, 2019 at 17:27
  • $\begingroup$ $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)$ $\endgroup$
    – JMoravitz
    Sep 19, 2019 at 17:36

3 Answers 3

Reset to default
1
$\begingroup$

Too long for a comment, but answering some of your side questions. For the answer to the actual question, see the other answers already posted.

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!$

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

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<b\le 25$ (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!$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Daniel Schepler
    Sep 19, 2019 at 17:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .