Full reptend prime

(Redirected from Long prime)

In number theory, a full reptend prime, full repetend prime, proper prime[1] :166 or long prime in base b is a prime number p such that the formula

$\frac{b^{p - 1} - 1}{p}$

(where p does not divide b) gives a cyclic number. Therefore the digital expansion of $1/p$ in base b repeats the digits of the corresponding cyclic number infinitely, as does that of $a/p$ 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, ordbp = p - 1.

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 repetend the same number of times as each other digit.[1]:166

The values of p less than 1000 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, ... (sequence A001913 in OEIS)

For example, the case b = 10, p = 7 gives the cyclic number 142857; thus 7 is a full reptend prime. Furthermore, 1 divided by 7 written out in base 10 is 0.142857 142857 142857 142857...

Not all values of p will yield a cyclic number using this formula; for example p = 13 gives 076923 076923. These failed cases will always contain a repetition of digits (possibly several) over the course of p - 1 digits.

The known pattern to this sequence comes from algebraic number theory, specifically, 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.

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."

Patterns of occurrence of full reptend primes

Advanced modular arithmetic can show that any prime of the following forms:

1. 40k+1
2. 40k+3
3. 40k+9
4. 40k+13
5. 40k+27
6. 40k+31
7. 40k+37
8. 40k+39

can never be a full reptend prime in base-10. The first primes of these forms, with their periods, are:

40k+1 40k+3 40k+9 40k+13 40k+27 40k+31 40k+37 40k+39
41
period 5
43
period 21
89
period 44
13
period 6
67
period 33
31
period 15
37
period 3
79
period 13
241
period 30
83
period 41
409
period 204
53
period 13
107
period 53
71
period 35
157
period 78
199
period 99
281
period 28
163
period 81
449
period 32
173
period 43
227
period 113
151
period 75
197
period 98
239
period 7
401
period 200
283
period 141
569
period 284
293
period 146
307
period 153
191
period 95
277
period 69
359
period 179

However, studies show that two-thirds of primes of the form 40k+n, where n ≠ {1,3,9,13,27,31,37,39} are full reptend primes. For some sequences, the preponderance of full reptend primes is much greater. For instance, 285 of the 295 primes of form 120k+23 below 100000 are full reptend primes, with 20903 being the first that is not full reptend.

Base 2 full reptend primes

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 OEIS)

For these primes, 2 is a primitive root modulo p, so 2n module p can be any natural number between 1 and p-1.

All of them are of form 8k+3 or 8k+5, because if p = 8k+1 or 8k+7, then 2 is a quadratic residue modulo p, so p divides 2(p-1)/2−1, and the period of 1/p in base 2 must divide (p−1)/2 and cannot be p−1, so they are not full reptend primes in base 2.

Further, all safe primes congruent to 3 (mod 8) are full reptend primes in base 2. For example, 3, 11, 59, 83, 107, 179, 227, 347, 467, 563, 587, 1019, 1187, 1283, 1307, etc. (less than 1500)

The following is a list about the periods to the primes congruent to 1 or 7 (mod 8): (less than 1000)

 8k + 1 period 8k + 1 period 8k + 7 period 8k + 7 period 17 41 73 89 97 113 137 193 233 241 257 281 313 337 353 401 409 433 449 457 521 569 8 20 9 11 48 28 68 96 29 24 16 70 156 21 88 200 204 72 224 76 260 284 577 593 601 617 641 673 761 769 809 857 881 929 937 953 977 1009 1033 1049 1097 1129 1153 1193 144 148 25 154 64 48 380 384 404 428 55 464 117 68 488 504 258 262 274 564 288 298 7 23 31 47 71 79 103 127 151 167 191 199 223 239 263 271 311 359 367 383 431 439 3 11 5 23 35 39 51 7 15 83 95 99 37 119 131 135 155 179 183 191 43 73 463 479 487 503 599 607 631 647 719 727 743 751 823 839 863 887 911 919 967 983 991 1031 231 239 243 251 299 303 45 323 359 121 371 375 411 419 431 443 91 153 483 491 495 515

The binary period of nth prime are

