The Hexianxuan Half-Order Theorem

This paper is under CC BY 4.0 International License. The Hexianxuan Half-Order Theorem (何先玄半阶定理) is established in this paper. Let n be an odd prime and a be a positive integer with gcd(a, n) = 1 and ord_n(a) = (n-1)/2. We prove the following results concerning the primitive root property of solutions to the congruence x^2 ≡ a (mod n): (1) If n ≡ 3 (mod 4), then among the two solutions of x^2 ≡ a (mod n), namely x ≡ ± a^((n+1)/4) (mod n), exactly one solution x ≡ -a^((n+1)/4) (mod n) is a primitive root modulo n, while the other solution x ≡ a^((n+1)/4) (mod n) is not a primitive root modulo n (it is in fact a quadratic residue). (2) If n ≡ 1 (mod 4), then both solutions of x^2 ≡ a (mod n) are primitive roots modulo n. The proof relies on the order formula ord_n(g^k) = (n-1)/gcd(k, n-1) for a primitive root g modulo n, together with a detailed analysis of the parity of m = (n-1)/2 and the coprimality condition gcd(e, n-1) = 1, where e = k + (k+1)m. This theorem provides a complete characterization and a useful criterion for constructing primitive roots from elements of half order (n-1)/2. This paper is under CC BY 4.0 International License. Mathematics Subject Classification (2020): 11A07, 11A15