Method for Determining Prime and Relatively Prime Numbers of 2n+k Type Based on the Periodicity Property
Igor Yakymenko, Mykhailo M. Kasianchuk, Stepan Ivasiev, Ruslan Shevchuk, Yuriy Batko, Vladyslav Vasylkiv · 2020
The paper presents theoretical bases for determining the conditions for the divisibility of numbers of 2n+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 2n+ type by prime numbers in the range from 3 to 147 is given.