# 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.

• Apply this and then this to the right-hand side. – metamorphy Oct 21 '18 at 10:49

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)$$.

$$2$$ has order $$5\bmod 31$$, so $$2^{11^{2017}}\equiv2^{11^{2017}\bmod 5}\pmod{31}.$$ Now $$11\equiv 1\mod 5$$, so $$11^{2017}\equiv 1\mod 5$$ and eventually $$2^{11^{2017}}\equiv2^1=2\mod{31}$$, so the congruence equation becomes $$7x+5\equiv 2\iff7x\equiv -3\iff x\equiv 9(-3)=-27\equiv \color{red}{4}\mod31$$ since $$7^{-1}\equiv 9\mod 31$$.

• What does it mean that 2 has order 5 mod 31? – Álvaro Oct 21 '18 at 11:27
• We're in the (multiplicative) group of units mod. $31$. It is the smallest positive integer $k$ such that $2^k\equiv 1\mod 31$. – Bernard Oct 21 '18 at 11:49

$$\!\bmod 31\!:\ 2^{\large\color{#c00} 5}\equiv 1\,\Rightarrow\, 2^{\large 11^{\Large n}}\!\! \equiv 2^{\large 11^{\Large n}\bmod\color{#c00}5}\!\equiv 2\$$ by $$\ 11^{\large n}\equiv 1^{\large n}\equiv 1\pmod{\!\color{#c00}5},\,$$ by Lemma below.

Thus $$\,7 x + 5\equiv 2\iff x\equiv \dfrac{-3}{7}\equiv \dfrac{-3\cdot 4}{\,\ \ 7\cdot 4}\equiv \dfrac{-12}{-3}\equiv 4\$$ by Gauss's algorithm.

Lemma $$\$$ If $$\,\ \color{#c00}{a^{\large n}\equiv 1}\,\$$ then $$\ a^{\large K}\equiv a^{\large k}\$$ if $$\,K\equiv k\pmod n$$

Proof $$\$$ Wlog $$\,K\ge k\,$$ so $$\, K = k + jn\$$ for $$\ j\ge 0.\$$ Therefore

$$a^{\large K}\equiv a^{\large k+jn}\equiv a^{\large k} (\color{#c00}{a^{\large n}})^{\large j}\equiv a^{\large k}\, \color{#c00}{1}^{\large j}\equiv a^k$$

using basic congruence rules such as the Congruence Power Rule.

To solve such question, I would simplify the right hand side first. Notice that $${(2^{11})}^{2017} \equiv 2^{2017} \pmod{31}$$. Further more, $$2017 = 67 \times 30 + 7$$. Therefore, By Fermat's theorem, $$2^{2017} \equiv {(2^{30})}^{67} \times 2^7 \equiv 1 \times 2^7 \equiv 128 \equiv 4 \pmod{31}$$.

The equation finally becomes

$$7x+5 \equiv 4 \pmod{31} \to 7x \equiv -1 \pmod{31}$$

Notice that I divided by $$30$$ instead of $$31$$ when using Fermat little theorem.

• But you are computing the innermost power, instead of starting with the outermost (11^2017). Isn't that invalid? – Álvaro Oct 21 '18 at 11:17
• if you know that $a\equiv b \pmod c$ then $a^n \equiv b^n \pmod c$ – Maged Saeed Oct 21 '18 at 11:36

$$2^5\equiv1(\mod31).$$ Thus, $$2^{11^{2017}}=2^{11\left(121^{1008}-1\right)+11}\equiv2^{11}\equiv2.$$ Id est we need to solve $$7x\equiv-3(\mod31)$$ or $$63x\equiv-27(\mod31)$$ or $$x\equiv4(\mod31).$$