4
$\begingroup$

I've just started a cryptography course, so i am not experienced at all how to calculate such big numbers. Clearly, i can't use a calculator, because the number is too big, so i have to calculate it by hand.

Since $101$ is a prime number, i think i should use here Fermat's little theorem. Found some example and tried to solve it this way, but i am totally not sure, if it is correct and if my approach must be this one.

Calculate $5^{3^{1000}}\bmod 101$.

First of all i think i should calculate $3^{1000}\bmod 101$. From Fermat's little theorem i get to $3^{100}\equiv 1\bmod 101$.

Thus $1000=x100+0$ and $x=10$.

$3^{1000}\equiv 3^{999^{10}} = 1 ^{10} \equiv 102\bmod 101 $

Later i have to calculate $5^{102}\bmod 101$. Again by Fermat $5^{100}\equiv 1\bmod 101$.

$$102=100\cdot 1 +2$$

Here i am not sure how to move on... I think that my solution is wrong, but i'd love to see your suggeststions and remarks how to solve the problem. Thank you very much in advance!

Improve this question
$\endgroup$
2
$\begingroup$

By Fermat's little theorem we know that $5^{100} \equiv 1 \bmod 101$.

What exactly does this tell us? It tells us that the powers of $5$ when reduced mod $101$ repeat every $100$ times.

So to find out what $5^{3^{1000}}$ is mod $101$ we really need to find out what $3^{1000}$ is mod $100$.

You can use the generalisation of FlT mentioned in another answer to see that $3^{40} \equiv 1 \bmod 100$, so that $3^{1000} = (3^{40})^{25} \equiv 1^{25} \equiv 1 \bmod 100$.

Alternatively you can do it by little step by step calculations.

Either way we find that $5^{3^{1000}} \equiv 5 \bmod 101$.

Improve this answer
$\endgroup$
  • $\begingroup$ Or he can type 3^1000 into an appropriate software an look at the last two digits ;) $\endgroup$ – Carsten S Sep 29 '13 at 21:56
  • $\begingroup$ ...but surely with that attitude he can type $5^{3^{1000}} mod 101$ into appropriate software? $\endgroup$ – fretty Sep 29 '13 at 22:07
  • $\begingroup$ Fair enough. I just wanted to point out that while it is agains the spirit of the problem, it is quite feasible to compute 3^10 exactly. $\endgroup$ – Carsten S Sep 30 '13 at 10:52
2
$\begingroup$

You should calculate $3^{1000}\mod \varphi(101)=100$. Here Fermat's little theorem doesn't apply, since $100$ is not prime, thus you must resort to Euler's theorem

If $(a,n)=1$, then $a^{\varphi(n)}=1\mod n$.

Improve this answer
$\endgroup$
1
$\begingroup$

You have seen that $5^{100} \equiv 1 \pmod{101}$. It follows that $5^{100a+b} \equiv 5^b \pmod{101}$. Now you should see to which modulus you need to calculate $3^{1000}$.

Improve this answer
$\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.