Composite numbers and divisibility (2 problems)

[Hannisch]

First of all, I hope this problem is supposed to be here - I'm Swedish and in Sweden "calculus" & "precalculus" are rather odd terms. Anyway..


1. The problem statement, all variables and given/known data
Prove that n3 - n is divisible by 6 if n is a natural number, and divisible by 24 if n is an odd natural number.


2. Relevant equations



3. The attempt at a solution
There were two problems similar to this before this one and I attempted to solve it in the way I solved those (and the way the book solved them, as well), which was to split n into its even case and odd case.

Even case:

n = 2k

(2k)3 - 2k = 8k3 - 2k , which obviously didn't help me much. But, as I'd used earlier for previous exercises, k can either be even or odd. If k is, say, even, k = 2s

8(2s)3 - 2(2s) = 64s3 - 4s .. and I can continue on, but nothing is divisible by 6..

And I've done the same for k = 2s + 1, which also doesn't work out. And I tried the odd case I mentioned earlier (n=2k +1) and that doesn't work out and I'm so close to screaming in frustration it's not even funny..






1. The problem statement, all variables and given/known data
Show that if n is a composite number it has a divisor greater than or equal to n½.

2. Relevant equations


3. The attempt at a solution
My problem is that, yes, I absolutely and completely agree with the statement due to logic, but I've not a clue where to start the proof.. I'm not asking for someone to show me the proof, but a tip as to where to start?

[rock.freak667]

Try proof by induction

assume true for n=k

Hk: k3-k=6A (A= integer)

so Hk+1=(k+1)3-(k+1)

expand and see if you can use k3-k=6A to show that Hk+1 is 6*something.

[Hannisch]

I wanted to use mathematical induction, but we're not supposed to have learnt it yet (I just started a course at university, and we did induction at my previous school).

And so, I tried MI, with the result: 6A + 3k2 + 3k .. divisible by 3, but not by 6.

This problem is behaving very strangely, because at the same time I can plug in numbers and see that it is in fact true x/

[njama]

Make a substitution k=k3-6A, and see what you will come up with. :smile:

6A+3(k3-6A)2+3(k3-6A) ?

[mathie.girl]

For the divisible by six, did you try just factoring the expression? Then your subbing in trick (2k+1) will work for the second half.

For your second proof (that a composite number has a factor greater than \sqrt{n}, did you try contradiction?

[VietDao29]

First of all, I hope this problem is supposed to be here - I'm Swedish and in Sweden "calculus" & "precalculus" are rather odd terms. Anyway..


1. The problem statement, all variables and given/known data
Prove that n3 - n is divisible by 6 if n is a natural number, and divisible by 24 if n is an odd natural number.


2. Relevant equations



3. The attempt at a solution
There were two problems similar to this before this one and I attempted to solve it in the way I solved those (and the way the book solved them, as well), which was to split n into its even case and odd case.

Even case:

n = 2k

(2k)3 - 2k = 8k3 - 2k , which obviously didn't help me much. But, as I'd used earlier for previous exercises, k can either be even or odd. If k is, say, even, k = 2s

8(2s)3 - 2(2s) = 64s3 - 4s .. and I can continue on, but nothing is divisible by 6..

Well, as pointed out by rock.freak667 in some earlier post, Proof of Induction can be used here.

But, if you really want to solve the problem by splitting up into 2 cases, where n is even, and n is odd, you can try to factor. Like this:

Even case:

n = 2k

(2k)3 - 2k = 8k3 - 2k

Notice that the final expression is already divisible by 2, so what's left is to prove that the rest is divisible by 3. And it's done. So,

(2k)3 - 2k = 8k3 - 2k
= 2(4k3 - k)
= 2k(4k2 - 1)
= 2k(2k - 1)(2k + 1)

Look at the final expression, can you see why it's divisible by 6?

Hint:
- Is it divisible by 2? Why?
- Is it divisible by 3? And why?

---------------------------

And for the case where n is odd, you can tackle it in pretty much the same manner. Let's see if you still get suck. :)

---------------------------

1. The problem statement, all variables and given/known data
Show that if n is a composite number it has a divisor greater than or equal to n½.

2. Relevant equations


3. The attempt at a solution
My problem is that, yes, I absolutely and completely agree with the statement due to logic, but I've not a clue where to start the proof.. I'm not asking for someone to show me the proof, but a tip as to where to start?

If n is a composite number, then there must exists some number a, and b, such that: n = ab, right? :)

Now, let's do a little bit thinking, can both a, and b be less than n½?

[HallsofIvy]

I wouldn't use induction.

n^3- n= n(n^2- 1)= (n-1)n(n+1), the product of three consecutive numbers. You should show that, of any three consecutive numbers, at least one must be even and at least one must be a multiple of 3 so their product is a multiple of 6.

If n is odd, then both n-1 and n+1 are even. Further, of two consecutive even numbers, 2k and 2k+2, one is a multiple of 4. (Look at the cases where k is even or odd.)

[Hannisch]

Thanks for that last thing, that's exactly what I needed! :)

And no, both a and b can't be less than n½, because there's no way it could become n. The thing is, I fully understand the logic, that either it's n½ * n½ or a>n½ * b<n½ (or the other way around, obviously).. but I can't get how to put it in mathematical language ..

[VietDao29]

Thanks for that last thing, that's exactly what I needed! :)

And no, both a and b can't be less than n½, because there's no way it could become n. The thing is, I fully understand the logic, that either it's n½ * n½ or a>n½ * b<n½ (or the other way around, obviously).. but I can't get how to put it in mathematical language ..

Ok, that's what we call Proof By Contradiction (http://en.wikipedia.org/wiki/Proof_by_contradiction), i.e, you are asked to prove some statement P. Now, you assume that you don't have P (i.e, P is false), and from there, try to find the contradiction.

So, start from assuming that: "that composite number has a divisor greater than or equal to n½" is a false statement. Can you write out the negation of that statement? And then, what happens?

[Hannisch]

Oh yeah, I'd completely forgotten Proof by Contradicton.. hum. We never focused on it much.

Anyway, I'd say something like:

n=ab, a<n½, b<n½

so, n < n½ * n½, but since it's the same base, n½ * n½ should be n1, and there's our contradiction.

That's at least how I remember proof by contradiction..