# Find all the solutions of the congruence $12^x \equiv 17 \bmod 25$

I need to find all the solutions of the congruence $12^x \equiv 17 \bmod 25$.

I don't really have an idea how to approach this.. I tried to write it as:

$12^x \equiv 17 \mod 25$ $\Leftrightarrow$ $(3*2*2)^x \equiv -8 \mod 25$ $\Leftrightarrow$ $3^x 2^x 2^x + 2^3 \equiv 0 \mod 25$ $\Leftrightarrow$ $2^x(3^x 2^x 2^{3-x}) \equiv 0 \mod 25$

Is that the way to solve it? and how should I continue from here? thnk you very much

• Fermats little theorem and it's generalization is useful. For example $\varphi(25) = 20$ so $12^{20} \equiv 1 \mod 25$. If you find one solution $x\in[0,20]$ you can use this to generate all the other. – Kibble Apr 27 '16 at 22:11

As said in the comments, you can ultimately reduce to check a finite number of cases. I'll illustrate a standard method which often lessens the number of cases to check. The idea is: since a congruence $\pmod{p^m}$ is also a congruence $\pmod{p^k}$ for each $k<m$, you need not consider the cases for which it fails $\pmod {p^k}$ for $k<m$.

By Euler theorem, since $\operatorname{gcd}(12,\,25)=1$, solutions for $x$ are determined $\pmod{20}$.

Moreover, if $12^x\equiv17\pmod{25}$, then $$12^x\equiv17\pmod5$$

So, $x$ solves $$2^x=2\pmod5$$ as well.

Which is true if and only if $x\equiv 1\pmod{4}$.

So you only need check integers in the form $x=4k+1$ such that $0\le x\le 19$ (hence, $k=0,1,2,3,4$) and such that $12^x\equiv 17\pmod{25}$.

\begin{align}12^{4k+1}&\equiv17\pmod{25}\\12\cdot 12^{4k}&\equiv17\pmod{25}\\12\cdot(-6)^{2k}&\equiv17\pmod{25}\\12\cdot11^k&\equiv17\pmod{25}\\-2\cdot12\cdot11^k&\equiv-34\pmod{25}\\11^k&\equiv16\pmod{25}\end{align}

Now, \begin{array}{c|cc}k&11^k&\mod{25}\\\hline0&1\\1&11\\2&-4\\3&6\\\color{red}4&\color{red}{16}\end{array}

So, $k\equiv4\pmod 5$, hence $x\equiv17\pmod{20}$

• I did not understand that line: "Which is true if and only if x≡1(mod4)" ? Isn't it mod 5? – CnR Apr 28 '16 at 7:33
• @CnR No: if $\operatorname{gcd}(a,d)=1$, the solutions of the diophantine equation $$a^x\equiv b\pmod d$$ are in the form $$x\equiv k\pmod{\operatorname{ord}_d(a)}$$ where $$\operatorname{ord}_d(a):=\min\left\{m\in\Bbb N\,:\, m>0\ \text{ and }\ a^m\equiv1\pmod d\right\}$$ Euler's theorem yields that $\operatorname{ord}_5(a)\mid 4$, so solutions for $x$ are not $\pmod 5$. With direct calculation you can see that $2^2\not\equiv 1\pmod 5$. So $\operatorname{ord}_5(2)=4$. – user228113 Apr 28 '16 at 15:18
• I didn't learn Exponential Diophantine equations, are you using a theorem of such equation? – CnR Apr 30 '16 at 12:42
• @CnR I'm using the basilar results of the topic you've asked, so: yes, I'm using theorems concerning exponential diophantine equation. Such theorems are: existence of multiplicative order $\pmod d$ for integers which are coprime with $p$, Fermat's little theorem and Euler's (totient) theorem. – user228113 Apr 30 '16 at 13:02