What is the remainder when 19^2001 is divided by 23?

Question

I don't just need the answer. I need to see the method in a generic equation form, as well.

Answer 1

First, by Fermat's Little Theorem, 19^22 = 1(mod 23)
and 2001 = 90*22 + 21.
So19 ^2001 = 19^(90*22)*19^21 = 19^21(mod 23).
Since 19^22 = 1(mod 23), 19 ^21 = 1/19(mod 23)
= 19^-1(mod 23).
So we need to solve 19x = 1(mod 23)
and, by trial or by Euclid's algorithm, we find that
the answer is 17.
So the remainder is17.

Answer 2

as per Fernat's Little theorem if p is a prime

a^p-1 = 1 mod p

so 19^22 = 1 mod 23

now 2001 = 22*90+21

so 19^2001 mod 23 = (19^20)^90 * 19^21 mod 23
= 19^21 mod 23

now 19 = -4 mod 23

so 19^2 = 16 mod 23
19^4 = 256 mod 23 = 3 mod 23
19*20 = (19^4)^5 mod 23 = 3 ^5 mod 23 = 243 mod 23 = 13 mod 23
19^21 = 13 * 19 mod 23 = 247 mod 23 = 17

so remainder = 17



19

Answer 3

6
19/23 has remainder 4, 19^2001 has remainder 4^2001. 4^2001 when divided by 23 has a pattern of remainders that repeats itself every 11 times. the pattern goes 4,16,18,3,12,2,8,9,13,6,1, then repeats. 2001/11 has remainder of 10. the tenth number in the sequence is 6

Answer 4

19^2001 mod 23
≡ (-4)^2001 mod 23
≡ -4^(11*181+10) mod 23
≡ -4^10 mod 23
≡ -6 mod23
≡ 17 mod 23

----------
Ideas:
4^11 mod 23
≡ 1 mod 23

Answer 5

that's what a calculator is for