Modulo Reduction Using Fermat's Little Theorem

[scottstapp]

Homework Statement

Reduce 3⁴⁵⁶⁷ modulo 19.

Homework Equations

The Attempt at a Solution

I approached by first reducing 4567 modulo 18.

I got the following: 3⁴⁵⁶⁷= 3^18*253+13=(3¹⁸)²⁵³*3¹³ congruent to 1²⁵³1594323 congruent to 14 mod 19

Is this the correct approach? I am not sure where 14 came from in the end I just guess and checked until I found a value that worked which was 14. Any explanations on how to correctly find 14?

 

[Tinyboss]

You were exactly right to use Fermat's Little Theorem to show that 3⁴⁵⁶⁷ = 3¹³ mod 19. From there I'd use binary exponentiation: 3¹³ = 3⁸⁺⁴⁺¹ = 3⁸3⁴*3.

So mod 19, 3⁴ = 5, so then 3⁸ = 3⁴3⁴ = 25 mod 19 = 6 mod 19.

Put it together: 3⁸3⁴*3 = 6*5*3 mod 19 = 90 mod 19 = 14.