In number theory, a full reptend prime, full repetend prime, proper prime[1]: 166 or long prime in base b is an odd prime number p such that the Fermat quotient
(where p does not divide b) gives a cyclic number. Therefore, the base b expansion of repeats the digits of the corresponding cyclic number infinitely, as does that of with rotation of the digits for any a between 1 and p − 1. The cyclic number corresponding to prime p will possess p − 1 digits if and only if p is a full reptend prime. That is, the multiplicative order ordp b = p − 1, which is equivalent to b being a primitive root modulo p.
The term "long prime" was used by John Conway and Richard Guy in their Book of Numbers. Confusingly, Sloane's OEIS refers to these primes as "cyclic numbers".
Base 10
[edit]Base 10 may be assumed if no base is specified, in which case the expansion of the number is called a repeating decimal. In base 10, if a full reptend prime ends in the digit 1, then each digit 0, 1, ..., 9 appears in the reptend the same number of times as each other digit.[1]: 166 (For such primes in base 10, see OEIS: A073761.) In fact, in base b, if a full reptend prime ends in the digit 1, then each digit 0, 1, ..., b − 1 appears in the repetend the same number of times as each other digit, but no such prime exists when b = 12, since every full reptend prime in base 12 ends in the digit 5 or 7 in the same base. Generally, no such prime exists when b is congruent to 0 or 1 modulo 4.
The values of p for which this formula produces cyclic numbers in decimal are:
- 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983, 1019, 1021, 1033, 1051... (sequence A001913 in the OEIS)
This sequence is the set of primes p such that 10 is a primitive root modulo p. Artin's conjecture on primitive roots is that this sequence contains 37.395...% of the primes.
Binary full reptend primes
[edit]In base 2, the full reptend primes are: (less than 1000)
- 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107, 131, 139, 149, 163, 173, 179, 181, 197, 211, 227, 269, 293, 317, 347, 349, 373, 379, 389, 419, 421, 443, 461, 467, 491, 509, 523, 541, 547, 557, 563, 587, 613, 619, 653, 659, 661, 677, 701, 709, 757, 773, 787, 797, 821, 827, 829, 853, 859, 877, 883, 907, 941, 947, ... (sequence A001122 in the OEIS)
For these primes, 2 is a primitive root modulo p, so 2n modulo p can be any natural number between 1 and p − 1.
These sequences of period p − 1 have an autocorrelation function that has a negative peak of −1 for shift of . The randomness of these sequences has been examined by diehard tests.[2]
Binary full reptend prime sequences (also called maximum-length decimal sequences) have found cryptographic and error-correction coding applications.[3] In these applications, repeating decimals to base 2 are generally used which gives rise to binary sequences. The maximum length binary sequence for (when 2 is a primitive root of p) is given by Kak.[4]
See also
[edit]References
[edit]- ^ a b Dickson, Leonard E., 1952, History of the Theory of Numbers, Volume 1, Chelsea Public. Co.
- ^ Bellamy, J. "Randomness of D sequences via diehard testing". 2013. arXiv:1312.3618.
- ^ Kak, Subhash, Chatterjee, A. "On decimal sequences". IEEE Transactions on Information Theory, vol. IT-27, pp. 647–652, September 1981.
- ^ Kak, Subhash, "Encryption and error-correction using d-sequences". IEEE Trans. On Computers, vol. C-34, pp. 803–809, 1985.
- Weisstein, Eric W. "Artin's Constant". MathWorld.
- Weisstein, Eric W. "Full Reptend Prime". MathWorld.
- Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, 1996.
- Francis, Richard L.; "Mathematical Haystacks: Another Look at Repunit Numbers"; in The College Mathematics Journal, Vol. 19, No. 3. (May, 1988), pp. 240–246.