Results 1 to 2 of 2

Math Help - A Challenging Proof...

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    19

    A Challenging Proof...

    Show there are 500 consecutive integers, each of which has at least 500 different primes in its factorization.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by iamthemanyes View Post
    Show 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:

    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:

    x\equiv 2\!\!\!\pmod3,
    x\equiv 2\!\!\!\pmod5,
    x\equiv 2\!\!\!\pmod7,
    x\equiv 1\!\!\!\pmod{11},
    x\equiv 1\!\!\!\pmod{13},
    x\equiv 1\!\!\!\pmod{17},
    x\equiv 0\!\!\!\pmod{19},
    x\equiv 0\!\!\!\pmod{23},
    x\equiv 0\!\!\!\pmod{29}.

    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 x-k\ (0\leqslant k\leqslant499). You just take a quarter of a million prime numbers p_j\ (1\leqslant j\leqslant 250000), 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 x\equiv r(j)\!\!\!\pmod{p_j}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Trigonometric Proof (Very Challenging)
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: January 28th 2009, 03:03 AM
  2. Replies: 2
    Last Post: July 14th 2008, 10:15 AM
  3. Challenging Integral?.
    Posted in the Calculus Forum
    Replies: 3
    Last Post: June 7th 2008, 10:56 AM
  4. Challenging Dif EQ
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 11th 2007, 05:01 PM
  5. challenging proof(section idea needed)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 17th 2006, 11:06 AM

Search Tags


/mathhelpforum @mathhelpforum