# Proof by induction

Use the method of induction to prove that if a ∈ Z is a prime
integer and if a/b1b2...br then a/bi for some 1 ≤ i ≤ r

I could prove this in other ways but how do you do this by induction?

I'm only use to induction of the form 'assume true for n show (n+1) also holds true'

Could someone start me of? Thanks

tiny-tim
Homework Helper
Hi Firepanda! Start "assume it's true for r ≤ n", and then try to prove it for r = n+1. ok so..

a/b1b2...br then a/bi for some 1 ≤ i ≤ r

assume true for r ≤ n

a/b1b2...bn then a/bi for some 1 ≤ i ≤ n

if r = n+1

a/b1b2...bnbn+1 then a/bi for some 1 ≤ i ≤ n+1

but since we already had 1 ≤ i ≤ n then surely this is true?

Probably wrong

tiny-tim
Homework Helper
No, if a divides a product of n+1 numbers, how can a theorem about products of n numbers be applied? D H
Staff Emeritus
Work backwards. There are three cases:
• a|b1 and a|b2b3...br (game over), or
• a|b1 (game over), or
• a|b2b3...br.
In the last case, recurse.

I don't think tiny-tim's idea will work because there is no base case to make the stack of dominos fall.

No, if a divides a product of n+1 numbers, how can a theorem about products of n numbers be applied? if a|bc and gcd(a,b) = 1 since a is prime and b certainly isn't as its a product

then a|c, so since a|c then a|bn+1, and 1 ≤ i ≤ n+1 so this holds true?

^ sorry this is wrong gcd(a,b) isnt 1 its bi

im stumped

D H
Staff Emeritus
There are three cases:
• a|b1 and a|b2b3...br (game over), or
• a|b1 (game over), or
• a|b2b3...br.

Conceptually, there are four cases:
1. a divides b1 and b2b3...br.
2. a divides b1 but not b2b3...br.
3. a divides b2b3...br but not b1
4. a divides neither b1 nor b2b3...br.
You need to show that these are the only four cases, and that case (4) does not apply.

tiny-tim
Homework Helper
I don't think tiny-tim's idea will work because there is no base case to make the stack of dominos fall.

I was thinking of saying a|bbn+1 where b = b1…bn D H
Staff Emeritus
So what is the base case? You do not know that a|b1.

You have proved that if a|b2b3...br then a|b2b3...brbr+1. The OP needs to prove the converse (assuming a does not divide br+1; it's game over if a|br+1).

tiny-tim
Homework Helper
No, if a|bbn+1, then … No, if a|bbn+1, then … go on... wanna see how you've done it!

tiny-tim
Homework Helper
Apply the induction … a divides the product of two numbers, so … ?

Apply the induction … a divides the product of two numbers, so … ?

a|b or a|bn+1?

tiny-tim
Homework Helper
That's right. Now carry on …​

That's right. Now carry on …​

dont we just conclude that i is certainly contained between 1 and n+1 inclusive so the induction hypothesis is true?

tiny-tim
Homework Helper
"i is certainly contained …"

That's meaningless!

What are you talking about? What is i?

(You're trying to find an i ≤ 1+1 such that a|bi, you haven't been given an i)

"i is certainly contained …"

That's meaningless!

What are you talking about? What is i?

(You're trying to find an i ≤ 1+1 such that a|bi, you haven't been given an i)

but we assumed it was true?

ok then but we've shown a must divide one of the terms so a can divide at least one of the i ≤ n+1