1. Not finding help here? Sign up for a free 30min 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!

Help with 2 Number Theory Problems

  1. Sep 15, 2005 #1
    Hey guys, I have a homework assignment for number theory and two of the problems I don't know how do solve. I was hoping I could get some hints or help. Thanks

    Problem 1
    Let m,n be elements of the natural numbers where n > m.
    and F_n = 2^2^n + 1

    a.) Show that (F_n - 2)/F_m is an integer.
    b.) Assume that there is a prime p in the factorization of both F_n,F_m. Show this leads to a contradiction.
    c.) Now there must be atleast n distinct primes. Now let n -> infinity. Write out the proof in detail.

    Problem 2
    Let p be a prime and let n be any integer satisfying 1 <= n <= p-1. Prove that p divides the binomial coefficient p!/(p-n)!n!

    For this, I said if p divides it, then p*a = it where a is some integer. I then get a term that reduces down to a = (p-1)!/(p-n)!n! and don't know where to do from here.

    I'm not looking for solutions, although if it's needed for me to understand that's fine. I am just hoping to get pointed in the right direction. Thanks.
  2. jcsd
  3. Sep 15, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    1.a) I would suggest solving by induction on n-m = i. Proving it for the base case (i = 1) is a simple matter of factoring a difference of squares. I assume that the inductive step should not be too hard to prove.
    b) If there is a common prime p in the factorizations of Fn and Fm, then if we let Fn = xp and Fm = yp, then from part a we get:

    (xp - 2)/(yp) = k for some integer k

    Show that this leads to a contradiction.

    c) This shouldn't be too hard. Proceed by induction on n.

    2. This again is very easy. If p doesn't divide the binomial coefficient, then the p in the numerator must be cancelled by some p in the denominator. If p is in the denominator, then since p is prime, it must be in (p - n)! or in n! or both (that is, since p is not composite, it is not equal to a*b where we would just need a to be in (p - n)! and b to be in n! or something like that, without all of p being in one of those factorials). You should be able to see very easily that p is a factor of neither factorial, since each factorial is just a product of numbers less than p.
  4. Sep 15, 2005 #3
    For question 2, I actually had something written like that. Not as clear as what you said, but I pretty much meant the same thing. As for part 1, thanks for the help. Induction didn't even occur to me.

    This is also my first proof writing course ever... So seeing how obvious certain proofs are is like a different language to me as of now. I'm sure I will get better with practice.
    Last edited: Sep 15, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Help with 2 Number Theory Problems
  1. Help on 2 problems (Replies: 1)