On indices modulo a number with no primitive roots

• Main Authors: Medina, Ma. Elaine L., Mendoza, Mary Gay O.
• Format: text
• Language: English
• Published: Animo Repository 1995
• Subjects: Number theory of; Linear systems; Congruences and residues; Groups, Theory of; Diophantine analysis
• Online Access: https://animorepository.dlsu.edu.ph/etd_bachelors/16261
• Institution: De La Salle University

A system of linear simultaneous congruences is a system of congruences that involves only one variable, but different moduli. The process of obtaining a solution to this system has a long history, appearing in the Chinese literature as early as the first century A.D.. Such systems arose in ancient Chinese puzzles such as the following: Find a number that leaves a remainder of 1 when divided by 3, a remainder of 2 when divided by 5, and a remainder of 3 when divided by 7.The rule for obtaining a solution goes by the name of the Chinese Remainder Theorem. An application of the Chinese Remainder Theorem leads to the main theorem of this paper which gives an easier way in finding indices modulo a number n which admits no primitive roots.The main theorem assumes that the integers n1, nj satisfy gcd (ni, nj) = 1, when I j where ni 2 (i = 2, ..., s) and n = n1 n2 ....n s. It also assumes that each n i admits a primitive root r i. We let x i denote the solutions of the s Chinese Remainder problems x1 = r1 (mod n1) x2 = 1 (mod n1) ... xs = 1 (mod n1) x1 = 1 (mod n2) x2 = r2 (mod n2) ... xs = 1 (mod n2) x1 = 1 (mod ns) x2 = 1 (mod ns) ... xs = r s (mod ns). Then every element M of a reduced residue system modulo n is produced exactly once by the congruences, M = k1 x1 X k2 x2 ... xs ks (mod n) where k i = 0, 1, 2, ... (ni) - 1, (i = 1, 2, ..., s).