# Finding $x$ such that $2^{4370} \equiv x \ (\mathrm{mod} \ 31)$

How to find $$x$$ such that $$2^{4370} \equiv x \ (\mathrm{mod} \ 31)$$?

The task is to compute $$2^{4370} \ (\mathrm{mod} \ 4371$$).

I know it's $$4371=3 \cdot 31 \cdot 47$$, so it's $$2 \equiv -29 \ (\mathrm{mod} \ 31)$$.

With Fermat's little theorem it's $$-29^{30} \equiv 1 \ (\mathrm{mod} \ 31)$$

$$\Rightarrow 2^{4370} \equiv -29^{4370} \equiv -29^{145 \cdot 30+20} \equiv -29^{20} \ (\mathrm{mod} \ 31)$$.

But how to continue?

I want to find a smaller number than $$-29^{20}$$ without a calculator. The calculator says $$x=1$$, but how to find it without?

• What is $2^5$ congruent to mod 31? May 26 '20 at 17:28
• You have $4370=5\cdot874$, hence $2^{4370}=(2^5)^{874}$. Now evaluate this mod 31. May 26 '20 at 17:32
• $2^{4370}\equiv2^{4350}2^{20}\equiv(2^{30})^{145}2^{20}\equiv(2^5)^4\equiv1\bmod31$ May 26 '20 at 17:59
• $4371$ is a base $2$ Fermat pseudoprime May 26 '20 at 19:08
• @CopyPasteIt: of course OP did not demonstrate that $4371$ is a base $2$ Fermat pseudoprime (yet) -- OP here was having trouble computing $2^{4370} \bmod 31$, which could be one of the steps toward that -- but I thought you asked why $4371$, so I gave an explanation of why $4371$ would be of interest May 27 '20 at 13:18

One way to proceed is to find an $$n$$ to get $$2^n$$ close (either on the left or right) of $$31$$.

Well

$$\quad 2^5 = 32 \equiv 1 \;(\text{ mod 31})$$

Couldn't come out that much better; yes, $$0 \lt 1$$, but...

So

$$\quad \displaystyle 2^{4370} = ({2^5})^{874} \equiv (1)^{874} \;(\text{ mod 31}) \equiv 1 \;(\text{ mod 31})$$

Fermat's little theorem works like a charm for modulus $$3$$ (resp. $$47$$) since $$3 -1 = 2$$ divides $$4370$$ (resp. $$47 - 1 = 46$$ divides $$4370$$). But even though $$30$$ doesn't divide $$4370$$, we can still use it when working in modulus $$31$$. Copying J.W.Tanner's comment,

$$\quad 2^{4370}\equiv2^{4350}2^{20}\equiv(2^{30})^{145}2^{20}\equiv 2^{20} \bmod31$$

Applying any 'divide and conquer' tactic you'll find that

$$\quad 2^{20} \equiv1\bmod31$$