In this paper, we introduce some new semiring structures by considering the prime factors, sum of divisors and the number of relatively prime positive divisors of a pair of non-negative integers and solve a variety of system of linear equations over one of these semirings. We then discuss the properties of these structures and how they compare with classical algebra. The paper is concluded by providing a key-exchange scheme using one of the newly discovered semirings.