0
$\begingroup$

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.

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

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What does it mean that 2 has order 5 mod 31? $\endgroup$ – Álvaro Oct 21 '18 at 11:27
  • $\begingroup$ 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$. $\endgroup$ – Bernard Oct 21 '18 at 11:49
0
$\begingroup$

$\!\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.

$\endgroup$
-1
$\begingroup$

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.

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

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

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