Proving Prime Divisibility with Induction

[Firepanda]

Use the method of induction to prove that if a ∈ Z is a prime
integer and if a/b₁b₂...b_r then a/b_i 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]

Hi Firepanda!

Start "assume it's true for r ≤ n", and then try to prove it for r = n+1.

 

[Firepanda]

ok so..

a/b₁b₂...b_r then a/b_i for some 1 ≤ i ≤ r

assume true for r ≤ n

a/b₁b₂...b_n then a/b_i for some 1 ≤ i ≤ n

if r = n+1

a/b₁b₂...b_nb_n+1 then a/b_i for some 1 ≤ i ≤ n+1

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

Probably wrong

 

[tiny-tim]

No, if a divides a product of n+1 numbers, how can a theorem about products of n numbers be applied?

 

[D H]

Work backwards. There are three cases:

• a|b₁ and a|b₂b₃...b_r (game over), or
• a|b₁ (game over), or
• a|b₂b₃...b_r.

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.

 

[Firepanda]

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|b_n+1, and 1 ≤ i ≤ n+1 so this holds true?

^ sorry this is wrong gcd(a,b) isn't 1 its b_i

im stumped

 

[D H]

There are three cases:

• a|b₁ and a|b₂b₃...b_r (game over), or
• a|b₁ (game over), or
• a|b₂b₃...b_r.

Conceptually, there are four cases:

1. a divides b₁ and b₂b₃...b_r.
2. a divides b₁ but not b₂b₃...b_r.
3. a divides b₂b₃...b_r but not b₁
4. a divides neither b₁ nor b₂b₃...b_r.

You need to show that these are the only four cases, and that case (4) does not apply.

 

[tiny-tim]

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|bb_n+1 where b = b₁…b_n

 

[D H]

So what is the base case? You do not know that a|b₁.

You have proved that if a|b₂b₃...b_r then a|b₂b₃...b_rb_r+1. The OP needs to prove the converse (assuming a does not divide b_r+1; it's game over if a|b_r+1).

 

[tiny-tim]

No, if a|bb_n+1, then …

 

[Firepanda]

No, if a|bb_n+1, then …

go on... want to see how you've done it!

 

[tiny-tim]

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

 

[Firepanda]

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

a|b or a|b_n+1?

 

[tiny-tim]

That's right.

Now carry on …​

 

[Firepanda]

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]

"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|b_i, you haven't been given an i)

 

[Firepanda]

"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|b_i, 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