A method of obtaining a solution of �� ����+���� ≡ �� (mod ��) when �� is prime and �� is a primitive root modulo ��

Abstract

The congruence relation modulo a positive integer identifies two integers if and only if their difference is divisible by that positive integer. The modern theory of congruences was developed by Gauss at the beginning of the 19th century. Several formulations are established in solving congruences of various types. In this study, we introduce a method in solving congruences of the form 𝑎 𝑝𝑥+𝑞𝑦 ≡ 𝑏 (mod 𝑚) for a prime number 𝑚 and integers 𝑎, 𝑏, 𝑝, and 𝑞. Since we do not have a standard generalized method of obtaining a solution for the aforementioned congruence type, some restricted forms of it were studied. In this work, we especially focus on the congruences of prime modulus 𝑚 and 𝑎 is a primitive root modulo 𝑚: If gcd(𝑎, 𝑛) = 1 and 𝜑(𝑛) is the order of 𝑎 modulo 𝑛, then 𝑎 is called a primitive root of the integer 𝑛. Here 𝜑(𝑛) is the Euler’s Phi function (totient function) of 𝑛, that counts the number of integers less than or equal to 𝑛 which are relatively prime to 𝑛. In or method, first, a solution system for 𝑎 𝑝𝑥+𝑞𝑦 ≡ 1 (mod 𝑚) is obtained. That solution system is used with a transformation to obtain a solution of the congruence 𝑎 𝑝𝑥+𝑞𝑦 ≡ 𝑏 (mod 𝑚). We prove that a solution of 𝑎 𝑝𝑥+𝑞𝑦 ≡ 1 (mod 𝑚) can be obtained by (±𝑘𝜑(𝑚) + 𝑥0, ±𝑙𝜑(𝑚) + 𝑦0), where 𝑘 and 𝑙 are non-negative integers. When (𝑥𝑜, 𝑦𝑜) is a solution of 𝑎 𝑝𝑥+𝑞𝑦 ≡ 1 (mod 𝑚) with both 𝑥𝑜, 𝑦𝑜 are not simultaneously zero, the obtained solution is transformed to a solution of 𝑎 𝑝𝑥+𝑞𝑦 ≡ 𝑏 (mod 𝑚) when gcd(𝑝, 𝑞) |𝑏. The former result can be used to obtain a solution for the congruence in the form of 𝑎 𝑝𝑥+𝑞𝑦 ≡ 𝑏 (mod 𝑚) when 𝑚 is prime and 𝑎 is a primitive root modulo 𝑚. In future, we hope to generalize this method when 𝑚 is composite and 𝑎 is not a primitive root modulo 𝑚.