Solutions To Several Congruences With Applications In Primality Testing

(Department of Mathematics, Anhui Normal University, Wuhu 241000) Abstract: The main results of this paper are devided into two parts. The first part is on the solutions to the congruence over Z, 2^n-2 ≡ 1 mod n. Richard K. Guy [Unsolved Problems in Number Theory, 3rd ed., Springer-Verlag, New York, 2004. MR 2076335 (2005h:11003)] asks if there are solutions to the congruence 2^n-2 ≡ 1 mod n with n≡ 9 mod 10. In this paper, we first tabulate all 31 solutions in the interval [3,3037000499], only one has final decimal digit 9, which is the product of three prime factors. Then we use Zhang Mingzhi's necessary and sufficient condition, trial division, Pollard ρ and Pollard p — 1 etc. factoring methods to find another solution with final digit 9, which is a product of two prime factors and which has 12 decimal digits.The second part is on the applications of congruences over extension rings of Z in primality testing. Zhang [Mathematics of Computation, 71 (2002), 1699-1734. MR 1933051 (2003f:11191)] first gave definitions of one-parameter quadratic-base (strong) probable primes and pseudoprimes. Let u (> 2) G Z. Put T_u = T mod (T² - uT + 1). If a composite n is a solution to the congruence T_u^n-ε = 1 mod n, Then n is called a pseudoprime to base T_u, or psp(T_u) for short, where If a composite n is a solution to the congruence T_u^q ≡ 1 mod n or to the congruence T_u^{(2r) q} ≡— 1 mod n for some r = 0,1, … ,k — 1, then n is called a strong pseudoprime to the base T_u, or spsp(T_u) for short, where we write n — ε = 2^kq with q odd. A (strong) probable prime to base T_u, denoted, prp(T_u) (sprp(T_u)), is a prime or a psp(T_u) (spsp(T_u)). Moreover, based on one-parameter quadratic-base pseudoprimes and strong pseudoprimes, Zhang provided a primality test, called the One Parameter Quadratic-Base Test (OPQBT). In this paper we first define ξ_m=min{n : n is an spsp(T_u) for all u with 3 ≤ u ≤ m + 2}. If we know the exact value of ï¿¡m, we will have a deterministic primality testing algorithm for integers n < ξ_m. We then give some properties of ï¿¡m and give procedures for finding ξ_mby these properties. Finally, we find exact values of ξ_m for i = 1, 2,3,4,5.