Evaluating modulos with large powers

Question

I need some help evaluating: $$13^{200} (mod \ 6)$$ What I've been trying to do:

$$13^1 \equiv 1 (mod \ 6)$$ $$13^2 \equiv 1 (mod \ 6)$$

Can I just say that: $$13^{200} = 13^2 * 13^2 * ... * 13^2 \equiv 1^{200}$$ Or is this incorrect?

Thanks in advance.

score 1 · Answer 1 · answered Sep 17 '14 at 22:16

1

$$ 13 \equiv 1 (mod \ 6) \implies 13^{200} \equiv 1^{200} (mod \ 6) \implies 13^{200} \equiv 1 (mod \ 6) $$

answered Sep 17 '14 at 22:16

Frank

score 1 · Answer 2 · answered Sep 17 '14 at 22:16

1

Since $gcd(13,6)=1$ we apply Euler's Theorem:

$$13^{\phi{(6)}} \equiv 1 \pmod 6 \Rightarrow 13^2 \equiv 1 \pmod 6$$

$$13^{200} \equiv (13^2)^{100} \equiv 1^{100} \equiv 1 \pmod 6$$

answered Sep 17 '14 at 22:16

Mary Star

2 Answers2