Question

Use Exercise $35$to find an inverse of $5$modulo $41$

Short answer

$33$

$33$ is the smallest positive integer that is an inverse of$5$modulo$41$

Step-by-step solution

Step 1

Exercise $35$states that if $p$is prime and $pxa$,then $a^{p-2}$ is an inverse of $a$modulo $p$.so $5^{41-2}=5^{39}$would be an inverse of $5$modulo $41$. Of course we can say the answer is $5^{39}$, but conventionally we want answer that is a positive integer less than $41$. So we have to evaluate localid="1668658378830" $5^{39}\mathrm{mod}41$, that is, we need to find the remainder when$5^{39}$is divided by$41$. If we directly calculate$5^{39}$, it will be a huge number. However, since we just need to know the remainder when$5^{39}$is divided by $41$, we can take advantage of exponentiation

Step 2

. If we directly calculate $5^{39}$, it will be a huge number. However, since we just need to know the remainder whe$5^{39}$is divided by $41$, we can take advantage of exponentiation.

$\begin{array}{r}{5}^{39}={\left(5^3\right)}^{13}(mod41)\\ =\left(125{)}^{13}\right(mod41)\to \text{because}125\equiv 2(mod41)\end{array}$

role="math" localid="1668658745905" $\begin{array}{r}\equiv 2^{13}(mod41)\\ ={\left(2^5\right)}^2\cdot 2^3(mod41)\end{array}$

$\begin{array}{r}=(32{)}^2.8(mod41)\to \text{because}32\equiv -9(mod41)\\ \equiv (-9{)}^2\cdot 8(mod41)\\ =81.8(mod41)\to \text{because}81\equiv -(mod41)\end{array}$

$\begin{array}{r}\equiv -1.8(mod41)\\ =-8(mod41)\\ \equiv 33(mod41)\end{array}$