1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number Theory: Define G(n) and show property for any prime p

  1. Oct 15, 2011 #1
    1. The problem statement, all variables and given/known data

    Define the numbers

    [tex] G_n = \prod_{k=1}^n (\prod_{j=1}^{k-1}\frac{k}{j}).[/tex]

    (a) Show that [itex]G_n[/itex] is an integer, [itex]n>1[/itex];

    (b) Show that for each prime [itex]p[/itex], there are infinitely many [itex]n>1[/itex] such that [itex]p[/itex] does not divide [itex]G_n.[/itex]

    2. Relevant equations

    3. The attempt at a solution

    I can see that the expansion is

    [tex] G_n = (\prod_{j=1}^{0}\frac{k}{j}) (\dfrac{2}{1})(\dfrac{3}{1}\dfrac{3}{2})...(\dfrac{n}{1}\dfrac{n}{2}...\dfrac{n}{n-1}).[/tex]

    However, what happens when n = 1, or more specifically, in the first factor of the general expansion where k = 1? Do we simply ignore [itex]\prod_{j=1}^{0}\frac{k}{j}[/itex]? Does it equal 1? I assume it doesn't equal 0, or the function would always equal 0. Once I understand this, I might actually be able to work the problem.
  2. jcsd
  3. Oct 15, 2011 #2
    Okay, now. Computing the first few values yields the sequence 1, 2, 9, 96, 2500,... which are the products across consecutive horizontal rows of Pascal's triangle.

    [tex]1 = 1[/tex]
    [tex]2 = 1*2*1[/tex]
    [tex]9 = 1*3*3*1[/tex]
    [tex]96 = 1*4*6*4*1[/tex]
    [tex]2500 = 1*5*10*10*5*1[/tex]

    and so on. In other words, it should be possible to convert [itex]G_n[/itex] to the product of the binomial coefficients [itex] \prod_{k=0}^n\dbinom{n}{k}. [/itex] Now, how to do that? I tried writing out both sides and equating them but am having a bit of trouble with all the number shunting.
  4. Oct 15, 2011 #3
    I proved the equality of [itex]G_n[/itex] with the product of the binomial coefficients, implying that [itex]G_n[/itex] is an integer for every [itex]n>1[/itex], as the product of a finite number of integers is also an integer. Now I need to prove that for a given prime p, there are infinitely many [itex]n>1[/itex] such that p does not divide [itex]G_n[/itex]. I think I need to show that our given prime p is not in the prime factorization of [itex]G_n[/itex], but I'm not sure how todo this. I could try writing out the function and showing that the power of the prime in the numerator and denominator are equal at some point and that this reoccurs for that prime as n increases, but this seems like a tedious way to go about it and the numbers in the numerator and denominator are not themselves factored into primes, making this difficult to compute for an arbitrary value of the function. Any suggestions?
  5. Oct 16, 2011 #4
    Still looking for help on this one. Another possibility I've considered is the following:

    Let us assume that there are not infinitely many n>1 such that p does not divide [itex]G_n[/itex]. Then there exists some integer n such that p divides [itex]G_n[/itex] and p also divides [itex]G_k[/itex] for all k>n. This implies that p is a factor in the prime factorization of [itex]G_k[/itex] for all k>n. Is there any way to show that this leads to a contradiction?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook