GRE Math question

[regularhumanbeing]

Took the GRE today and one question on the Quant section I'm still struggling to figure out, wondered if any geniuses here could explain this one to me.

 

3 to the 82nd power divided by 5 leaves what remainder?

 

It was a multiple choice, not a quant comp, so somehow you were expected to deduce this answer. For the life of me, I can't figure it out. I've since written a computer program to output all the remainders from 3 to the 0 to 3 to the 82nd power but I can't see any pattern here, nor can I brainstorm any way to simplify this question.

 

Any insights would at least give me peace of mind, although not change my score.

 

Thanks for your help.

[DerpTastic]

Without a calculator, there actually is a pattern here that can be used. Each time the power is raised the remainder will also change, but it should follow a pattern.

 

3 ^ 1 / 5 : Remainder of 3

3 ^ 2 / 5 : Remainder of 4

3 ^ 3 / 5 : Remainder of 2

3 ^ 4 / 5 : Remainder of 1

3 ^ 5 / 5 : Remainder of 3

3 ^ 6 / 5 : Remainder of 4

3 ^ 7 / 5 : Remainder of 2

3 ^ 8 / 5 : Remainder of 1

3 ^ 9 / 5 : Remainder of 3

 

As it's following a pattern, it goes 4 cycles then repeats. Just looking at the pattern quickly, 82 is an even power, so it would be either a remainder of 4 or 1, and because 82 is not divisible by 4, it lines up with answers like 3^2 and 3^6, so it must have a remainder of 4?

Edited August 3, 2013 by DerpTastic

[MikKar]

The units are cyclical after a power of 3, so that's all you need to know to figure out the remainder.

 

n = 0 -> Unit is 1 (3^0 = 1)

n = 1 -> Unit is 3 (3^1 = 3)

n = 2 -> Unit is 9 (3^2 = 9)

n = 3 -> Unit is 7 (3^3 = 27)

n = 4 -> Unit is 1 (3^4 = 81)

etc...

 

For a power of 82, you just need to know that 3^2 and 3^82 will have the same unit in the end, which is 9. A division by 5 will result in a remainder of 4.

 

 

Edit : Ah, DerpTastic beat me to it, haha

Edited August 3, 2013 by MikKar

[regularhumanbeing]

Ah. I started to do that, just didn't pick up the pattern correctly.

 

Thanks for the peace of mind, it's much appreciated. 

[33andathirdRPM]

http://en.wikipedia.org/wiki/Fermat%27s_little_theorem

[Guest Gnome Chomsky]

If you've ever taken discrete mathematics in college, they go over stuff like that. Especially when using modulus. 

[andythemonster]

3^1, the unit digit is 3;

3^2, the unit digit is 9;

3^3, the unit digit is 7;

3^4, the unit digit is 1;

3^5, the unit digit is 3 again;

....

since that repeats every 4, the unit digit of 3^82 must be 9;

so, the remainder must be 4.