An Algorithm to Solve A System of Linear Congruences with Applications

Abstract

In this paper, an algorithm as an alternative tool for solving system of linear congruences (SLC) is developed. this algorithm involves finding LCM of the moduli of reduced SLC, in view of cancellation law, identifying the largest moduli, and obtaining the solution of the linear congruence with largest modulus. Then it involves checking whether the solution satisfies the remaining linear congruences in the system of linear congruences. The advantage of this algorithm is the simplicity of its computation since it uses algebraic concepts which are easy to understand. Some illustrative examples are given to show the validity of this method for solving SLC’s. The application of the developed algorithm on solving system of linear congruences is also used to solving higher order congruences (HOC) with composite moduli and system of higher order congruences (SHOC).

Key words/Phrases: Chinese Remainder Theorem (CRT), linear congruences (LC), System of linear congruences (SLC), Applications to Higher order Congruences (HOC) and System of HOC with composite moduli.

DOI: 10.7176/MTM/9-10-05

Publication date: October 31^st 2019