Help with 2 Number Theory Problems

[SomeRandomGuy]

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.

 

[AKG]

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 F_n and F_m, then if we let F_n = xp and F_m = 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 canceled 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.

 

[SomeRandomGuy]

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.