Properties of the sequences 3⋅2ⁿ+1

Golomb, Solomon W.

doi:10.1090/S0025-5718-1976-0404129-8

Properties of the sequences $3\cdot 2^{n}+1$
HTML articles powered by AMS MathViewer

by Solomon W. Golomb PDF

Math. Comp. 30 (1976), 657-663 Request permission

Erratum: Math. Comp. 38 (1982), 335-336.
Erratum: Math. Comp. 38 (1982), 335.

Abstract:

For applications to fast finite field transforms, one is interested in the arithmetic of $GF(p)$, where the order of the multiplicative group, $\varphi (p) = p - 1$, is divisible by a high power of 2, and where the multiplicative order of 2 modulo p is large. Primes of the form $3 \bullet {2^n} + 1$ appear well-suited to these objectives. Results are obtained on the divisibility properties of the numbers ${A_n} = 3 \bullet {2^n} + 1$, and on the exponent of 2 modulo ${A_n}$ when ${A_n}$ is prime. Generalizations to various related types of sequences are also considered.

References

Charles M. Rader, Discrete convolutions via Mersenne transforms, IEEE Trans. Comput. C-21 (1972), 1269–1273. MR 438672, DOI 10.1109/t-c.1972.223497
Irving S. Reed and T. K. Truong, The use of finite fields to compute convolutions, IEEE Trans. Inform. Theory IT-21 (1975), 208–213. MR 406677, DOI 10.1109/tit.1975.1055352
Raphael M. Robinson, A report on primes of the form $k\cdot 2^{n}+1$ and on factors of Fermat numbers, Proc. Amer. Math. Soc. 9 (1958), 673–681. MR 96614, DOI 10.1090/S0002-9939-1958-0096614-7
J. C. Morehead, Note on the factors of Fermat’s numbers, Bull. Amer. Math. Soc. 12 (1906), no. 9, 449–451. MR 1558370, DOI 10.1090/S0002-9904-1906-01371-4
Emma Lehmer, Criteria for cubic and quartic residuacity, Mathematika 5 (1958), 20–29. MR 95162, DOI 10.1112/S0025579300001303
Raphael M. Robinson, The converse of Fermat’s theorem, Amer. Math. Monthly 64 (1957), 703–710. MR 98057, DOI 10.2307/2309747