Purchase Solution

Mathematical Induction with Prime Numbers and Integers

Not what you're looking for?

Ask Custom Question

I need help proving the following 3 problems :

Problem 1: Prove by induction that if a prime number p divides the product a1a2....an 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

Purchase this Solution
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.

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 ...

Purchase this Solution
Free BrainMass Quizzes
Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Probability Quiz

Some questions on probability

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

View More Free Quizzes
Related BrainMass Solutions

  • Use mathematical induction to prove...

    For integers n>= 1 and for all real numbers x>=-1, use mathematical induction to prove that 1 + nx =< (1 + x)^n. We first consider the case of n=1: (1+x)<=(1+x) That is obviously true.

  • Summation and series

    (Required) Without using Theorem 4.2.2, use mathematical induction to prove that P(n): 1 + 5 + 9 + ... + (4n  3) = n(2n  1) for all integers n  1 Prove the statements in #9-12 by mathematical induction. 9.

  • Abstract Algebra : mathematical induction

    147415 Abstract Algebra : Mathematical Induction Prove the following statement Given the recursively defined sequence a_1= 0, a_2= -30, and a_n=8a_n-1 -15a_n-2, use complete induction to prove that a_n=5*3^n - 3*5^n for all positive integers n.

  • Discrete Math: Logic

    T F The Fibonacci Sequence is {sn | sn = sn1 + sn2, with s0 = 1 and s1 = 1}. T F The First (Weak) and Second (Strong) Principles of Mathematical Induction are logically equivalent.

  • Mathematical induction: Flaws and Inductive Proofs

    So the mathematical induction is not correct. Flaws and inductive proofs for two mathematical induction problems are provided in the solution.

  • Proofs, Diophantine equations, and sequences

    Hence, by mathematical induction it is true , for all n. 4- A sequence x1, x2, x3, ......of real numbers is defined by x1=1 and xn+1 = , if n Prove that xn = for all positive integers n.

  • Discrete math proofs

    Using induction hypothesis, divides . Hence divides i.e. So, we proved that for each odd integer 2) Prove that 5n+3 is divisible by 4 for all integers n>=0 We also prove this again by using Mathematical induction.

  • Mathematical induction

    220437 Example of a Mathematical Induction Proof Show by mathematical induction that 1 + 3 + 3^2 + 3^3 + ... + 3^n = ((3^n+1) - 1) / 2 for all positive integers n.

  • Fibonacci numbers: F 2n+1 - Fn Fn+2 = (-1) n

    Application of Mathematical Induction Application of Mathematical Induction Mathematical Induction :- If a statement is true in the first case and if it is true for all the cases preceding a given

View More Related Solutions