Solve the system of modular equations

Question

I have the system $$2^a \equiv 7 \mod 27 \\2^{18} \equiv 1 \mod 27$$ How can I solve this system?

I was thinking of using Chinese remainder theorem but 27 and 27 are not coprime.

Answer 1

We are given that $2^{18} \equiv 1 \pmod{27}$, and it is easy to see that $2^k \not\equiv 1 \pmod{27}$ for $1 \le k \le 17$ since none of $2^1 = 2$, $2^2 = 4$, $2^3 = 8$, $2^6 = 64$, $2^9 = 512$ are congruent to $1 \pmod{27}$.

Therefore, $2^k \equiv 1 \pmod{27}$ iff $k$ is a multiple of $18$.

Starting from $2^a \equiv 7 \pmod{27}$, we can multiply both sides by $2$ until the right side becomes $1$:

$2^a \equiv 7 \pmod{27} \leadsto 2^{a+1} \equiv 14 \pmod{27} \leadsto 2^{a+2} \equiv 28 \equiv 1 \pmod{27}$

Therefore, $2^a \equiv 7 \pmod{27}$ iff $18 \mid a+2$, i.e. $a \equiv 16 \pmod{18}$.

Answer 2

The group of units of $\mathbf Z/p^n\mathbf Z$ has ordre $\varphi(p^n)=p^{n-1}(p-1)$. Here, $\mathbf Z/27\mathbf Z$ has order $\varphi(27)=18$. By Lagrange's theorem, 2 has order 1, 3, 9 or 18. As it's not of order 1 nor 3, it has order 9 or 18. So all possible values for $2^a$ are obtained for $0 \le a \le 17$.

Actually we can start computing at $a=5$ since previous values in $\mathbf Z$ are less than $27$. We find successively $2^5 \equiv 5$, $2^6 \equiv 10 $, $2^7 \equiv -7 $, $2^8 \equiv -14$, $ 2^9 \equiv -1 $ (so $2$ is of order $18$, and it's a generator of the cyclic group $\mathbf Z/27\mathbf Z$).

From these data, we deduce at once that $2^{7+9}\equiv 7$, so that $a=16$.