1
$\begingroup$

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?

$\endgroup$
12
  • 1
    $\begingroup$ What is $2^5$ congruent to mod 31? $\endgroup$ May 26 '20 at 17:28
  • 1
    $\begingroup$ You have $4370=5\cdot874$, hence $2^{4370}=(2^5)^{874}$. Now evaluate this mod 31. $\endgroup$ May 26 '20 at 17:32
  • 1
    $\begingroup$ $2^{4370}\equiv2^{4350}2^{20}\equiv(2^{30})^{145}2^{20}\equiv(2^5)^4\equiv1\bmod31$ $\endgroup$ May 26 '20 at 17:59
  • 2
    $\begingroup$ $4371$ is a base $2$ Fermat pseudoprime $\endgroup$ May 26 '20 at 19:08
  • 1
    $\begingroup$ @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 $\endgroup$ May 27 '20 at 13:18
3
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.