elementary number theory - Modular equation with exponents on the exponents

I want to solve this modular equation:

$ 7x + 5 \equiv 2^{11^{2017}} \pmod {31}$

As far as I know, dividing the exponent by 31 and substituting it with the remainder is not allowed.

I've looked here and here but I don't see how to apply that to my equation.
I'm sorry for this short question but I don't really know how to approach this equation.

Answer

As far as I know, dividing the exponent by 31 and substituting it with the remainder is not allowed.

Correct. $a^k \not \equiv a^{(k\mod n)} \mod n$ is certainly not allowed.

(Although modulo distributes over addition and multiplication; $(a + \text{multiple of }n)\circ(b + \text{multiple of }n)= a\circ b + \text{multiple of }n$ when $\circ$ is either $+$ or $\times$--- it clearly does not distribute over exponents; $a^{k+ \text{multiple of }n} = a^k\times a^{\text{multiple of }n} \ne a^k + \text{multiple of }n$-- it simply does not.)

However you are allowed the two following.

if $a \equiv b \pmod n$ then $a^k \equiv b^k \pmod n$--

and if $a^m\equiv 1 \pmod n$ then $a^{(k\pmod m)} \equiv a^k \mod n$.

This is because $a^{k + m*h} = a^k*(a^m)^h \equiv a^k*(1)^h \equiv a^k \mod n$.

.....

Thus if we know $2^m \equiv 1 \pmod {31}$

Then $2^{11^{2017} } \equiv 2^{(11 \pmod m)^{2017}} \pmod {31}$.

So if we know $2^m \equiv 1 \pmod {31}$. And we know $11 \equiv a \mod m$. And we know $a^k \equiv 1 \pmod m$. And we know $2017 \equiv b \pmod k$ the we know:

$2^{11^{2017}}\equiv 2^{(11^{2017}\pmod m)} \equiv$

$2^{(11\pmod m)^{2017}}\equiv 2^{a^{2017}} \equiv 2^{a^{2017 \mod k}}$

$2^{a^b} \pmod {31}$.

.....

Which is not as abstract as it looks.

Why know by Fermat's Little Theorem that $2^{30} \equiv 1 \pmod {31}$ and by experimenting with smaller factors of $30$ we find that $2^5 = 32 \equiv 1 \pmod {31}$.

So $2^{11^{2017}}\equiv 2^{(11^{2017} \mod 5)}\equiv 1 \pmod {31}$.

Now clearly $11^{2017} \equiv 1^{2017} \equiv 1 \pmod 5$ so

$2^{11^{2017}}\equiv 2^1 \equiv 2 \pmod {31}$.

....

To put it another way.

$2^{11^{2017}} = 2^{(1 + 10)^{2017}} = 2^{1 + \text{some multiple of } 10}=$

$2*2^{\text{some multiple of } 10} = 2*((2^5)^2)^{\text{some integer}}=$

$2*(32)^{2*\text{some integer}} \equiv 2*1^{2*\text{some integer}}\pmod {32} \equiv 2\pmod {31}$.

=====

Oh, to actually solve the original question:

$7x + 5 \equiv 2^{11^{2017}} \pmod {31}$

$7x + 5 \equiv 2 \pmod {31}$

$7x \equiv -3 \pmod {31}$

Well, we could get lucky and notice $7x \equiv -3 \equiv 28\pmod {31}$ so $x \equiv 4 \pmod {31}$ will be one set of solutions. But is it the only one? And could we have solved it without getting lucky?

Well, we know if $\gcd (n,k) =1$ then we know that there exist $x, m$ so that $kx + mn = 1$.... or in other words thatn $kx \equiv 1 \mod n$ has a solution.

And if $n$ is prime we know that the solutions to $kx\equiv 1\mod n$ is unique up to modulo $31$ equivalence.

So $7m\equiv 1 \pmod {31}$ has a unique solution. By brute force/luck we can find that $7*9 = 63 \equiv 1 \pmod {31}$.

So $9$ is the multiplicative inverse of $7$ in tems of modulo $31$ equivalence.

So $7x + 5 \equiv 2 \pmod (31)$

$7x \equiv -3\pmod (31)$

$9*7x \equiv -3*9 \pmod(31)$

$63x \equiv -27 \pmod (31)$

$x \equiv 4 \pmod(31)$.