# Given 2 is a primitive root mod 19, find all solutions to x^12 ≡ 7 (mod 19) (a) x^12 ≡ 6 (mod 19)

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!

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

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 ?)

• 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? – – Kami Mar 24 at 7:58
• Yes, this is it, for $x^{12}=7$ you have $6$ solutions and for $x^{12}=6$ there are none. – zwim Mar 24 at 10:32

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?

• 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? – Kami Mar 24 at 5:30
• @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$. – Bernard Mar 24 at 11:11