Question

g 2 is a primitive root modulo 19. Use the following table to assist you in the solution of the first two questions and 4(a). The most efficient solutions involve the use of the table and the application of theory; numerically correct solutions involving long computations will not receive full credit t 1234567 8 9 10 11 12 13 14 15 16 1718 2 48 16 13 7 149 18 1715 11 3 6 12 5 10 1 (a) Find the least positive residue of 126 modulo 19 (efficiently, using the given information!). b) Find the number of solutions to x15 12 (mod 19 (e) Find all the solutions to ris ะไ (mod ¡9)

Answer 1

Given that g = 2 Now from the table above. 12 = 2^15 (module 19) i.e, 12^6 = 2^90 (mod 19) = (2^18)^5 (mod 19) But from given table 2^18 = 1 (mod 19) therefore 12^6 = (2^18)^(mod 19) = (1)^5 (mod 19) = 1 (mod 19) therefore 12^6 = 1 (mod 19) from table any x elementof {1, 2, 3,...,18} can be written a = 2^t for some t elementof {1, 2, 3,...18} therefore we have find solution (2^t)^15 = 12 (mod 19) i.e 2^15t = 12 (mod 19) from the table, 12 = 2^15 (mod 19) rightarrow 2^15t = 2^15 (mod 19) 2^15t - 15 = 1 (mod 19) \r\n rightarrow since 2 is primitive root module 19, we have 15t - 15/18 rightarrow 15t = 15 (mod 18) rightarrow Now here, a = 15, b = 15, m = 18 [therefore 2^18 = 1 (mod 19) & 2^t notequalto 1