You are Here: Home >< Maths

# Proof By Induction for Divisibility Help Needed

1. (Original post by Matureb)
No. In this case 30 is divisible by 2 and by 6. But not by 18. For 18 you would need to show it was divisible by 2 and 9.
Ugh I am confused over tiny technical details..
So to prove something is divisible by 30, it would be 15 and 2 ?
for 18 - 2 and 9
for x - any two factors which multiply to give x ?

Or is it that one of the factors must always be 2 ?
eg to prove something is divisible by 60 can I use 10 and 6 or must I use 2 and 30, or will 4 and 15 also work ?
2. (Original post by member910132)
Oh, can we say that at least one of those numbers must be even and so the whole thing can be divided by 2 and so the whole number is even.

But can someone clarify this issue of using factors to prove something is divisible by a number ?
If I wanted to prove something is divisible by x, then obviously proving it is divisible by Ax would suffice right ? (where A is a constant integer).

But if I am to prove that something is divisible by 12 for example then must I say that it is divisible by 2 of it's factors, eg show that it is divisible by both 3 and 4 or 2 and 6 ?

Thnx tons
In general if you want to prove x is divisible by y then you have to show x is divisible by each of the prime factors of y.
3. (Original post by miml)
In general if you want to prove x is divisible by y then you have to show x is divisible by each of the prime factors of y.
Tank you so much for this !!!!!!!!!!
4. 60 = 2*2*3*5. To test if a nunber is divisible by 60 it must be divisible by (2*2), by 3 and by 5. I.e it must be divisible by 3, 4 and 5. Note, these are relatively prime.
You are right that 4 and 15 will do since if it is divisible by 15, then it is automatically divisible by 3 and 5.
10 and 6 would not do. 90 is divisible by 10 and 6 , but not by 60.
5. Surely it would be easier to say

1) when n=k
assume n^3-n is divisible by 6

2) when n=k+1
n^3+3n^2+2n

1)x4 + 2)x2 gives 4n^3-4n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
......................(divisible by 6).............................. .................(divisible by 6)

As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2).
6. (Original post by Matureb)
60 = 2*2*3*5. To test if a nunber is divisible by 60 it must be divisible by (2*2), by 3 and by 5. I.e it must be divisible by 3, 4 and 5. Note, these are relatively prime.
You are right that 4 and 15 will do since if it is divisible by 15, then it is automatically divisible by 3 and 5.
10 and 6 would not do. 90 is divisible by 10 and 6 , but not by 60.
Got it, great ! So I just need to shwo that it is divisible by it's prime factors or the prime factors multiplied by each other (in the example of 2.2.3.5 = 4.15)

(Original post by Quip)
Surely it would be easier to say

1) when n=k
assume n^3-n is divisible by 6

2) when n=k+1
n^3+3n^2+2n

1)x4 + 2)x2 gives 4n^3-4n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
......................(divisible by 6).............................. .................(divisible by 6)

As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2).
Sorry I can't follow what you have done at all, but it is okay, I get it now. And I realize that their are other ways of doing it but I wanted to know how to do it in a specific way.
7. (Original post by Quip)
Surely it would be easier to say

1) when n=k
assume n^3-n is divisible by 6

2) when n=k+1
n^3+3n^2+2n

1)x4 + 2)x2 gives 4n^3-4n + 2n^3+6n^2+4n = 6n^3+6n^2 = 6(n^3+n^2)
......................(divisible by 6).............................. .................(divisible by 6)

As the two bits I've shown are divisible by 6, the 6n^2+4n must be divisible by 6 and so is the equation in 2).
Might be missing something, but your argument only shows that the "equation 2" is divisible by 2?

Surely you want 2n^3 + 6n^2 + 4n to be divisible by 12, to show that our original expression is divisible by 6.
8. (Original post by miml)
Might be missing something, but your argument only shows that the "equation 2" is divisible by 2?

Surely you want 2n^3 + 6n^2 + 4n to be divisible by 12, to show that our original expression is divisible by 6.
I thought that because it equals something that is divisible by 6 and equation 1 is divisible by 6 (assumed), the 2n^3 + 6n^2 + 4n must also be divisible by 6. (If two things are added which are both divisible by 6, the sum will also be divisible by 6)

However, I've just realised that as I've already multiplied it by 2, this only shows that n^3 + 3n^2 + 2n is divisible by 3 and you're right I need to show 2n^3 + 6n^2 + 4n is divisible by 12. Sorry, my mistake (I've been on holiday too long and forgotten how to do maths)
9. there are different cases to consider:

firstly, n^3-n can be expressed as: n(n-1)(n+1)

so, first, if n is divisible by 3, then n-1 is divisible by2, so whole thing divisible by 6 - nothing further needed there.

second thing you do is examine what happens when n is both odd and even: odd n=2k+1 for some k in Z - you find out, by factoring, that both expressions are divisible by 2,

3rd, you examine n when it`s NOT divisible by 3 - by using in the expression, (then factoring it) both n=3k+1, and n=3k-1 (this ensures thatyou encompass every number NOT divisible by 3) - you find that the expression n^3-1 when used with these values, simplifies to something with a factor of 3,

so you will have proved simultaneously that the expression has factors of both 2 and 3...
10. (Original post by Hasufel)
there are different cases to consider:

firstly, n^3-n can be expressed as: n(n-1)(n+1)

so, first, if n is divisible by 3, then n-1 is divisible by2, so whole thing divisible by 6 - nothing further needed there.

second thing you do is examine what happens when n is both odd and even: odd n=2k+1 for some k in Z - you find out, by factoring, that both expressions are divisible by 2,

3rd, you examine n when it`s NOT divisible by 3 - by using in the expression, (then factoring it) both n=3k+1, and n=3k-1 (this ensures thatyou encompass every number NOT divisible by 3) - you find that the expression n^3-1 when used with these values, simplifies to something with a factor of 3,

so you will have proved simultaneously that the expression has factors of both 2 and 3...
Problem with this is proof was asked to be done by induction.

To prove by induction that a number is divisible by some number, the difference between k and k+1 must be used. Otherwise its just a direct proof.

(Original post by BJack)
.
Also a problem with your idea of just showing either number is a multiple of 6 is that it isn't induction. You can do all the induction steps to disguise it as induction, but unless you actually use the assumption that n³ - n is a multiple of 6 then its just a direct proof.
11. How I would have done it, if it had to be done by induction:
Assume true for n=k then is divisible by 6.

For n=k+1

The first bracket is divisible by 6 by our assumption so it remains to show the second bracket is.
Which is clearly divisible by 3, and as it contains a product of two consecutive numbers i.e. one must be even, it is also divisible by 2. Hence divisible by 6 and we have shown that for n=k+1 the expression is divisible by 6.

If it didn't have to be done by induction
Spoiler:
Show
n^3 - n = (n-1)n(n+1) which is the product of 3 consecutive integers, hence is divisible by 3 and 2
12. (Original post by hassi94)
Also a problem with your idea of just showing either number is a multiple of 6 is that it isn't induction. You can do all the induction steps to disguise it as induction, but unless you actually use the assumption that n³ - n is a multiple of 6 then its just a direct proof.
Oh dear.

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
2. this can't be left blank
3. this can't be left blank

6 characters or longer with both numbers and letters is safer

4. this can't be left empty
1. Oops, you need to agree to our Ts&Cs to register

Updated: April 17, 2012
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Today on TSR

### A-level exams coming up?

Find everything you need here.

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams