Find the remainder of $13*12^{45}$ divided by $47$
I wrote $13\times 12^{45}$ as $(12+1)\times 12^{45} = 12^{46}+12^{45}$ so I can use Fermat to say that $12^{46}$ equals $1$ in $\Bbb Z_{47} $.
Now I just have to find $12^{45}$ in $\Bbb Z_{47} $. I know that $12^2 = 144$ which equals $3$ in $\Bbb Z_{47} $, and by multiplying that again and again by $12$ and using some properties of congruences I got to $12^{45}$. I managed to see that the total remainder is $22$ (I'm not sure if that's correct).
Anyways, this method took me a lot of time and I'm sure that there is another way, faster way, to solve it. Any hint?
$\endgroup$ 43 Answers
$\begingroup$Since $48\equiv1$ mod $47$, we have
$$13\cdot12^{45}\equiv48\cdot13\cdot12^{45}=52\cdot12^{46}\equiv5\cdot1=5\mod 47$$
$\endgroup$ 2 $\begingroup$Since $12^{46} \equiv 1$, we have $12^{45} \equiv 12^{-1}$, which is most easily found using the extended Euclidean algorithm: You want an integer $x$ such that $12x\equiv 1$, which is the same as saying you want an $x$ such that there is an integer $n$ so that $$ 12x+47n = 1 $$ and the extended Euclidean algorithm is exactly what provides such an $x$ (and an $n$ as well, but you don't care about that).
$\endgroup$ $\begingroup$Note that since $47$ is prime, we have $12^{46} \equiv 1 \pmod{47}$ by Fermat's Little Theorem.
Thus, we can reduce the expression $13 \times 12^{45} = 12^{46} + 12^{45} \equiv 1 + 12^{-1} \pmod{47}$
To evaluate this, we note the fact that $12 \times 4 = 48 \equiv 1 \pmod{47}$. Thus, $4 \equiv 12^{-1} \pmod{47}$.
Substituting this in gives us $13 \times 12^{45} \equiv 1+4 = 5 \pmod{47}$.
$\endgroup$
