Help with 2 Number Theory Problems

In summary, the conversation discusses two problems in number theory and the need for hints or help in solving them. The first problem involves proving that a certain expression is an integer using induction, finding a contradiction if there is a common prime in the factorizations of two numbers, and proving the existence of a certain number of distinct primes. The second problem involves proving that a prime number divides a binomial coefficient. The conversation also mentions the need for practice and improvement in writing proofs.
  • #1
SomeRandomGuy
55
0
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.
 
Physics news on Phys.org
  • #2
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 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.
 
  • #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:

1. What is Number Theory?

Number Theory is a branch of mathematics that deals with the properties and relationships of numbers, including integers, rational numbers, and real numbers. It also studies patterns and structures within numbers and has applications in cryptography, computer science, and other fields.

2. What are some common topics in Number Theory?

Some common topics in Number Theory include prime numbers, divisibility, modular arithmetic, Diophantine equations, and the distribution of primes.

3. What are some practical applications of Number Theory?

Number Theory has many practical applications, including in cryptography for securing communications and data, in coding theory for error-correction in data transmission, and in computer science for algorithms and data structures.

4. How does Number Theory relate to other branches of mathematics?

Number Theory has connections to many other branches of mathematics, including algebra, geometry, and analysis. It also has applications in other fields such as physics, engineering, and economics.

5. How can I improve my skills in Number Theory?

To improve your skills in Number Theory, it is important to have a strong foundation in algebra and basic mathematical concepts. You can also practice solving problems and studying theorems and proofs in Number Theory. Online resources, textbooks, and attending seminars or workshops can also help improve your knowledge and skills in this field.

Similar threads

  • Introductory Physics Homework Help
Replies
18
Views
1K
Replies
41
Views
2K
  • Introductory Physics Homework Help
Replies
4
Views
792
  • Introductory Physics Homework Help
Replies
2
Views
662
  • Precalculus Mathematics Homework Help
Replies
3
Views
897
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
  • Introductory Physics Homework Help
Replies
12
Views
684
  • Introductory Physics Homework Help
Replies
4
Views
1K
Replies
11
Views
294
  • Introductory Physics Homework Help
Replies
6
Views
742
Back
Top