What is the remainder of $19^{1999}$ divided by 25?
By Emma Terry •
How to solve this problem without using Euler's Theorem?n Any help is highly appreciated!
$\endgroup$ 7What is the remainder of $19^{1999}$ divided by 25?
2 Answers
$\begingroup$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$.
$\endgroup$ 0 $\begingroup$$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$.
$\endgroup$ 1
