How do I get that $11^{35} \equiv 6 \hspace{0.1cm} \text{mod} (13)$ from $11^{36} \equiv 1 \hspace{0.1cm} \text{mod} (13)$ [duplicate]

$\begingroup$

I have no clue how to do this, I manage to get I get that $11^{36} \equiv 1 \hspace{0.1cm} \text{mod} (13)$ but I can't get anywhere from there.

$\endgroup$ 1

5 Answers

$\begingroup$

If $11^{36}=1$ in $\Bbb Z/13$, then $11^{35}=11^{-1}$. But since $6\cdot 11=66=1$ in $\Bbb Z/13$, we have $11^{-1}=6$.

Here I just write $a=b$ in the ring $\Bbb Z/n$ for $a\equiv b\bmod n$, so that we see it a bit easier. For $n=13$, $\Bbb Z/n$ is a field and all nonzero elements have an inverse.

$\endgroup$ 3 $\begingroup$

All you need to know for this is that, since $13$ is a prime number, $\mathbb{Z} / 13 \mathbb{Z}$ is a field.

In particular, every non zero element has a unique inverse for multiplication. Constating that$$11 \times 6 = 66 \equiv 1 \hspace{0.1cm} \text{mod} (13)$$it turns out that the multiplicative inverse of $11$ is $6$ : $\boxed{11^{-1} \equiv 6}$.

Now, since you know that $11^{36} \equiv 1 \hspace{0.1cm} \text{mod} (13)$, it turns out that :

$$11^{35} \equiv 11^{36} \times 11^{-1} \equiv 1 \times 6 \equiv 6 \hspace{0.1cm} \text{mod} (13)$$

$\endgroup$ $\begingroup$

What were your efforts ? However, if you proved that $11^{36} \equiv 1 \hspace{0.1cm} (13)$ then you have that $11^{35}\cdot 11 \equiv 1 \hspace{0.1cm}(13)$. In this line it is written that $11^{35}$ is the inverse of $11$ by definition, by uniqueness you only have to prove that $6$ does the same job, i.e $6 \cdot 11 \overset{?}{\equiv} 1 \hspace{0.1cm}(13)$, which is true, and you have the desired result.

$\endgroup$ 2 $\begingroup$

Use this relation:

$6\times 11-5\times 13=1$

So we can write:

$$11^{36}\equiv (6\times 11-5\times 13=1) \ mod (13) \equiv 6 \times 11\ mod (13)$$

Therefore:

$11^{36}\equiv 6\times 11 \ mod(13)$

Dividing both sides by 11 we get:

$11^{35} \equiv 6 \ mod(13)$

$\endgroup$ $\begingroup$

The exercise here is to calculate the multiplicative inverse of $11$, written $11^{-1}$, in $\bmod 13$ arithmetic. Then we can get that since $11^{36}\equiv 1$, we will have $11^{35}\equiv 11^{36}\cdot 11^{-1}\equiv 11^{-1}\bmod 13$

Now $13$ and $11$ are coprime (of course, since $13$ is prime) so it's guaranteed that there is a value $a$ such that $11a \equiv 1 \bmod 13$. For a small number like $13$, it's not too hard to find this by guessing, but the extended Euclidean algorithm will find the value rapidly for less straightforward cases.

To show the logic of this algorithm, we find progressively smaller results which we can make with linear combinations of $13$ & $11$ until we make $1$:\begin{align}1\cdot 13 + 0\cdot 11 &= 13 \tag{setup: 1}\\ 0\cdot 13 + 1\cdot 11 &= 11 \tag{setup: 2}\\ 1\cdot 13 + -1\cdot 11 &= 2 \tag{(1)-(2): 3 }\\ -5\cdot 13 + 6\cdot 11 &= 1 \tag{(2)-5(3): result }\\\end{align}gives us that $6\cdot 11 \equiv 1$ so $11^{-1}\equiv 6 \bmod 13$.

$\endgroup$