number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathe ...

, a full reptend prime, full repetend prime, proper primeDickson, Leonard E., 1952, ''History of the Theory of Numbers, Volume 1'', Chelsea Public. Co. or long prime in base ''b'' is an odd

prime number A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

''p'' such that the

Fermat quotient In number theory, the Fermat quotient of an integer ''a'' with respect to an odd prime ''p'' is defined as= 3/ref> The smallest solutions of ''q'p''(''a'') ≡ 0 (mod ''p'') with ''a'' = ''n'' are: :2, 1093, 11, 1093, 2, 66161, 5, 3, 2, 3, 71, ...

q_p(b) = \frac

(where ''p'' does not divide ''b'') gives a cyclic number. Therefore, the base ''b'' expansion of

1/p

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 In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bicond ...

''p'' is a full reptend prime. That is, the

multiplicative order In number theory, given a positive integer ''n'' and an integer ''a'' coprime to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n. In other words, the multiplicative order ...

= ''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 The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...

refers to these primes as "cyclic numbers".

Base 10

Base 10 The decimal numeral system (also called the base-ten positional numeral system and denary or decanary) is the standard system for denoting integer and non-integer numbers. It is the extension to non-integer numbers of the Hindu–Arabic numeral ...

may be assumed if no base is specified, in which case the expansion of the number is called a

repeating decimal A repeating decimal or recurring decimal is decimal representation of a number whose digits are periodic (repeating its values at regular intervals) and the infinitely repeated portion is not zero. It can be shown that a number is rational if a ...

