Question on Identifying Prime Factors of a Very Large Number

Question

Let $P$ be the product of all numbers less than $90$. Find the largest integer $N$ so that for each
$n∈$ {$2,3,4,...,N$}, the number $P+n$ has a prime factor less than 90.

Upon first thinking about this question, my plan of action was to find the first prime number that is larger than $P$ since that would guarantee that by that number, $P+n$ would not have a prime factor less than $90$.

So maybe the answer is one subtracted from that certain prime number.

However, obviously, $P$ is much too large a number to brute force this problem using that strategy nor to guess and check the answer.

So I'm stuck. When analyzing the prime factorization, where the answer might lie, I'm at a lost on how to deal with the added $+n$ to the product.

What actual steps am I supposed to take when answering this question?

Answer 1

Hint :

The number $$P+97$$ does not have a prime factor less than $90$ (Try to find out why). On the other hand, $$P+2,\cdots,P+96$$ have a prime factor less than $90$ (again try to find out why , hint : the second summand divides the sum). Hence the answer is $96$.

Answer 2

You are very close, but instead of focussing on $P$, you should focus on the largest prime factor of $P$, which is $89$. I'll answer the question you asked: what steps am I supposed to take?

Try to imagine $P + n$. You can visualise $P$ as $$ P = 2 \cdot 3 \cdot \ldots \cdot 89 $$ and $n$ as $$ n = p_{1} \cdot p_{2} \cdot \ldots \cdot p_{k} $$ where the $p_{i}$ are prime numbers (so this is the prime factorisation of $n$).

Then we have $$P + n = (2 \cdot 3 \cdot \ldots \cdot 89) + (p_{1} \cdot p_{2} \cdot \ldots \cdot p_{k})$$

This number can be divided by some prime $p_{i} \leq 89$ if and only if $p_{i}$ appears in both $P$ and $n$.

So we need to force $n$ to not have any $p_{i}$ from $1, \ldots, 89$.

Of course, if $n \leq 89$ then we must have some $p_{i} \leq 89$ since any $n$ can be factorised into primes and they all must be $\leq n$.

So how can we get at least one $p_{i} > 89$? Well, it must include the first prime $p$ larger than $89$. That is $97$. In fact, $97$ itself should be the smallest such $n$.

Let's now pick a few numbers at random and test our intuition:

$n = 35 = 7 \times 5$ contains $5$ which is in $P$ and $n$ and thus $P+n$. No good.

$n = 90 = 2 \times 3 \times 3 \times 5$ contains $2$. No good.

$n = 91 = 7 \times 13$. No good.

$n = 97 = \ldots$ Aha!

$n = 96, 95, 94, 93, 92$, these all have primes in common with $P$.

---

This is just to give you some idea about how I approached the problem in my mind, in the hope that it might help you approach similar problems in the future.

There are no 'steps' per se. Problems are very often not routine and don't have a clear and obvious method to follow. It requires turning the problem over in your mind, using some ideas you're familiar with (prime factorisation and algebra, in this case) and approaching from several angles until you find some insight.

---

As a final note, it is absolutely possible to brute force this using a computer. Here is some badly written sage code to solve this problem:

X = range(2,91)
for x in X:
    for k in range(2,int(sqrt(x))+1):
        if x % k == 0:
            X.remove(x)
            break

P = 1
for x in X:
    P *= x

n = 2
while any((P+n) % x == 0 for x in X):
    n += 1
print n

You can try this code by clicking here. I think this problem is best solved on paper. But sometimes making the computer find the answer and then figuring out why that is the answer is a useful learning experience.