Find all $k∈Z_+$ such that:
i) $7834^k≡1$ $(mod$ $8613)$
ii) $7834^k≡6850$ $(mod$ $8613)$
iii) $7834^k≡2703$ $(mod$ $8613)$
iv) $7834^k≡1318$ $(mod$ $8613)$
Where $8613=3^3 *11 *29$
Hi I'm trying to learn the Chinese Remainder Theorem and now I'm facing problem where I have to it for exponentials. I have been given a proper solution, I just have a hard time following.
The solution:
We have isomorfi $f: Z_{8613} → (Z_{27}$ x $Z_{11}$ x $Z_{29})$. The I get $f(7834)=(4,2,4), f(1)=(1,1,1), f(6850)=(19,8,6), f(2703)=(3,8,6)$ and $f(1318)=(22,9,13)$.
So far so good, now the solution looks at a table:
Now apparently I'm supposed to be able to deduce that:
For part i) is says: $k≡_9 0,≡_{10} 0, ≡_{14} 0$
ii) $k≡_9 6, ≡_{10} 3, ≡_{14} 3$
iii) Is no such $k$ such that $4^k = 3$ in $Z_{27}$.
iv) $k≡_9 7, ≡_{10} 6, ≡_{14} 9$
Can someone please explain the last step after the table and how do I go from there to answer what $k$ is? Thanks.
I'll do case $(ii)$ below (the others are very similar).
$\begin{align} \phantom{\iff}&\qquad7834^k \equiv\ 6850\ \ \ \ \ \,\pmod{27\cdot 11\cdot 29}\\[.2em] \iff&\ \ \ (4,2,4)^k\equiv (19,8,6)\pmod{27,\ 11,\ 29}\\[.2em] \iff& \left\{\begin{array}{}4^k\equiv 19\pmod{27}\iff k\equiv 6\pmod{9}\\ 2^k\equiv\ \ 8\pmod{11}\iff k\equiv 3\pmod{10}\\ 4^k\equiv\ \ 6\pmod{29} \iff k\equiv 3\pmod{14} \end{array}\right. \end{align}$
Now $\,10,14\mid k-3\iff 70\mid k-3,\ $ by $\,{\rm lcm}(10,14) = 2\,{\rm lcm}(5,7)=70$
So $\,\bmod \color{#0a0}9\!:\,\ 6\equiv k\equiv 3+70\,\color{#c00}n\equiv 3-2n\iff 2n\equiv 6\iff \color{#c00}{n\equiv 3}$
Thus we conclude $\, k = 3+70(\color{#c00}3+\color{#0a0}9k) = 213+ 630k $