Method for Determining Prime and Relatively Prime Numbers of 2n+k Type Based on the Periodicity Property

摘要

The paper presents theoretical bases for determining the conditions for the divisibility of numbers of $2^{n}+k$ type using the periodicity property of modulo prime arithmetic. The proposed approach on the basis of the developed analytical expressions allows us to find prime and relatively prime numbers and solve the problem of factorization. The results obtained can be used as a basis for building high-performance special-purpose processors aimed at solving the above-mentioned problems. An example of application of the developed method for determining the divisibility of numbers of $2^{mathrm{n}}+3$ type by prime numbers in the range from 3 to 147 is given.