. 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. (For such primes in base 10, see . 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 The duodecimal system (also known as base 12, dozenal, or, rarely, uncial) is a positional notation numeral system using twelve as its base. The number twelve (that is, the number written as "12" in the decimal numerical system) is instead writ ...

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'' 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 __NOTOC__ Year 223 ( CCXXIII) was a common year starting on Wednesday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Maximus and Aelianus (or, less frequently, year 976 ' ...

, 229,

233 __NOTOC__ Year 233 ( CCXXXIII) was a common year starting on Tuesday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Claudius and Paternus (or, less frequently, year 986 ...

257 __NOTOC__ Year 257 ( CCLVII) was a common year starting on Thursday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Valerianus and Gallienus (or, less frequently, year 10 ...

263 __NOTOC__ Year 263 ( CCLXIII) was a common year starting on Thursday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Albinus and Dexter (or, less frequently, year 1016 '' ...

269 Year 269 ( CCLXIX) was a common year starting on Friday (link will display the full calendar) of the Julian calendar. At the time, it was known as the Year of the Consulship of Claudius and Paternus (or, less frequently, year 1022 ''Ab urbe con ...

, 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, ... 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 Not all values of ''p'' will yield a cyclic number using this formula; for example, ''p'' = 13 gives 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 Algebraic number theory is a branch of number theory that uses the techniques of abstract algebra to study the integers, rational numbers, and their generalizations. Number-theoretic questions are expressed in terms of properties of algebraic ob ...

, specifically, this sequence is the set of primes ''p'' such that 10 is a primitive root modulo ''p''.

Artin's conjecture on primitive roots In number theory, Artin's conjecture on primitive roots states that a given integer ''a'' that is neither a square number nor −1 is a primitive root modulo infinitely many primes ''p''. The conjecture also ascribes an asymptotic density to th ...

is that this sequence contains 37.395...% of the primes.

Patterns of occurrence of full reptend primes

Advanced

modular arithmetic In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his bo ...

can show that any prime of the following forms: #40''k'' + 1 #40''k'' + 3 #40''k'' + 9 #40''k'' + 13 #40''k'' + 27 #40''k'' + 31 #40''k'' + 37 #40''k'' + 39 can ''never'' be a full reptend prime in base 10. The first primes of these forms, with their periods, are: However, studies show that ''two-thirds'' of primes of the form 40''k'' + ''n'', where ''n'' ∈ 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 120''k'' + 23 below 100000 are full reptend primes, with 20903 being the first that is not full reptend.

Binary 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, ... For these primes, 2 is a primitive root modulo ''p'', so 2^''n'' modulo ''p'' can be any

natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...

between 1 and ''p'' − 1. :

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 The diehard tests are a battery of statistical tests for measuring the quality of a random number generator. They were developed by George Marsaglia over several years and first published in 1995 on a CD-ROM of random numbers. Test overview ; Bi ...

. All of them are of form 8''k'' + 3 or 8''k'' + 5, because if ''p'' = 8''k'' + 1 or 8''k'' + 7, then 2 is a

quadratic residue In number theory, an integer ''q'' is called a quadratic residue modulo ''n'' if it is congruent to a perfect square modulo ''n''; i.e., if there exists an integer ''x'' such that: :x^2\equiv q \pmod. Otherwise, ''q'' is called a quadratic n ...

modulo ''p'', so ''p'' divides

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 prime In number theory, a prime number ''p'' is a if 2''p'' + 1 is also prime. The number 2''p'' + 1 associated with a Sophie Germain prime is called a . For example, 11 is a Sophie Germain prime and 2 × 11 + ...

s congruent to 3 modulo 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, 1523, 1619, 1907, etc. (less than 2000). Binary full reptend prime sequences (also called maximum-length decimal sequences) have found

cryptographic Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...

and error-correction coding applications. 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:Kak, Subhash, "Encryption and error-correction using d-sequences". IEEE Trans. On Computers, vol. C-34, pp. 803–809, 1985. The following is a list about the periods (in binary) to the primes congruent to 1 or 7 (mod 8): (less than 1000) ''None'' of them are binary full reptend primes. The binary period of ''n''-th 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) The binary period level of ''n''-th 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, ... However, studies show that ''three-fourths'' of primes of the form 8''k'' + ''n'', where ''n'' ∈ are full reptend primes in base 2 (For example, there are 87 primes below 1000 congruent to 3 or 5 modulo 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, 1078 of the 1206 primes of form 24''k'' + 5 below 100000 are full reptend primes in base 2, with 1013 being the first that is not full reptend in base 2.

''n''-th level reptend prime

An ''n''-th level reptend prime is a prime ''p'' having ''n'' different cycles in expansions of

\frac

(''k'' is an

integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...

, 1 ≤ ''k'' ≤ ''p''−1). In base 10, smallest ''n''-th level reptend prime are :7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289, 859, 239, 27581, 9613, 18131, 13757, 33931, 9161, 118901, 6763, 18233, 1409, 88741, 4003, 5171, 19489, 86143, 23201, ... In base 2, smallest ''n''-th level reptend prime are :3, 7, 43, 113, 251, 31, 1163, 73, 397, 151, 331, 1753, 4421, 631, 3061, 257, 1429, 127, 6043, 3121, 29611, 1321, 18539, 601, 15451, 14327, 2971, 2857, 72269, 3391, 683, 2593, 17029, 2687, 42701, 11161, 13099, 1103, 71293, 13121, 17467, 2143, 83077, 25609, 5581, 5153, 26227, 2113, 51941, 2351, ...

Full reptend primes in various bases

Artin also

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 1 ...

d: * There are infinitely many full-reptend primes in all bases except

square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length ad ...

s. * Full-reptend primes in all bases except

perfect power In mathematics, a perfect power is a natural number that is a product of equal natural factors, or, in other words, an integer that can be expressed as a square or a higher integer power of another integer greater than one. More formally, ''n'' ...

s and numbers whose

squarefree In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, is square-f ...

part are congruent to 1 modulo 4 comprise 37.395...% of all primes. (See ) 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, 2, 3, 2, 13, 2, 5, 2, 3, 2, 5, 2, 11, 2, 3, 2, 5, 2, 11, 2, 3, 2, 7, 2, 7, 2, 3, 2, 0, ...

References