remainder question

[brain]

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]

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]

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]

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]

@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]

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]

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.

[bobn]

Please refer to Properties of Congruences

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

For proofs you can refer any introductory number theory book.

[brain]

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]

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]

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]

(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]

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