-1
$\begingroup$

I'm stuck on (another) problem under Number Theory. There are quite a few gaps on what was covered in my class so I'm having quite a bit of trouble. Could you please help me solve the following problem?

2 is a primitive root mod 19. Using this information, find all solutions to x^12 ≡ 7 (mod 19) and x^12 ≡ 6 (mod 19)

I think I would have to make use of the powers of 2 to solve this, but I can't get any further than that.

Any help would be much appreciated!

$\endgroup$
  • $\begingroup$ You could start by listing out the powers of 2 $\pmod{19}$... $\endgroup$ – Dzoooks Mar 23 at 19:28
1
$\begingroup$

Hint:

Write $x=2^p$ (why ?) then you get $2^{12p}\equiv 2^y\pmod{19}$ where $y$ correspond to the representation for $7$ and $6$.

Then you get solve $12p\equiv y\pmod{18}$ (why ?)

$\endgroup$
  • $\begingroup$ This would solve to give k = 2, right? And then would the next one be 2^14 = 6 (mod 19) => 2^12k = 2^14 (mod 18)? I might have set this up wrong because I can't find a solution for 12k = 14 (mod 18). Any input? – $\endgroup$ – Kami Mar 24 at 7:58
  • $\begingroup$ Yes, this is it, for $x^{12}=7$ you have $6$ solutions and for $x^{12}=6$ there are none. $\endgroup$ – zwim Mar 24 at 10:32
1
$\begingroup$

Hint:

So you're given that $2$ has order $18\bmod 19$. In particular, $7\equiv 2^6\mod 19$.

Any solution can be written as $2^k$, where $k$ is unique module $18$. The equation can be rewritten as $$2^{12k}\equiv 2^6 \mod 19\iff 12k\equiv 6\mod 18\iff 2k\equiv 1\mod 3.$$

Can you continue?

$\endgroup$
  • $\begingroup$ This would solve to give k = 2, right? And then would the next one be 2^14 = 6 (mod 19) => 2^12k = 2^14 (mod 18)? I might have set this up wrong because I can't find a solution for 12k = 14 (mod 18). Any input? $\endgroup$ – Kami Mar 24 at 5:30
  • $\begingroup$ @Kami: For the first equation, you find $k\equiv 2\mod 3$, i.e. $k=2, 5, 8$, &c. As to the second equation, $12k\equiv 14\pmod{18}\iff 6k\equiv 7\pmod 9$, and there's not necessarily a solution, as $6$ is not a unit mod. $9$. Indeed $6$ has only three multiples mod. $9$: $\;6, 3$ and $0$. $\endgroup$ – Bernard Mar 24 at 11:11

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.