2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 11, 48, 100, 51, 106, 36, 28, 7, 130, 68, 138, 148, 15, 52, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29, 119, 24, 50, 16, 131, 268, 135, 92, 70, 94, 292, 102, 155, 156, 316, 30, 21, 346, 348, 88, 179, 183, 372, 378, 191, 388, 44, ... (this sequence starts at n = 2, or the prime = 3) (sequence A014664 in OEIS)

The binary period level of nth prime are

1, 1, 2, 1, 1, 2, 1, 2, 1, 6, 1, 2, 3, 2, 1, 1, 1, 1, 2, 8, 2, 1, 8, 2, 1, 2, 1, 3, 4, 18, 1, 2, 1, 1, 10, 3, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 6, 1, 3, 8, 2, 10, 5, 16, 2, 1, 2, 3, 4, 3, 1, 3, 2, 2, 1, 11, 16, 1, 1, 4, 2, 2, 1, 1, 2, 1, 9, 2, 2, 1, 1, 10, 6, 6, 1, 2, 6, 1, 2, 1, 2, 2, 1, 3, 2, 1, 2, 1, 1, ... (sequence A001917 in OEIS)

However, studies show that three-fourths of primes of the form 8k+n, where n ≠ {1,7} are full reptend primes in base 2 (For example, there are 87 primes below 1000 congruent to 3 or 5 (mod 8), and 67 of them are full-reptend in base 2, it is total 77%). For some sequences, the preponderance of full reptend primes is much greater. For instance, all of the primes of form 24k+5 below 1000 are full reptend primes in base 2, with 1013 being the first that is not full reptend in base 2.

Full reptend primes in various bases

Artin also conjectured that full-reptend primes in all bases except perfect powers and numbers whose squarefree part are congruent to 1 to mod 4 comprise 37.395...% of all primes. (See )

