What is the remainder when 5^16 - 3^16 is divided by 16?

Question

What is the remainder when  5^{16} - 3^{16}  is divided by 16?

A.  0
 B.  1
 C.  3
 D.  5
 E.  7

To read all our articles: Must read articles to reach Q51

https://e-gmat.com/blogs/wp-content/uploads/2018/08/Free-Session-NP-e1533292073470.jpg

KSBGC · Accepted Answer

5^{16} - 3^{16}

5^8*2 - 3^8*2

(5^8 +3^8) (5^8 - 3^8)

now just break down 5^8 - 3^8.

apply  a^2 -b^2.

at least we got : ( 5^8 +3^8) (5^4 +3^4) (5^2 +3^2) ( 5 +3 ) (5-3)

Now divide :

(5^8 +3^8) (5^4 +3^4) (5^2 +3^2) ( 5 +3 ) (5-3) /16.

(5^8 +3^8) (5^4 +3^4) (5^2 +3^2) *8*2 /16.

Reminder is 0.

A is the correct answer.

Archit3110 · Answer

I solved using cyclicity

for any power to 5 we would always get 5 as units digit and for 3 ^ 16 we would get 1 as unit digits

so 5-1= 4 unit digit

16= 2^4

for an even Nr ending with 4 unit digit when divided by 2 would always give remainder as 0 , so IMO A ..

EgmatQuantExpert · Answer

Solution 
  To find:  
We are asked to find out,
 • The remainder when  5^{16} – 3^{16}  is divided by 8

Approach and Working:   
 •  5^{16} – 3^{16}  can be written as  (5^8)^2 – (3^8)^2

We know that,  a^2 – b^2 = (a + b) * (a - b) 
 • Thus,  (5^8)^2 – (3^8)^2 = (5^8 + 3^8) * (5^8 – 3^8) = (5^8 + 3^8) * (5^4 + 3^4) * (5^4 – 3^4)  
 = (5^8 + 3^8) * (5^4 + 3^4) * (5^2 + 3^2) * (5^2 - 3^2) = (5^8 + 3^8) * (5^4 + 3^4) * (5^2 + 3^2) * (5 + 3) * (5 – 3)

• So,  5^{16} – 3^{16} = 16 * (5^8 + 3^8) * (5^4 + 3^4) * (5^2 + 3^2) * (5^2 - 3^2)  
 
If you observe carefully, the above expression is a multiple of 8
 • Therefore, the remainder will be 0 
 
Hence the correct answer is Option A.

Answer: A

https://e-gmat.com/blogs/wp-content/uploads/2018/08/Free-Session-NP-e1533292073470.jpg

rnnamrata · Answer

(5-3)^16/16= (2)^16/2^4.
The remainder is zero.

=== Please suggest if we can solve like this

suchita2409 · Answer

I dont think we can.
its against the rules of indices

Posted from my mobile device

ManjariMishra · Answer

5^16-3^16

25^8 - 9^8

((16+9)^8 - 9^8)/16

Remiander

(9^8 - 9^8)/16

0

Posted from my mobile device

EgmatQuantExpert · Answer

Hey  suchita2409 ,
I am afraid you can not solve it like that.

But, I have an alternate solution. I think you might prefer to solve the question from that method.

In this method, we are using the formula a^2 -b^2 = (a-b)(a+b)

5^16- 3^16 = (5^8- 3^8 )( 5^8 + 3^8) 
= (5^4 - 3^4)(5^4 + 3^4)(5^8 + 3^8)
= (5^2 - 3^2)(5^2 + 3^2)(5^4 + 3^4)(5^8 + 3^8)

Now, (5^2 - 3^2) = 25 - 9 = 16
 And, 16 is a multiple of 8.
S0, 5^16 - 3^16 is also a multiple of 8.

Hence, 5^16- 3^16 is divisible by 8. Thus, the remainder is 0.

chakrads · Answer

Am I correct in solving the problem as below? And can this strategy be applied to similar problems??

5^2-3^2= 16; This divided by 16 -rem=0
5^4-3^4= 544; This divided by 16 -rem=0

so for all even powers of this expression, the remainder is 0 and hence for 5^16-3^16. Remainder =0.

arvind910619 · Answer

Hi  egmat ,

Can this problem be solved without using the identity. 
(5^16 - 3^16) / 8 = ( 5^16/8 ) - ( 3^16/8 )
Now we make use of cyclic pattern and compute remainder.

5/8 = remainder is always 5 
3/8 = remainder is 1 as pattern repeats after 2
So remainder is = 5-1=4 
This will be divisible by 8 as 4 ^16 hence the remainder is 0

Please comment on the approach whether it is correct or not

gurmukh · Answer

(5^2)^8-(3^2)^8
=(25)^8- (9)^8
=(25-9)× integer
 =16× integer
Reminder 0

Posted from my mobile device

philipssonicare · Answer

5=8(1)+5
25=8(3)+1
Both only contain 5 as prime factor yet have different remainders when divided by 8 (think this cyclicity continues 125=8(15)+5; 625=8(78)+1)

A side note for others, a^b isn't necessarily divisible by b
e.g. 4^3=64, 64=3(21)+1

mmaganinhoo · Answer

Ciclicity tells us that the units digit of the subtraction will be 5-1=4.
Hence, the remainder must be even.
Answer (A).

CEO2021 · Answer

5^16 is always odd
3^16 is always odd
it means 5^16- 3^16 is always even---( x )
 IQ part: 
 if a even number (16) will divide any even number (from ( x )) then how the remainder is any ODD number

Looking into choices , ANS must be (a) 0 ie Even number.

Ans A

mcrea · Answer

My way:

Notice that:

(5^1 - 3^1) / 16 gives you a remainder of 2
(5^2 - 3^2) / 16 gives you a remainder of 0
(5^3 - 3^3) / 16 gives you a remainder of 2

So remainder patterns repeats every 2 --> i.e., 2, 0, 2, 0, ...
since exponent 16 is even, then the remainder when (5^16 - 3^16) / 16 is equal to 0

amitarya · Answer

I solved it using remainder cyclicity:

==> 5^16/16

In this remainder cyclicity is as below
5/16 = Remainder 5
5^2/16 = Remainder 9
5^3/16 = Remainder 13
5^4/16 = Remainder of 5^3/16 * Remainder of 5/16 = remainder of (13*5) = Remainder is 1
5^5/6 = Remainder of 5^4/16 * Remainder of 5/16 = remainder of (1*5) = Remainder is 5

Therefore, cyclicity is 5,9,13,1 
 ===> Remainder of 5^16/16 = remainder of 5^4th Power = 1

Similarly cyclicity of exponent of 3 divided by 16 is 3, 9, 11, 1 
 ===> Remainder of 5^16/16 = remainder of 3^4th Power = 1

Therefore, remainder of (5^16 - 3^16)/16
  = remainder of (5^16/16 - 3^16/16) 
 = 1-1
  =0

Is this cyclicity method correct @Buneul

Krunaal · Answer

The cyclicity you found is correct, however the above highlighted part is incorrect, incorrect sign and then multiplication.

=>  \frac{5^{16} - 3^{16}}{16}

=>  \frac{5^{16}}{16}  -  \frac{3^{16}}{16}

=>  \frac{(1 - 1)}{16}

=>  \frac{0}{16}

=>  remainder = 0

amitarya · Answer

Thanks for highlighting..
Corrected.

What is the remainder when 5^16 - 3^16 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 when 5^16 - 3^16 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