# Solutions of $2^a - 7 = 27b$

How can I find the solutions of the equation $2^a - 7 = 27b : a, b \in \mathbb{N}$? I can see this is also of the form $2^a - 7 \equiv 0 \mod 27$.

• the question in the title seems easier than that in the body – Jorge Fernández Hidalgo Dec 23 '14 at 4:49
• I edited the title. – Ahaan S. Rungta Dec 23 '14 at 4:51

Note that $2^a - 7 \equiv 0 \pmod {27} \iff 2^a \equiv 7 \pmod {27}$.

Note that the only $a$ such that this is true and $0 \le a \le \phi(27) = 18$ is $2^{16} \equiv 7 \pmod {27}$. Do you see why all $a$ such that $a \equiv 16 \pmod {18}$ are solutions and they are the only ones? Hint: look back at Euler's theorem.

• $a\equiv 16\pmod{18}$, where $18=\phi(27)$. – vadim123 Dec 23 '14 at 4:54
• @vadim123 Yes, sorry and thanks. Edited! – Ahaan S. Rungta Dec 23 '14 at 6:14
• I have the system $$2^a \equiv 7 \mod 27$$ and $$2^{18} \equiv 1 \mod 27$$ How can I solve this system? – Don Larynx Dec 23 '14 at 20:30

you want $2^a\equiv 7\bmod27$.

Compute all powers of $2 \bmod 27$ to get

$2,4,8,16,5,10,20,13,-1,-2,-4,-8,-16,-5,-10,-20,-13,1$. So $2$ has order $18$ mod $27$

Notice $-20\equiv7\bmod 27$ thus you want $2^{16+18k}$

$$2^2\cdot7\equiv1\pmod{27}\implies7\equiv2^{-2}$$

Using Prove that a primitive root of $p^2$ is also a primitive root of $p^n$ for $n>1$., $2$ is a primtive root $\pmod{3^n},n\ge1$

So modulo order ord$_{(3^n)}2=\phi(3^n)=3^{n-1}(3-1)$

$\implies7\equiv2^{-2}\equiv2^{-2+18}$

Proof : $2$ is a primitive root $\pmod9$

ord$_32=2$

$2^2\not\equiv1\pmod9\implies$ord$_{3^2}2\ne2\implies$ord$_92=3(3-1)=\phi(9)$

Hint: all $a$ are of the form

$$a=16+18k,\,k\in \mathbb{N}\cup \{0\}$$

Can you prove this by induction?

• This may be harder to prove with induction than you expect. How would you inductively prove $$\bigg(2^{16 + 18k} \not \mid 27 \bigg) \Rightarrow \bigg(2^{16 + 18(k+1)} \not \mid 27\bigg)$$ ? It is a good exercise to prove that the equation is sufficient, but not that it is necessary. – DanielV Dec 23 '14 at 5:16
• Well, I agree. I should be possible though :P. – Edward Jiang Dec 23 '14 at 5:17