Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

trying to solve:

$$x^{13} \equiv 11 \pmod{135}$$

I came to the fact that $x = 11^{59}$ but its in mod $72$ and needs to be converted to mod $135$

any suggestions? I'm not sure how to change it to mod $135$ with such a large number

share|improve this question

3 Answers 3

$135 = 3^3 \cdot 5$, so $\varphi(135) = 72$. Using Euclid, you find that $$ 1 = 13 \cdot (-11) + 72 \cdot 2 = 13 \cdot 61 + 72 \cdot (-11), $$ so $$ x \equiv (x^{13})^{61} \equiv 11^{61} \pmod{135}. $$

PS Once again, apologies for the initial mistake in this late-night post (never again!), and thanks to Gerry Myerson and user62340 for calling my attention to it.

To finish the calculation by hand, it is probably safer to compute first $$ 11^{11} = 11 \cdot 11^2 \cdot 11^{8} \equiv 41 \pmod{135}, $$ and then the inverse $56$ of $41$ modulo $135$, which is the required solution.

share|improve this answer
1  
$\phi(135)=72$. –  Gerry Myerson Feb 14 '13 at 23:24
    
@GerryMyerson, thank you so much, I shouldn't post this late in the evening, I'll fix it. –  Andreas Caranti Feb 14 '13 at 23:27
    
I thought ϕ(135) = 72 not 24... How did you get it Andreas? ϕ(135) is 2*3*3*4 ? –  user62340 Feb 14 '13 at 23:32
    
@user62340, it's late in the evening, I cannot count anymore. I have fixed it, thanks to you and Gerry Myerson for notifying me. –  Andreas Caranti Feb 14 '13 at 23:34

If $\rm\: x^{13}\equiv 11\,\ (mod\ 5\cdot27)\:$ then the same congruence holds mod $5$ and $27$, and we can use CRT (Chinese Remainder Theorem) to recombine the two solutions. It turns out to be very simple:

$\rm\quad\ mod\,\ 5\!:\ x^4\equiv 1,\:$ so $\rm\,x \equiv x (x^4)^3 \equiv x^{13}\equiv 11\equiv \color{#C00}1.\ \ $ Next $\ \phi(27) = 18,\:$ hence

$\rm\quad\ mod\ 27\!:\ 1 \equiv x^{18}\equiv x^{13} x^5 \equiv 11 x^5\:$ so $\rm\,x^5 \equiv \dfrac{1}{11}\equiv \dfrac{55}{11}\equiv 5\equiv 2^5\Rightarrow\:x\equiv \color{#0A0}2\ $ (unique, see Note)

$\rm\Rightarrow mod\ 5\cdot 27\!:\,\ x \equiv \color{#0A0}2 + 27\,\left[\dfrac{\color{#C00}1\!-\!\color{#0A0}2}{27}\ mod\ 5\right]\! \equiv 56,\ $ by $\rm\ mod\ 5\!:\, \dfrac{-1}{27}\equiv \dfrac{4}2 \equiv 2,\ $ using Easy CRT.

Note $\,\ 5$'th roots are unique $\rm\,mod\ 27\:$ since $\rm\, (5,\phi(27)) = (5,18) = 1,\:$ so $\rm\:n\equiv 1/5\ mod\ 18\:$ exists, hence $\rm\,x^5 = y^5\:\Rightarrow x\equiv x^{5n}\equiv y^{5n}\equiv y\,$ since $\rm\,5n\equiv 1\,\ (mod\ 18).$

share|improve this answer

$x^{13}\equiv11\pmod{135}\implies x^{13}\equiv11\pmod5$ and $x^{13}\equiv11\pmod{27}$

Using Euler's Totient Theorem, $$a^{\phi(m)}\equiv1\pmod m \text{ where }(a,m)=1$$

So, if $\phi(m)\mid(r-s),a^r\equiv a^s\pmod m$

$\implies x^{13}\equiv x\pmod5$ as $\phi(5)=5-1=4\implies x^{13}\equiv11\pmod5\iff x\equiv1\pmod5--->(1)$

Using this, if $a$ is primitive roots of prime $p$ and $p^2,a$ will be primitive roots of $p^n$ for $n\ge1$

$2^1\equiv-1\pmod3,2^2\equiv1\implies2$ is a primitive root of $3$

Now, $2^1\equiv2\pmod9,2^2\equiv4,2^3\equiv-1\implies ord_92=6=\phi(9)\implies2$ is a primitive root of $9$

So, $2$ is a primitive root of $3^n$ for $n\ge1$

Applying Discrete Logarithm with respect to base $2$ on $x^{13}\equiv11\pmod{27},$

$13\cdot ind_2x\equiv ind_211\pmod{18}$ as $\phi(27)=3^2(3-1)=18$

Now, $2^3\equiv8\pmod{27},2^4\equiv16\equiv-11\pmod{27}$

Again as $2$ is a primitive root of $27,2^{\frac{\phi(27)}2}\equiv-1\pmod{27}$ i.e., $2^9\equiv-1$

So, $11\equiv2^4\cdot2^9\equiv2^{13}\implies ind_211=13$

So, $13\cdot ind_2x\equiv 13\pmod{18}\implies ind_2x\equiv1\pmod{18}$ as $(13,18)=1$

So, $x\equiv2^1\pmod{27}\equiv2--->(2)$

Applying well known CRT on $(1),(2)$ we get $x\equiv2b_1\frac{27\cdot5}{27}+1\cdot b_2\frac{27\cdot5}5\pmod{27\cdot5}\equiv 10b_1+27b_2\pmod{135}$

where $b_1\frac{27\cdot5}{27}\equiv1\pmod {27}\iff 5b_1\equiv1$

and $b_2\frac{27\cdot5}5\equiv1\pmod{27}\iff 27b_2\equiv1$

Expressing $\frac{27}5$ as continued fraction, $\frac{27}5=5+\frac25=5+\frac1{\frac52}=5+\frac1{2+\frac12}$

So, the last convergent of $\frac{27}5$ is $5+\frac12=\frac{11}2$

Using convergent property of continued fraction, $27\cdot2-5\cdot11=-1$

$\implies 5\cdot11\equiv1\pmod{27}\implies 5^{-1}\equiv11\implies b_1\equiv11 $

and $27\cdot2\equiv-1\pmod5\implies (27)^{-1}\equiv-2\equiv3\implies b_2\equiv3$

So, $x\equiv27\cdot3+10\cdot11\pmod{135}\equiv191\equiv56$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.