What is the remainder of $19^{1999}$ divided by 25?

Question

How to solve this problem without using Euler's Theorem?n Any help is highly appreciated!

What is the remainder of $19^{1999}$ divided by 25?

Answer 1

You can find out what value of $n$ satisfies $19^n\equiv1\mod25$ just by trying all values of $n$ from $1$ to $25$. Once you get that value, which I will call $m$, you find $19^k\mod25$, where $k\equiv1999\mod m$. In this case, $m=10$, so you find $k\equiv1999\equiv9\mod10$. Your final solution is $19^{1999}\equiv19^9\equiv4\mod25$.

Answer 2

$19^{1999} = (20-1)^{1999}=\sum (-1)^k a_k*20^{n-k} $

Note $20^2 =400 =16*25$. So $25$ divides all but the last two terms.

So $19^{1999}$ will have the same remainder as $1999(-1)^{1998}20 + (-1)^{1999}=39980-1=39979=39975+4$ which has remainder $4$.