Base Full reptend primes OEIS sequence
−20 11, 13, 17, 31, 37, 53, 59, 73, 79, 113, 131, 137, 139, 157, 173, 179, 191, 199, 211, 233, 239, 257, 271, 277, ... A105892
−18 5, 7, 23, 29, 31, 37, 47, 53, 61, 71, 101, 103, 109, 127, 149, 151, 157, 167, 173, 181, 191, 197, 223, 239, ... A105890
−16 3, 7, 11, 19, 23, 47, 59, 67, 71, 79, 83, 103, 107, 131, 139, 163, 167, 179, 191, 199, 211, 227, 239, 263, 271, ... A105876
−12 5, 17, 23, 41, 47, 53, 59, 71, 83, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 239, 251, 257, ... A105884
−11 2, 7, 13, 17, 29, 41, 73, 79, 83, 101, 107, 109, 127, 131, 139, 149, 151, 167, 173, 197, 227, 233, 239, 263, ... A105883
−10 3, 17, 29, 31, 43, 61, 67, 71, 83, 97, 107, 109, 113, 149, 151, 163, 181, 191, 193, 199, 227, 229, 233, 257, ... A007348
−9 2, 7, 11, 19, 23, 31, 43, 47, 59, 71, 79, 83, 107, 127, 131, 139, 163, 167, 179, 191, 199, 211, 223, 227, 239, ... A105881
−8 5, 23, 29, 47, 53, 71, 101, 149, 167, 173, 191, 197, 239, 263, 269, 293, 311, 317, 359, 383, 389, 461, 479, 503, ... A105880
−7 2, 3, 5, 13, 17, 31, 41, 47, 59, 61, 83, 89, 97, 101, 103, 131, 139, 167, 173, 199, 227, 229, 241, 251, 257, ... A105879
−6 13, 17, 19, 23, 41, 47, 61, 67, 71, 89, 109, 113, 137, 157, 167, 211, 229, 233, 257, 263, 277, 283, 331, 359, ... A105878
−5 2, 11, 17, 19, 37, 53, 59, 73, 79, 97, 113, 131, 137, 139, 151, 157, 173, 179, 193, 197, 233, 239, 257, 277, ... A105877
−4 3, 7, 11, 19, 23, 47, 59, 67, 71, 79, 83, 103, 107, 131, 139, 163, 167, 179, 191, 199, 211, 227, 239, 263, 271, ... A105876
−3 2, 5, 11, 17, 23, 29, 47, 53, 59, 71, 83, 89, 101, 107, 113, 131, 137, 149, 167, 173, 179, 191, 197, 227, 233, ... A105875
−2 5, 7, 13, 23, 29, 37, 47, 53, 61, 71, 79, 101, 103, 149, 167, 173, 181, 191, 197, 199, 239, 263, 269, 271, 293, ... A105874
−1 2, 3
0 None
1 2
2 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, ... A001122
3 2, 5, 7, 17, 19, 29, 31, 43, 53, 79, 89, 101, 113, 127, 137, 139, 149, 163, 173, 197, 199, 211, 223, 233, 257, ... A019334
4 None
5 2, 3, 7, 17, 23, 37, 43, 47, 53, 73, 83, 97, 103, 107, 113, 137, 157, 167, 173, 193, 197, 223, 227, 233, 257, ... A019335
6 11, 13, 17, 41, 59, 61, 79, 83, 89, 103, 107, 109, 113, 127, 131, 137, 151, 157, 179, 199, 223, 227, 229, 233, ... A019336
7 2, 5, 11, 13, 17, 23, 41, 61, 67, 71, 79, 89, 97, 101, 107, 127, 151, 163, 173, 179, 211, 229, 239, 241, 257, ... A019337
8 3, 5, 11, 29, 53, 59, 83, 101, 107, 131, 149, 173, 179, 197, 227, 269, 293, 317, 347, 389, 419, 443, 461, 467, ... A019338
9 2
10 7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, ... A001913
11 2, 3, 13, 17, 23, 29, 31, 41, 47, 59, 67, 71, 73, 101, 103, 109, 149, 163, 173, 179, 197, 223, 233, 251, 277, ... A019339
12 5, 7, 17, 31, 41, 43, 53, 67, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, 223, 257, 269, 281, 283, ... A019340
13 2, 5, 11, 19, 31, 37, 41, 47, 59, 67, 71, 73, 83, 89, 97, 109, 137, 149, 151, 167, 197, 227, 239, 241, 281, 293, ... A019341
14 3, 17, 19, 23, 29, 53, 59, 73, 83, 89, 97, 109, 127, 131, 149, 151, 227, 239, 241, 251, 257, 263, 277, 283, 307, ... A019342
15 2, 13, 19, 23, 29, 37, 41, 47, 73, 83, 89, 97, 101, 107, 139, 149, 151, 157, 167, 193, 199, 227, 263, 269, 271, ... A019343
16 None
17 2, 3, 5, 7, 11, 23, 31, 37, 41, 61, 97, 107, 113, 131, 139, 167, 173, 193, 197, 211, 227, 233, 269, 277, 283, ... A019344
18 5, 11, 29, 37, 43, 53, 59, 61, 67, 83, 101, 107, 109, 139, 149, 157, 163, 173, 179, 181, 197, 227, 251, 269, ... A019345
19 2, 7, 11, 13, 23, 29, 37, 41, 43, 47, 53, 83, 89, 113, 139, 163, 173, 191, 193, 239, 251, 257, 263, 269, 281, ... A019346
20 3, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 103, 107, 113, 137, 157, 163, 167, 173, 223, 227, 233, 257, 263, 277, ... A019347
21 2, 19, 23, 29, 31, 53, 71, 97, 103, 107, 113, 137, 139, 149, 157, 179, 181, 191, 197, 223, 233, 239, 263, 271, ... A019348
22 5, 17, 19, 31, 37, 41, 47, 53, 71, 83, 107, 131, 139, 191, 193, 199, 211, 223, 227, 233, 269, 281, 283, 307, ... A019349
23 2, 3, 5, 17, 47, 59, 89, 97, 113, 127, 131, 137, 149, 167, 179, 181, 223, 229, 281, 293, 307, 311, 337, 347, ... A019350
24 7, 11, 13, 17, 31, 37, 41, 59, 83, 89, 107, 109, 113, 137, 157, 179, 181, 223, 227, 229, 233, 251, 257, 277, ... A019351
25 2
26 3, 7, 29, 41, 43, 47, 53, 61, 73, 89, 97, 101, 107, 131, 137, 139, 157, 167, 173, 179, 193, 239, 251, 269, 271, ... A019352
27 2, 5, 17, 29, 53, 89, 101, 113, 137, 149, 173, 197, 233, 257, 269, 281, 293, 317, 353, 389, 401, 449, 461, 509, ... A019353
28 5, 11, 13, 17, 23, 41, 43, 67, 71, 73, 79, 89, 101, 107, 173, 179, 181, 191, 229, 257, 263, 269, 293, 313, 331, ... A019354
29 2, 3, 11, 17, 19, 41, 43, 47, 73, 79, 89, 97, 101, 113, 127, 131, 137, 163, 191, 211, 229, 251, 263, 269, 293, ... A019355
30 11, 23, 41, 43, 47, 59, 61, 79, 89, 109, 131, 151, 167, 173, 179, 193, 197, 199, 251, 263, 281, 293, 307, 317, ... A019356
32 3, 5, 13, 19, 29, 37, 53, 59, 67, 83, 107, 139, 149, 163, 173, 179, 197, 227, 269, 293, 317, 347, 349, 373, 379, ... A019358
36 None
40 7, 11, 17, 19, 23, 29, 47, 59, 73, 97, 101, 103, 109, 131, 137, 139, 149, 167, 179, 193, 229, 233, 257, 263, ... A019365
48 5, 17, 19, 29, 31, 41, 43, 53, 67, 79, 89, 101, 103, 127, 137, 149, 151, 173, 197, 199, 211, 223, 233, 257, 269, ... A019373
50 3, 11, 13, 29, 37, 53, 59, 67, 83, 101, 107, 109, 131, 139, 149, 163, 173, 179, 181, 197, 227, 229, 269, 277, ... A019374
60 19, 23, 29, 41, 47, 73, 79, 83, 89, 97, 107, 149, 157, 167, 227, 263, 269, 313, 331, 337, 347, 373, 379, 383, ... A019384
64 None
72 5, 11, 13, 19, 29, 37, 43, 53, 59, 83, 101, 107, 109, 131, 139, 149, 157, 163, 173, 179, 197, 211, 227, 229, ... A019395
80 3, 7, 13, 17, 23, 47, 53, 67, 83, 97, 107, 113, 137, 157, 163, 167, 193, 197, 223, 227, 233, 257, 263, 277, 283, ... A019403
90 11, 17, 19, 23, 29, 47, 59, 97, 101, 113, 131, 137, 139, 149, 167, 179, 181, 193, 223, 229, 233, 251, 257, 263, ... A019412
96 7, 11, 17, 31, 37, 59, 61, 83, 89, 103, 107, 109, 113, 127, 131, 151, 157, 179, 181, 223, 227, 229, 233, 251, ... A019418
100 None

The smallest full-reptend primes in base n are:

2, 3, 2, 0, 2, 11, 2, 3, 2, 7, 2, 5, 2, 3, 2, 0, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 11, 2, 3, 2, 19, 2, 0, 2, 3, 2, 7, 2, 5, 2, 3, 2, 11, 2, 5, 2, 3, 2, 5, 2, 7, 2, 3, 2, 5, 2, 19, 2, 3, 2, 0, 2, 7, 2, 3, 2, 19, 2, 5, ... (sequence A056619 in OEIS)

Applications to cryptography

Binary full reptend prime sequences (also called maximum-length decimal sequences) have found cryptographic and error-correction coding applications. [2] In these applications repeating decimals to base 2 are generally used which gives rise to binary sequences. The maximum length binary sequence for $1/p$ (when 2 is a primitive root of p) is given by:[3]

$a(i) = 2^{i}~\bmod p ~\bmod 2$

These sequences of period p-1 have an autocorrelation function that has a negative peak of -1 for shift of (p-1)/2. The randomness of these sequences has been examined by diehard tests.[4]