I need to find the least nonnegative residue

Question

I have a hard time finding the least non negative residue of large numbers, and I'm having trouble with finding the least non negative residue of (1511)^7 (mod 3131) can someone help?

Answer 1

1. Prime decomposition of the modulus: $\;3131=31\cdot 101$.

   2. Bézout's relation between $31$ and $101$ with the extended Euclidean algorithm: $$\begin{array}[t]{rrrrr} \text{Successive Divisions}& r_i & u_i & v_i & q_i\\ \hline & 101 & 1 & 0 & \\ 101= {\color{red}3} \times 31 +\color{blue}{8} & 31 & 0 & 1 & \color{red}{3} \\ \hline 31 = {\color{red}3} \times 8 + \color{blue}{7} & \color{blue}{8} & 1 & -3 & \color{red}3 \\ 8 = {\color{red}1} \times 7 + \color{blue}{1} & \color{blue}{7} & -3 & 10 & \color{red}1 \\ & \color{blue}{1} & 4 & -13 \\ \hline \end{array}$$ Thus, $\;4\times 101-13\times31=1$.

   3. Reducing $1511$ modulo $31$ and modulo $101$: $$1511\bmod 31=-8,\quad 1511\bmod101=-4.$$

   4. Powers mod $31$ and mod $101$, with the fast exponentiation algorithm: $$\begin{array}{ccr} n&S& P\\ \hline 7&-8&-8\\ 3&2&2\cdot-8=15\\ 1&4&4\cdot15=\color{red}{-2}\\ \hline \end{array} \qquad\begin{array}{cr} S&P\\ \hline -4&-4\\ 16&16\cdot(-4)=37\\ 54&54\cdot 37=\color{red}{-22}\\ \hline \end{array}$$

   5. Thus $1511^7=-2\bmod31$ and $1511^7=-22\bmod101$, so that \begin{align*}1511^7&=-2\times 4\times101+22\times13\times31\\&=-2\times404+22\times403=20\times403-2\\&=8058\bmod3131, \end{align*} and the least non-negative integer of $1511^7\mod3131$ is $\;\color{red}{1796}$.