NP (book 1) - 4th ed. - q2 153

[tcsmith314]

I'm wondering if someone can help me out...

In reviewing the answer provided; I'm not sure I follow the logic...

In the answer on page 155, it states -

"Therefore no matter what integer n is, k will equal 4 x even x odd, plus 1. In other words, k will equal a multiple of 8 plus 1."

I understand everything until the first sentence, but I'm not following how you can lead from the first sentence to the second, where it states "In other words, k will equal a multiple of 8 plus 1."

Here is the complete question, and solution...

Q. If k=2n-1, where n is an integer, what is th3 remainder of (k^2) / 8?

Solution:

Since k=2n-1, we can represent k^2 as:
k^2=(2n-1)^2=4n^2-4n+1
We can factor this expression as follows:
k=4n(n-1)+1

If n is even, then n-1 is odd, while if n is odd, then n-1 is even. Therefore no matter what integer n is, k will equal 4 X even X odd, plus 1. In other words, k will equal a multiple of 8, plus 1. Therefore, the remainder is 1.

NOTE: I've bolded what I don't understand.

[siddharth.sheth]

Hello,

What that statement is trying to say is simply this:
The value of k^2 will be equal to Q + 1, where for the sake of simplicity I have denoted Q as the factor 4n(n-1). As per the solution in the book, you already know, from the logic as presented, that 4n(n-1) is a multiple of 8.
Also note that the solution is not saying that k is equal to a multiple of 9! All it is saying is that k^2 when divided by 8 will always leave a remainder of 1.


for example since we know that Q is a multiple of 8, substituting any multiple of 8 in the equation k^2 = Q + 1
Q = 8, k^2 = 8 + 1 = 9 Remainder when divided by 8 = 1
Q = 16, k^2 = 16 + 1 = 17 Remainder when divided by 8 = 1
Q = 24 k^2 = 24 + 1 = 25 Remainder when divided by 8 = 1

and so on and so forth.

Another way of looking at this situation is to realize that this is the same formula for calculating the remainder:
Number = Quotient* Divisor + Remainder
k^2 = Q*8 + 1

Hopefully that helps. Let me know if this is still not clear and I will try and come up with a clearer explanation.

Cheers :)

[tcsmith314]

thanks this helped...

Given "4n(n-1)" there is nothing within this statement that would indicate it's divisible by 8. Divisible by 4, yes - but nothing to say it is divisible by 8.

So if this question had k^2/4... I'd be all over it, and see 4n(n-1)+1, and see that Q clearly was divisible by 4, therefore R=1. But since the divisor is 8, don't we have to worry about those situations where we have multiples of 4 that are not divisible by 8... i.e. 4, 12, 20, etc.? I still don't see how the answer demonstrates why these situations do not exist.

But, I do see - from testing that this doesn't happen...

n=0, 4(0)(0-1)=0=8*0
n=1, 4(1)(1-1)=0=8*0
n=2, 4(2)(2-1)=8=8*1
n=-5, 4(-5)(-5-1)= -20*-6=120 = 8*15
etc..

But this is a laborious approach... so I'd much rather understand how to conclude this using theory/definitions rather than testing. But - I still can't seem to understand how answer concludes divisibility by 8 without testing.

There seems to be a logic that states, 4n(n-1)+1 is in the form of Q+R. But I must be missing something - to me this seems wrong, since we have to make sure 4n(n-1) is divisible by 8 before we can say this... therefore we are left to prove 4n(n-1) is divisible by 8 before we can jump to saying 4n(n-1)+1 is in the form of Q+R.

[siddharth.sheth]

Hello Again :)

From the solution in the book on pg. 155 it states that k = 4n(n-1)

n, and n-1 are consecutive integers. So if n is even, n-1 is odd, and if n is odd, n-1 is even.
So the product is 4*even*odd or 4*odd*even
now if i break this up it should look something like this

4*(2*integer)*odd or 4*odd*(2*integer)
What i have done is basically used the knowledge that an even number is a multiple of 2 and taken that 2 out. Say 10 for example = 2*5
that integer i have denoted is what is left when you take 2 common, as in the example above would be 5. But we should not worry about what this is since it does not do anything to the divisibility by 8.

So, now hopefully you can see that if you multiply the 4 and the 2 (the one we took out from one of the even numbers) you get 8. Which is clearly divisible by 8.

Hopefully that clears some of it as to why and how it is divisible by 8.

Cheers :)

[tcsmith314]

ok... the fog cleared. LOL. Yes, I see it now. Thanks!

[siddharth.sheth]

You are more than welcome.

Have a great one.

Cheers :)

[Ben Ku]

If n is even, then n-1 is odd, while if n is odd, then n-1 is even. Therefore no matter what integer n is, k will equal 4 X even X odd, plus 1. In other words, k will equal a multiple of 8, plus 1. Therefore, the remainder is 1.

I think "k will equal 4 X even X odd, plus 1" can be simply understood this way. Let's let E be an even number, and D be an odd number.

k = 4 * (E) * (D) + 1

Since E is even, we can express it as 2n (where n is an integer)

k = 4 * 2 * n * D + 1 or 8(nD) + 1

Here we clearly see that this is a multiple of 8 plus 1. Hope that helps.

[stewartmcm]

I realize this thread is long dormant, but I'm still not convinced the answer is 1.

What if n=1? Then wouldn't the answer be "cannot determine"?

1^2/8=1/8, this is a fraction.

Any clarity would be much appreciated.

[jnelson0612]

I realize this thread is long dormant, but I'm still not convinced the answer is 1.

What if n=1? Then wouldn't the answer be "cannot determine"?

1^2/8=1/8, this is a fraction.

Any clarity would be much appreciated.

The remainder is still 1. "1/8" just means 1 divided by 8. 1 divided by 8 is 0 with remainder 1.

Hope this helps!