Is there a way to solve congruences?

Question

Ofter i come across things like this:

$$7^x\equiv 1 \pmod{180} $$

$$x^3\equiv7 \pmod{13}$$

Are there easy ways to solve in general these kinds of congruences: $$a^x\equiv b \pmod{n} $$

$$x^a\equiv b \pmod{n}$$

For example $7^x\equiv 1 \pmod{180} $ has as solution $x\equiv 0 \pmod{12}$, I checked with Wolfram. But how can I do these?

Thank you for your time :)

Answer 1

In view of $a^x\equiv b\mod n$, the problem is to solve the discrete log problem in the ring ${\Bbb Z}_n$.

More specifically, given a group $G$ and $a,b\in G$, solving $a^x=b$ for some integer $x$ is the discrete log problem for the group $G$. There is no efficient method for solving it. Number-theoretic cryptography relies on it.

Answer 2

Hint

Using http://mathworld.wolfram.com/CarmichaelFunction.html

$\lambda(180)=12$

So, $x$ must divide $12$

$7^3\equiv-17\pmod{180}$

$7^4\equiv-17\cdot7\not\equiv1$

$7°6=(7^3)^2\equiv(-17)^2\not\equiv1$

Answer 3

Another way

As $180=5\cdot36$

$7\equiv2\pmod5,7^2\equiv2^2\not\equiv1,7^4\equiv1$

$7^x=(1+6)^x\equiv1+6x\pmod{36}$

So, $6$ divides $x$

For $\pmod{180}, x=[4,6]=?$