remainder question

Forum for the GRE subject test in mathematics.
Post Reply
brain
Posts: 28
Joined: Tue Aug 25, 2009 12:16 pm

remainder question

Post by brain » Tue Dec 21, 2010 10:49 am

What is the remainder when $$3^{12}$$ is divided by 12?

A 3 B 6 C 9 D11 E None of these


My point was since $$3^{12}$$ divided by 12 equals $$3^{11}$$ divided by 4 so it must be A, but I was wrong. To my surprise the answer is C.

le6tan
Posts: 8
Joined: Sat Apr 10, 2010 8:30 am

Re: remainder question

Post by le6tan » Tue Dec 21, 2010 12:28 pm

well just check some of the first remainders:

3^3 = 19
3^4 = 9
3^5 = 3
3^6 = 9
3^7 = 3
...

so an even power of 3 should have 9 as a remainder once divided by 12.

owlpride
Posts: 204
Joined: Fri Jan 29, 2010 2:01 am

Re: remainder question

Post by owlpride » Tue Dec 21, 2010 12:54 pm

brain wrote:My point was since $$3^{12}$$ divided by 12 equals $$3^{11}$$ divided by 4 so it must be A, but I was wrong. To my surprise the answer is C.
It is correct that 3^12 divided by 12 equals 3^11 divided by 4 as integers. However, you lose information about the residue class modulo 12 when you go to a residue class modulo 4. For example, a number congruent to 3 mod 4 could equal 3 or 7 or 11 mod 12 - there's no way to tell without additional information.

bobn
Posts: 61
Joined: Thu Nov 12, 2009 2:59 am

Re: remainder question

Post by bobn » Wed Dec 22, 2010 2:55 am

3^3 mod 12 = 3

So, 3^12 mod 12 = (3^3)^4 mod 12 = 3^4 mod 12 = (3^3)*3 mod 12 = 3*3 mod 12 = 9.

bobn
Posts: 61
Joined: Thu Nov 12, 2009 2:59 am

Re: remainder question

Post by bobn » Wed Dec 22, 2010 5:48 am

@brain

Are you non English speaker?

Divided by doesn't mean divisible.
The question asks remainder of 3^12 when it 12 divides it.
In other words the question says "find b when 3^12 is represented as a*12 + b"

Hope you got thee point.

brain
Posts: 28
Joined: Tue Aug 25, 2009 12:16 pm

Re: remainder question

Post by brain » Wed Dec 22, 2010 6:25 am

I understand the problem but how do you get (3^3)^4 mod 12 = 3^4 mod 12? Is it some theorem you use here?

prong
Posts: 24
Joined: Thu Sep 24, 2009 12:17 am

Re: remainder question

Post by prong » Wed Dec 22, 2010 7:19 am

You are working in the ring of integers mod 12. In this ring 3^3 is the same as 3, because 27 = 24 + 3 = 2*12 + 3.

Therefore, since 3^3 = 3 in that ring, anything at all containing 3^3 can be rewritten to use 3 instead of 27.

If you want to think of it more formally, the equivalence class of 3^3 is the same as the equivalence class of 3. Since the ring operations are well-defined, i.e. invariant under choice of representatives of equivalence classes, it doesn't matter which representative of the common equivalence class of 3 and 27 you use. In this case, it makes sense to take a representative with small absolute value--I'm sure it's clear why.
Last edited by prong on Wed Dec 22, 2010 7:21 am, edited 1 time in total.

bobn
Posts: 61
Joined: Thu Nov 12, 2009 2:59 am

Re: remainder question

Post by bobn » Wed Dec 22, 2010 7:21 am

Please refer to Properties of Congruences

http://mathworld.wolfram.com/Congruence.html

For proofs you can refer any introductory number theory book.

brain
Posts: 28
Joined: Tue Aug 25, 2009 12:16 pm

Re: remainder question

Post by brain » Wed Dec 22, 2010 7:42 am

bobn wrote:Please refer to Properties of Congruences

http://mathworld.wolfram.com/Congruence.html

For proofs you can refer any introductory number theory book.
It's more like what prong said, not a matter of property check. Exchanging representatives of a residue class in a congruence doesn't look like application of properties.

prong
Posts: 24
Joined: Thu Sep 24, 2009 12:17 am

Re: remainder question

Post by prong » Wed Dec 22, 2010 1:47 pm

Actually bobn's answer is probably more appropriate. It's not about "property check" (by which I think you mean, checking that properties of congruences hold)... but it is about applying those properties, which you should know. In this situation maybe I should've just quoted the fact (if a = b mod m then a^x = b^x mod m) and let you work out how it applies, as you're surely able to. This is the basic property of congruences I was explaining above in a bit more generality.

brain
Posts: 28
Joined: Tue Aug 25, 2009 12:16 pm

Re: remainder question

Post by brain » Thu Dec 23, 2010 11:30 am

OK, it's clear, bobn uses if a = b mod m then a^x = b^x mod m. But the confusing thing is that he writes mod on both sides of the equality. So it turns out that a^x mod m = b^x mod m which is not legal notation but it works out the needed remainder.

Thanks to all.

Becatien
Posts: 1
Joined: Sun Jun 02, 2013 2:31 am

Re: remainder question

Post by Becatien » Sun Jun 02, 2013 2:42 am

(1) 3^3(27) = 3 mod 12
(2) (3^3)^4 = 3^4 mod 12
(3) (3^3)^4 = 3*3^3 mod 12
(1) & (3) => 3^12 = 3*3 mod 12
(4) 3^12 = 9 mod 12
The remainder is 9.

DDswife
Posts: 161
Joined: Thu Aug 14, 2014 5:29 pm

Re: remainder question

Post by DDswife » Fri Aug 15, 2014 11:38 pm

Brain:

3^12 = 12q + r, where r is the remainder and q is the qotient. Of course, r < 12

Both, 3^12 and 12q are multiple of 3. Hence, r is a multiple of 3

Dividing everything by 3

3^11 = 4q + r/3

Since you know that r/3 is 3, then r is 9



Post Reply