Difference between revisions of "7"
(→Quadratic theory) |
(→Properties and families) |
||
| (14 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
! Property or family !! Parameter values !! First few numbers !! Proof of satisfaction/membership/containment | ! Property or family !! Parameter values !! First few numbers !! Proof of satisfaction/membership/containment | ||
|- | |- | ||
| − | | [[satisfies property::prime number]] || fourth prime number || {{#lst:prime number|list}} || divide and check | + | | [[satisfies property::prime number]] || fourth prime number || {{#lst:prime number|list}} || {{divide and check up to sqrt}} In this case, since <math>\sqrt{7}</math> is between 2 and 3, verifying primality requires verifying that 7 is not divisible by any prime up to 2, i.e., it is not divisible by [[2]]. |
|- | |- | ||
| [[satisfies property::Mersenne number]] <math>M_n = 2^n - 1</math> || <math>n = 3</math>, i.e., <math>M_3 = 2^3 - 1</math> || {{#lst:Mersenne number|list}} || plug and check | | [[satisfies property::Mersenne number]] <math>M_n = 2^n - 1</math> || <math>n = 3</math>, i.e., <math>M_3 = 2^3 - 1</math> || {{#lst:Mersenne number|list}} || plug and check | ||
| Line 22: | Line 22: | ||
| [[satisfies property::regular prime]] || third regular prime || {{#lst:regular prime|list}} || | | [[satisfies property::regular prime]] || third regular prime || {{#lst:regular prime|list}} || | ||
|- | |- | ||
| − | | [[satisfies property::twin | + | | [[satisfies property::twin primes]] (greater member of pair) || second greater member twin prime || {{#lst:twin primes|list-greater}} || 7 - 2 = [[5]] is prime |
| + | |- | ||
| + | | [[satisfies property::Euclid number]] (number of the form [[primorial]] + 1) || 1 more than the second primorial || {{#lst:Euclid number|list}} || <math>7 = (2 \cdot 3) + 1</math> | ||
| + | |- | ||
| + | | [[satisfies property::factorial prime]] (prime that is a factorial <math>\pm 1</math>) || <math>3! + 1</math> || {{#lst:factorial prime|list}} || <math>7 = 3! + 1</math> | ||
|} | |} | ||
| Line 34: | Line 38: | ||
{| class="sortable" border="1" | {| class="sortable" border="1" | ||
| − | ! Congruence class mod 7 (written as smallest positive integer) !! Congruence class mod 7 (written as smallest magnitude integer) !! Discrete logarithm to base 3, written as integer mod 6 !! Is it a [[primitive root]] mod 7 (if and only if the discrete log is relatively prime to 6)? !! Is it | + | ! Congruence class mod 7 (written as smallest positive integer) !! Congruence class mod 7 (written as smallest magnitude integer) !! Discrete logarithm to base 3, written as integer mod 6 !! Is it a [[primitive root]] mod 7 (if and only if the discrete log is relatively prime to 6)? !! Is it a quadratic residue or nonresidue mod 7 (residue if discrete log is even, nonresidue if odd) |
|- | |- | ||
| 1 || 1 || 0 || No || [[quadratic residue]] | | 1 || 1 || 0 || No || [[quadratic residue]] | ||
| Line 47: | Line 51: | ||
|- | |- | ||
| 6 || -1 || 3 || No || [[quadratic nonresidue]] | | 6 || -1 || 3 || No || [[quadratic nonresidue]] | ||
| + | |- | ||
| + | ! -- !! -- !! -- !! Total: 2 Yes, 4 No<br><math>2 = \varphi(6)</math>, <math>\varphi</math> is [[Euler totient function]] !! Total: 3 residues, 3 nonresidues. Equal number of both | ||
|} | |} | ||
| Line 52: | Line 58: | ||
{| class="sortable" border="1" | {| class="sortable" border="1" | ||
| − | ! Congruence class mod 7 (written as smallest positive integer) !! Congruence class mod 7 (written as smallest magnitude integer) !! Discrete logarithm to base 5, written as integer mod 6 !! Is it a [[primitive root]] mod 7 (if and only if the discrete log is relatively prime to 6)? !! Is it | + | ! Congruence class mod 7 (written as smallest positive integer) !! Congruence class mod 7 (written as smallest magnitude integer) !! Discrete logarithm to base 5, written as integer mod 6 !! Is it a [[primitive root]] mod 7 (if and only if the discrete log is relatively prime to 6)? !! Is it a quadratic residue or nonresidue mod 7 (residue if discrete log is even, nonresidue if odd) |
|- | |- | ||
| 1 || 1 || 0 || No || [[quadratic residue]] | | 1 || 1 || 0 || No || [[quadratic residue]] | ||
| Line 65: | Line 71: | ||
|- | |- | ||
| 6 || -1 || 3 || No || [[quadratic nonresidue]] | | 6 || -1 || 3 || No || [[quadratic nonresidue]] | ||
| + | |- | ||
| + | ! -- !! --!! --!! Total: 2 Yes, 4 No<br><math>2 = \varphi(6)</math>, <math>\varphi</math> is [[Euler totient function]] !! Total: 3 residues, 3 nonresidues. Equal number of both | ||
|} | |} | ||
| + | |||
| + | ===Orders of elements=== | ||
| + | |||
| + | The order of <math>a</math> mod 7 is the smallest positive integer <math>m</math> such that <math>a^m \equiv 1 \pmod 7</math>. | ||
| + | |||
| + | The order of any element of the multiplicative group is the order of its discrete log in the corresponding additive group, i.e., we have: | ||
| + | |||
| + | <math>\operatorname{ord}(x) = \frac{6}{\operatorname{gcd}(6,\log x)}</math> | ||
| + | |||
| + | where <math>\log</math> represents any discrete logarithm. The orders of elements are given below usin discrete logs to base 3: | ||
| + | |||
| + | {| class="sortable" border="1" | ||
| + | ! Congruence class mod 7 (written as smallest positive integer) !! Congruence class mod 7 (written as smallest magnitude integer) !! Discrete logarithm to base 3, written as integer mod 6 !! Order of element | ||
| + | |- | ||
| + | | 1 || 1 || 0 || 1 | ||
| + | |- | ||
| + | | 2 || 2 || 2 || 3 | ||
| + | |- | ||
| + | | 3 || 3 || 1 || 6 | ||
| + | |- | ||
| + | | 4 || -3 || 4 || 3 | ||
| + | |- | ||
| + | | 5 || -2 || 5 || 6 | ||
| + | |- | ||
| + | | 6 || -1 || 3 || 2 | ||
| + | |} | ||
| + | |||
| + | ==Primitive root theory== | ||
===Primitive roots=== | ===Primitive roots=== | ||
| Line 72: | Line 108: | ||
Explicitly, the primitive roots are 3 and 5 (= -2). | Explicitly, the primitive roots are 3 and 5 (= -2). | ||
| + | |||
| + | ===Significance of 10 being a primitive root=== | ||
| + | |||
| + | {{base 10-specific observation}} | ||
| + | |||
| + | If 10 is a primitive root modulo a prime <math>p</math>, then the prime <math>p</math> is a [[full reptend prime]] in base 10, i.e., the decimal expansion of <math>1/p</math> has a repeating block of the maximum possible length <math>p - 1</math>. The condition holds for <math>p = 7</math> (note that <math>10 \equiv 3 \pmod 7</math> and 3 is a primitive root), and the corresponding decimal expansion of 1/7 is: | ||
| + | |||
| + | <math>0 \cdot \overline{142857}</math> | ||
| + | |||
| + | The corresponding number: | ||
| + | |||
| + | <math>\! 142857</math> | ||
| + | |||
| + | has the property that it is a [[cyclic number]], i.e., its product with any of the numbers from 1 to 6 is obtained by cyclically permuting its digits. | ||
==Quadratic theory== | ==Quadratic theory== | ||
| Line 80: | Line 130: | ||
Explicitly, the quadratic residues are 1,2,4 and the quadratic nonresidues are 3,5,6. | Explicitly, the quadratic residues are 1,2,4 and the quadratic nonresidues are 3,5,6. | ||
| + | |||
| + | If we also choose to include 0, the quadratic residues are 0,1,2,4 and the quadratic nonresidues are 3,5,6. | ||
===Adjacent quadratic residues=== | ===Adjacent quadratic residues=== | ||
| Line 99: | Line 151: | ||
By [[Dirichlet's theorem on arithmetic progressions]], we thus find that there are infinitely many primes <math>p</math> for which 7 is a quadratic residue and infinitely many primes <math>p</math> for which 7 is a quadratic nonresidue. | By [[Dirichlet's theorem on arithmetic progressions]], we thus find that there are infinitely many primes <math>p</math> for which 7 is a quadratic residue and infinitely many primes <math>p</math> for which 7 is a quadratic nonresidue. | ||
| − | == | + | ==Cyclotomic theory== |
| − | === | + | ===Cyclotomic extension of primitive roots of unity=== |
| − | + | {{fillin}} | |
| − | === | + | ===Constructibility of regular 7-gon=== |
| − | + | 7 is the smallest prime <math>p</math> for which the regular <math>p</math>-gon is ''not'' constructible by straightedge and compass. In fact, it is the smallest natural number <math>n</math> for which the regular <math>n</math>-gon is not constructible by straightedge and compass. This can be seen by noting that the cyclotomic extension of adjoining 7th roots is a degree six Galois extension and cannot be expressed using successive quadratic extensions. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
Latest revision as of 17:35, 3 July 2012
This article is about a particular natural number.|View all articles on particular natural numbers
Contents
Summary
Factorization
The number 7 is a prime number.
Properties and families
| Property or family | Parameter values | First few numbers | Proof of satisfaction/membership/containment |
|---|---|---|---|
| prime number | fourth prime number | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, [SHOW MORE]View list on OEIS | A natural number  is prime if and only if  is not divisible by any prime less than or equal to  . In this case, since  is between 2 and 3, verifying primality requires verifying that 7 is not divisible by any prime up to 2, i.e., it is not divisible by 2.
|
Mersenne number  |
 , i.e.,  |
plug and check | |
| Mersenne prime (both a prime number and a Mersenne number) | same as for Mersenne number | combine above | |
| safe prime (odd prime such that half of that minus one is also prime) | second safe prime | 5, 7, 11, 23, 47, 59, 83, 107, 167, [SHOW MORE]View list on OEIS | plug and check  is prime.
|
| regular prime | third regular prime | 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 61, [SHOW MORE]View list on OEIS | |
| twin primes (greater member of pair) | second greater member twin prime | 5, 7, 13, 19, 31, 43, 61, 73, 103, [SHOW MORE]View list on OEIS | 7 - 2 = 5 is prime |
| Euclid number (number of the form primorial + 1) | 1 more than the second primorial | 2, 3, 7, 31, 211, 2311, View list on OEIS | 
|
factorial prime (prime that is a factorial  ) |
 |
2, 3, 5, 7, 23, 719, 5039, [SHOW MORE] View list on OEIS | 
|
Structure of integers mod 7
Discrete logarithm
Template:Discrete log facts to check against
3 is a primitive root mod 7, so we can take that as the base of the discrete logarithm. We thus get an explicit bijection from the additive group of integers mod 6 to the multiplicative group of nonzero congruence classes mod 7, given by 
. The inverse of that mapping is the discrete logarithm, i.e., the discrete logarithm of is 
means 
:
| Congruence class mod 7 (written as smallest positive integer) | Congruence class mod 7 (written as smallest magnitude integer) | Discrete logarithm to base 3, written as integer mod 6 | Is it a primitive root mod 7 (if and only if the discrete log is relatively prime to 6)? | Is it a quadratic residue or nonresidue mod 7 (residue if discrete log is even, nonresidue if odd) |
|---|---|---|---|---|
| 1 | 1 | 0 | No | quadratic residue |
| 2 | 2 | 2 | No | quadratic residue |
| 3 | 3 | 1 | Yes | quadratic nonresidue |
| 4 | -3 | 4 | No | quadratic residue |
| 5 | -2 | 5 | Yes | quadratic nonresidue |
| 6 | -1 | 3 | No | quadratic nonresidue |
| -- | -- | -- | Total: 2 Yes, 4 No ,  is Euler totient function |
Total: 3 residues, 3 nonresidues. Equal number of both |
Alternatively, we could take discrete logs to base 5, which is the other primitive root. This is simply the negative of the other discrete log:
| Congruence class mod 7 (written as smallest positive integer) | Congruence class mod 7 (written as smallest magnitude integer) | Discrete logarithm to base 5, written as integer mod 6 | Is it a primitive root mod 7 (if and only if the discrete log is relatively prime to 6)? | Is it a quadratic residue or nonresidue mod 7 (residue if discrete log is even, nonresidue if odd) |
|---|---|---|---|---|
| 1 | 1 | 0 | No | quadratic residue |
| 2 | 2 | 4 | No | quadratic residue |
| 3 | 3 | 5 | Yes | quadratic nonresidue |
| 4 | -3 | 2 | No | quadratic residue |
| 5 | -2 | 1 | Yes | quadratic nonresidue |
| 6 | -1 | 3 | No | quadratic nonresidue |
| -- | -- | -- | Total: 2 Yes, 4 No, is Euler totient function |
Total: 3 residues, 3 nonresidues. Equal number of both |
Orders of elements
The order of 
mod 7 is the smallest positive integer such that 
.
The order of any element of the multiplicative group is the order of its discrete log in the corresponding additive group, i.e., we have:
where 
represents any discrete logarithm. The orders of elements are given below usin discrete logs to base 3:
| Congruence class mod 7 (written as smallest positive integer) | Congruence class mod 7 (written as smallest magnitude integer) | Discrete logarithm to base 3, written as integer mod 6 | Order of element |
|---|---|---|---|
| 1 | 1 | 0 | 1 |
| 2 | 2 | 2 | 3 |
| 3 | 3 | 1 | 6 |
| 4 | -3 | 4 | 3 |
| 5 | -2 | 5 | 6 |
| 6 | -1 | 3 | 2 |
Primitive root theory
Primitive roots
The number of primitive roots equals the number of generators of the additive group of integers modulo 6 (= 7 - 1) which is the Euler totient function of 6, which is 2. If is a primitive root, the primitive roots are and 
.
Explicitly, the primitive roots are 3 and 5 (= -2).
Significance of 10 being a primitive root
Template:Base 10-specific observation
If 10 is a primitive root modulo a prime 
, then the prime is a full reptend prime in base 10, i.e., the decimal expansion of 
has a repeating block of the maximum possible length 
. The condition holds for 
(note that 
and 3 is a primitive root), and the corresponding decimal expansion of 1/7 is:
The corresponding number:
has the property that it is a cyclic number, i.e., its product with any of the numbers from 1 to 6 is obtained by cyclically permuting its digits.
Quadratic theory
Quadratic residues and nonresidues
Of the six congruence classes of invertible elements mod 7, three are quadratic residues and three are quadratic nonresidues. If is a primitive root, the quadratic nonresidues are 
, and the quadratic residues are 
. Alternatively, we can obtain the quadratic residues by taking the congruence classes of 
.
Explicitly, the quadratic residues are 1,2,4 and the quadratic nonresidues are 3,5,6.
If we also choose to include 0, the quadratic residues are 0,1,2,4 and the quadratic nonresidues are 3,5,6.
Adjacent quadratic residues
Fill this in later
Condition for 7 to be a quadratic residue modulo a prime
Whether or not 7 is a quadratic residue modulo a given prime depends only on the congruence class of that prime modulo 28. This follows from quadratic reciprocity (applicable only to odd primes, but the case of 2 is isolated), which states that:
We note that 
depends only on the congruence class of mod 7, and the right side depends only on the congruence class of mod 4. Thus, 
depends only on the congruence class of mod 28.
The full list is below:
Fill this in later
By Dirichlet's theorem on arithmetic progressions, we thus find that there are infinitely many primes for which 7 is a quadratic residue and infinitely many primes for which 7 is a quadratic nonresidue.
Cyclotomic theory
Cyclotomic extension of primitive roots of unity
Fill this in later
Constructibility of regular 7-gon
7 is the smallest prime for which the regular -gon is not constructible by straightedge and compass. In fact, it is the smallest natural number for which the regular -gon is not constructible by straightedge and compass. This can be seen by noting that the cyclotomic extension of adjoining 7th roots is a degree six Galois extension and cannot be expressed using successive quadratic extensions.
