Explore BrainMass

Mathematical Induction with Prime Numbers and Integers

I need help proving the following 3 problems :

Problem 1: Prove by induction that if a prime number p divides the product then p must divide at least one of the factors, aj for some j=1...n

Problem 2: Prove by induction that if gcd(a,b)=1 then gcd(a,b^n)=1 for any positive integer n

Problem 3: Use problem 2 to prove that if gcd(a,b)=1 then gcd(a^m,b^n)=1 for any positive integers m and n

*** Must solve them using the induction method

Solution Preview

Problem 1:
(a) First case: for n = 1: if p divides a_1 then it divides a_1
(b) Hypothesis: assume statement holds for n = k
(c) Induction: given Hypothesis prove for n = k+1:
If p divides a_{k+1} then the statement is true.
If p does not divide a_{k+1} then it must divide a_1a_2....a_k and then, by Hypothesis, it must ...

Solution Summary

Proofs by mathematical induction are provided. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.