1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kibble Apr 27 '16 at 22:11
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I did not understand that line: "Which is true if and only if x≡1(mod4)" ? Isn't it mod 5? $\endgroup$ – CnR Apr 28 '16 at 7:33
  • $\begingroup$ @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$. $\endgroup$ – user228113 Apr 28 '16 at 15:18
  • $\begingroup$ I didn't learn Exponential Diophantine equations, are you using a theorem of such equation? $\endgroup$ – CnR Apr 30 '16 at 12:42
  • $\begingroup$ @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. $\endgroup$ – user228113 Apr 30 '16 at 13:02

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.