3
$\begingroup$

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

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

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.

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

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

$\endgroup$
3
$\begingroup$

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

Using Number of consecutive zeros at the end of $11^{100} - 1$.,

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

$\endgroup$
2
$\begingroup$

Hint: all $a$ are of the form

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

Can you prove this by induction?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – DanielV Dec 23 '14 at 5:16
  • $\begingroup$ Well, I agree. I should be possible though :P. $\endgroup$ – Edward Jiang Dec 23 '14 at 5:17

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.