How to do large modulus by hand?

Question

How would I compute something like $2018^{2018} \bmod n$ by hand?

Additionally, how would I solve something like: $2018^{2018} \bmod n = 0$?

Answer 1

So given some base $b$ and exponent $e$ then for the form $b^e \mod n$ with $b, e \in \mathbb{Z}^+$ we begin by taking powers of $b$ sequentially with $b^0, b^1,b^2,b^3$,... until we find some $k \leq n$ such that $b^0 \equiv 1 \equiv b^k \mod n$. Then we do division with remainder to factor $e = kq + r$ and note that $b^e = b^{kq + r} = (b^{kq})(b^r)=(b^k)^q(b^r)$ and then because $(b^k)^q \equiv 1 \mod n$ this simplifies to $b^r \mod n$ which was calculated when finding the value of $k$. Essentially the values are periodic modulo $n$ and we exploit this to simply the calculation.

For the case when we consider $b^e \equiv 0 \mod n$ this will be true if and only if $b$ divides $n$ and $e \geq \frac{n}{b}$. See if you can parse out why using similar reasoning to what I used above.

As for one additional trick rather than using $0,1,2,...,n-1$ for your calculations instead center around zero and use positive and negative values. Say for modulo $7$ you can reduce to $\{-3,2,1,0,1,2,3\}$ to keep the numbers small at the expense of tracking the sign changes. Overall I find it faster for hand calculations.

Answer 2

Well, $2018^{2018}\equiv 0 \mod n$ just means $n|2018^{2018}$ and that can be any divisor.

To solve $2018^{2018}\mod n$ I'd use a combinition of Fermat and Chinese remainder theorem.

Example to solve $2018^{2018} \mod 3612$. I'd:

factor $3612 = 2^2*3*7*43$.

Then I'd solve $2018^{2018}\equiv 0 \mod 4$

$2018^{2018}\mod 3$.

$2018^{2018}\mod 7$ and $2018^{2018}\mod 43$

$\phi 3 = 2$ and $2018$ is relatively prie to $3$ so $2018^{2018}\equiv 1 \mod 3$

$\phi 7 = 6$ and $2018\equiv 2 \mod 6$ so $2018^{2018}\equiv 2018^2 \equiv 2^2\equiv 4 \mod 7$

$\phi 43 =42$ and $2018\equiv 2$ so $2018^{2018} \equiv 2018^2 \equiv 40^2 \equiv (-3)^2 \equiv 9 \mod 43$.

Now use chinese remainder theorem.

$x = 2018^{2018} \equiv 0 \mod 4$ and $x \equiv 1\mod 3$ so $x \equiv 4 \mod 12$.

$x \equiv 4 \mod 7$ so $x \equiv 4 \mod 84$.

$x \equiv 9\mod 43$ so

$84a + 43b=1$ can be solved.

$84 - 43 = 41$

$43 - 41 = 2$

$41- 20*2 = 1$

$1 = 41 - (43-41)*20 = (84-43) -(43-(84-43))*20= 21*84 - 43*41$

$9 + 43k = 4+ 84j$ so

$5 = 84j - 43k$. Let $j=21*5; k=41*5$

So $2018^{2018} \equiv x \equiv 9 + 4515=4524\equiv 912 \mod 3612$.