LinkBack URL
About LinkBacksShow there are 500 consecutive integers, each of which has at least 500 different primes in its factorization.
As always with problems involving large numbers, think first about how to solve the same problem in the case of a small number, So:Originally Posted by iamthemanyes
Show there are 3 consecutive integers, each of which has at least 3 different primes in its factorization.
Suppose that the numbers are x–2, x–1 and x. The only prime that can be a factor of more than one of those numbers is 2. For simplicity, let's exclude the prime 2. Then we are going to need nine different primes in all, three to divide x–2, three to divide x–1 and three to divide x. For example, we could take the primes 3, 5, 7, 11, 13, 17, 19, 23, 29 and ask that 3, 5, 7 should be factors of x–2, that 11, 13, 17 should be factors of x–1, and that 19, 23, 29 should be factors of x. In terms of congruences, that gives us nine conditions:
Now all you have to do is to quote the Chinese remainder theorem to ensure that these congruences have a solution for x (it will be a large number, so I wouldn't want to have to find it explicitly).
Having seen how to do it for three consecutive numbers, you can now use the same argument to do it for 500 numbers. You just take a quarter of a million prime numbers
, write r(j) for the remainder when j is divided by 500, and use the Chinese remainder theorem to assert the existence of a solution to the 250000 congruences
\!\!\!\pmod{p_j}.)
  |
