Cubic reciprocity and explicit primality tests for \(h\cdot 3^k\pm1\). (English) Zbl 1103.11039

Bosma, Wieb

van der Poorten, Alf (ed.) et al., High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams. Selected papers from the international conference on number theory, Banff, AB, Canada, May 24–30, 2003. Providence, RI: American Mathematical Society (AMS) (ISBN 0-8218-3353-7/hbk). Fields Institute Communications 41, 77-89 (2004).

This is a thematical paper which succeeds to captivate with a simple classical problem. The use of quadratic reciprocity leads to deterministic tests for the Mersenne numbers \(M_n = 2^n - 1\) and the so-called Proth numbers, \(P(n, k) = k 2^n \pm 1\), which are generalizations thereof. By replacing the power of two by a power of three, one has a variant problem setting, which can be addressed by use of the cubic reciprocity. This is an obvious observation but has been seldom pursued concretely.
The author addresses the question in a general form, aiming to find covering sets of conditions for fixed \(n\) or \(k\) and touches thus en passant another interesting combinatorial problem going back to Sierpiński and which also interested Erdős. As a byproduct, he encounters values of \(k\) such that \(k \cdot 3^n - 1\) is composite for all \(n\), a frequent question of the covering set problems.
For the entire collection see [Zbl 1051.11008].

Reviewer: Preda Mihailescu (Göttingen)

MSC:

11Y11	Primality
11A07	Congruences; primitive roots; residue systems
11A15	Power residues, reciprocity