What is the remainder obtained when 63^25 is divided by 16?

Question

What is the remainder obtained when  63^{25}  is divided by 16?

A. -1
B. 0
C. 5
D. 10
E. 15

gmatophobia · Accepted Answer

Remainder  (\frac{63^{25}}{16} )

⇒ Remainder  (\frac{63}{16})^{25}

⇒  (-1)^{25}

⇒ -1

As remainders cannot be negative, the net remainder = 16 - 1 = 15

Option E

BrushMyQuant · Answer

↧↧↧ Detailed Video Solution to the Problem ↧↧↧

https://www.youtube.com/watch?v=35AJStlaPec

What is the remainder obtained when  63^{25}  is divided by 16?

To solve this problem we will be using a concept called as  Binomial Theorem 
Learn more about Binomial Theorem  in this video .

Now, we need to break 63 into two number
 
 One number should be a multiple of 16 and should be close to 63 (i.e. 64) 
 Other number should be a small number to make the sum or difference as 63 (i.e. -1)  
=> Remainder of  63^{25}  by 16 = Remainder of  (64-1)^{25}  by 16

"The reason we are doing this is because when we open  (64-1)^{25}  this using Binomial Theorem then we will get all the terms except one term as a multiple of 64 (which also makes them a multiple of 16."
=> Remainder of all the terms by 16, except one term will be 0

Let's open  (64-1)^{25}  using Binomial Theorem to understand this

(64-1)^{25}  =  ^{25}C_0 * 64^{25} * (-1)^0 + ^{25}C_1 * 64^{24} * (-1)^1 + .... + ^{25}C_{24} * 64^{1} * (-1)^{24} + ^{25}C_{25} * 64^{0} * (-1)^{25}

=> All terms except the last term are multiples of 64 => Their remainder by 16 will be 0

=> Our problem is reduced to what is the remainder when  ^{25}C_{25} * 64^{0} * (-1)^{25}  is divided by 16

^{25}C_{25} * 64^{0} * (-1)^{25}  = 1 * 1 * -1 = -1
=> Reminder of -1 by 16 = -1 + 16 = 15

So,  Answer will be E 
Hope it helps!

MASTER Remainders with 2, 3, 5, 9, 10 and Binomial Theorem

https://www.youtube.com/watch?v=h1HTEhmUb1w

ymer · Answer

With binomial theorem remainder:
63^26 = (3x16 + 15)^26 --> REMAINDER --> 15^26 = (16 - 1)^26 --> REMAINDER --> (-1)^25 = -1
(when is negative we have to add to the divisor)
REMAINDER --> 16 + (-1) = 15
ANS : E

SaquibHGMATWhiz · Answer

Solution:

We are asked the value of  (\frac{63^{25}}{16})_R  
 If we ignore the power 25 and find  (\frac{63}{16})_R=15  
 So, we can write  (\frac{63^{25}}{16})_R=(\frac{15^{25}}{16})_R 
 ⇒(\frac{(15^2)^{12}	imes 15}{16})_R 
 ⇒(\frac{(15^2)^{12}}{16})_R	imes (\frac{15}{16})_R 
 ⇒1^{12}	imes 15  (because  (15^2/16)_R=1  and 15 is less than 16 so  (15/16)_R=15 )
 ⇒15

Hence the right answer is    Option E

Sujithz001 · Answer

Bunuel   KarishmaB

Is there any way we can solve this without Binomial theorem?

Thanks!

BrushMyQuant · Answer

Other way of solving remainder problems it to find cyclicity, but that will be lengthier. Example below:

Remainder of power of 63 by 1

Remainder of  63^{1}  by 16 = 15 ( or -1 + 16 = 15)
Remainder of  63^{2}  by 16 = Remainder of 63 by 16 * Remainder of 63 by 16 = Remainder of -1 * -1 by 16 = Remainder of 1 by 16 = 1
Remainder of  63^{3}  by 16 = Remainder of  63^2  by 16 * Remainder of 63 by 16 = 1 * 15 = 15

Two ways from here
  Method 1:   
So, Cycle is 2
=> Remainder of Odd power of 63 by 16 = 15
=> Remainder of Even power of 63 by 16 = 1

=> Remainder of  63^{25}  by 16 = 15 (odd power)

Method 2:   
Other way to Solve,

63^{25}  =  63 * 63^{24}  =  63 * (63^2)^{12}

=> Remainder of  63^{25}  by 16 = Remainder of  63 * (63^2)^{12}  = Remainder of 63 by 16 * Remainder of  (63^2)^{12}  by 16 = 15 * 1 = 15

So,  Answer will be E 
Hope it helps!

What is the remainder obtained when 63^25 is divided by 16?

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

What is the remainder obtained when 63^25 is divided by 16?

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