If k = 2n - 1, where n is an integer, what is the remainder

Question

If k = 2n - 1, where n is an integer, what is the remainder of  \frac{k^2}{8} ?

A. 1
B. 3
C. 5
D. 7
E. Cannot be determined from the information given.

Bunuel · Accepted Answer

This one can be done very easily with number picking. As you correctly noted  k = 2n - 1  means that k is an odd number (basically  k = 2n - 1  is a formula of an odd number).

Now let's try several odd numbers:
k=1 --> k^2=1 ---> remainder upon division of 1 by 8 is 1;
k=3 --> k^2=3 ---> remainder upon division of 9 by 8 is 1;
k=5 --> k^2=25 ---> remainder upon division of 25 by 8 is 1;

At this point we can safely assume that this will continue for all odd numbers.

But if you want algebraic approach, here you go:
 k = 2n - 1  -->  k^2=(2n-1)^2=4n^2-4n+1=4n(n-1)+1  --> what is a remainder when  4n(n-1)+1  is divided by 8:

Now either  n  or  n-1  will be even so in any case  4n(n-1)=4*odd*even=multiple \ of \ 8 , so  4n(n-1)  is divisible by 8, so  4n(n-1)+1  divided by 8 gives remainder of 1.

Answer: A.

Hope it's clear.

jpr200012 · Answer

My initial thoughts were:
1)  k = 2n -1 , so  k  must be odd
2) For  k^2  to be divisible by 8,  k^2  must contain at least 3 2's. Therefore, each k must contain 2 2's.

I'm not sure how to continue using my initial thoughts.

The official answer shows:
i) Express  k^2 = (2n-1)^2 = 4n^2 - 4n + 1

ii) Factor to  k = 4n(n-1)+1

Step ii doesn't make sense to me. If you factor out  4n  on the right side, why would the left not still be  k^2 ? If this is just a misprint, then the the next step makes sense to me.

iii) 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 * even * odd, plus 1. In other words,  k  will equal a multiple of 8, plus 1. Therefore, the remainder of  k^2/8  is 1.

jpr200012 · Answer

I think picking a number is a lot easier on this one.

utin · Answer

Hi Bunuel,

How come 1 div by 8 gives remainder as 1???

utin.

whiplash2411 · Answer

I don't think he meant that 1 is divisible by 8. I think he was referring to the term before: 4(n)(n-1)

Either n or n-1 must be even so we have odd*even*4 which gives you 8*number, so we have this term divisible by 8.

Let us assume that k = 4(n)(n-1)

This is divisible by 8.

So k+1 when divided by 8 will give reminder 1.

For example, consider n = 2

We have 4*2*1 + 1 = 9

When we divide this by 8 we get reminder 1. And so on. Hope this explains.

Bunuel · Answer

THEORY: 
Positive integer  a  divided by positive integer  d  yields a reminder of  r  can always be expressed as  a=qd+r , where  q  is called a quotient and  r  is called a remainder, note here that  0\leq{r}<d  (remainder is non-negative integer and always less than divisor).

So when divisor (8 in our case) is more than dividend (1 in our case) then the reminder equals to the dividend:

1 divided by 8 yields a reminder of 1 -->  1=0*8+1 ;
or:

5 divided by 6 yields a reminder of 5 -->  5=0*6+5 .

Eden · Answer

Agree, but good to know that a square of odd number gives 1 when divided by 8.

TGC · Answer

K=2n-1

K^2 = 4n^2 +1 - 4n

Dividing both sides by '8'.

=> K^2/8 = 4(n^2-n)/8 +1/8

=> n(n-1)/2 + 1/8

In both cases whether 'n' is EVEN or ODD n(n-1) is divisible by '2'.

Hence,

Remainder is = 1/8 = 1

Asifpirlo · Answer

......
Finally after 3lines calculation,
n(n-1)/2 + 1/8

so remainder = 1

stonecold · Answer

Here K^2= (2n-1)^2 = 4n^2-4n+1=> 4n(n-1)+1
Now using the property -> " The product of n consecutive integers is always divisible by n!
=> K^2= 4*2p +1 => 8p+1 for some integer p
hence remainder with 8 must be 1

Hence A

gmatdordie · Answer

Pick any number for n=1, 2, 3, or 4

Lets say n=2
so k-4-1=3

so remainder for 9/8=1

correct OA:A

dave13 · Answer

From the given expression it can be clearly seen that K is an ODD number. let K be 7 then 7= 2*4 - 1 \frac{7^2}{8} yields remainder 1 let K be 9 then 10= 2*5 - 1 \frac{9^2}{8} yields remainder 1 A

Mansoor50 · Answer

Can we also do the following:

k^2/8 = (2n-1)^2/8 = (4n^2 +1 - 4n)/8

the individual remainders of each term are: 4, 1, -4 and we add these up, we 1.

bumpbot · Answer

Hello from the GMAT Club BumpBot!

Thanks to another GMAT Club member, I have just discovered this valuable topic, yet it had no discussion for over a year. I am now bumping it up - doing my job. I think you may find it valuable (esp those replies with Kudos).

Want to see all other topics I dig out? Follow me (click follow button on profile). You will receive a summary of all topics I bump in your profile area as well as via email.

If k = 2n - 1, where n is an integer, what is the remainder

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

If k = 2n - 1, where n is an integer, what is the remainder

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards