17
This article is about a particular natural number.|View all articles on particular natural numbers
Contents
Summary
Factorization
The number 17 is a prime number.
Properties and families
Property or family | Parameter values | First few numbers | Proof of satisfaction/membership/containment |
---|---|---|---|
prime number | it is the 7th 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 . Since is between 4 and 5, we only need to check divisibility by primes less than or equal to 4, i.e., we need to verify that 17 is not divisible by the primes 2 and 3. |
Fermat number, Fermat prime | , where , starts | 3, 5, 17, 257, 65537, 4294967297 View list on OEIS | plug and check |
Proth prime: prime of the form with | 3, 5, 13, 17, 41, 97, 113, [SHOW MORE]View list on OEIS | ||
regular prime | sixth regular prime (2 is neither regular nor irregular) | 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 61, [SHOW MORE]View list on OEIS | |
near-square prime of the form | (third prime of this form) | 2, 5, 17, 37, 101, 197, 257, [SHOW MORE]View list on OEIS | |
lucky number of Euler | fifth of six such numbers | 2, 3, 5, 11, 17, 41 View list on OEIS | A prime is a lucky number of Euler iff the ring of integers in is a unique factorization domain. |
Structure of integers mod 17
Discrete logarithm
Template:Discrete log facts to check against
We can take 3 to be a primitive root mod 17, i.e., a generator for the multiplicative group of integers mod 17. With this, the discrete logarithm table from the multiplicative group mod 17 to the additive group mod 16 looks as follows:
Congruence class mod 17 (written as smallest positive integer) | Congruence class mod 17 (written as smallest magnitude integer) | Discrete logarithm to base 3, written as integer mod 16 | Is it a primitive root mod 17 (if and only if the discrete log is relatively prime to 16)? | Is it a quadratic residue or nonresidue mod 17 (residue if discrete log is even, nonresidue if odd)? |
---|---|---|---|---|
1 | 1 | 0 | No | quadratic residue |
2 | 2 | 14 | No | quadratic residue |
3 | 3 | 1 | Yes | quadratic nonresidue |
4 | 4 | 12 | No | quadratic residue |
5 | 5 | 5 | Yes | quadratic nonresidue |
6 | 6 | 15 | Yes | quadratic nonresidue |
7 | 7 | 11 | Yes | quadratic nonresidue |
8 | 8 | 10 | No | quadratic residue |
9 | -8 | 2 | No | quadratic residue |
10 | -7 | 3 | Yes | quadratic nonresidue |
11 | -6 | 7 | Yes | quadratic nonresidue |
12 | -5 | 13 | Yes | quadratic nonresidue |
13 | -4 | 4 | No | quadratic residue |
14 | -3 | 9 | Yes | quadratic nonresidue |
15 | -2 | 6 | No | quadratic residue |
16 | -1 | 8 | No | quadratic residue |
-- | -- | -- | 8 Yes, 8 No , is Euler totient function |
8 residues, 8 nonresidues. Equal numbers of both. |
Primitive root theory
Primitive roots
The number of primitive roots equals the number of generators of the additive group of integers mod 16, which is the Euler totient function of 16, which is 8. Given any primitive root , the primitive roots are , i.e., the odd powers of . 17 is a Fermat prime so the primitive roots are precisely the quadratic nonresidues, see quadratic nonresidue equals primitive root for Fermat prime.
The explicit list of primitive roots is: 3,5,6,7,10,11,12,14.
We note the following:
- The fact that 3 is a primitive root follows from the fact that Fermat prime greater than three implies three is primitive root.
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 , and the corresponding decimal expansion of 1/17 is:
The corresponding number:
has the property that it is a cyclic number, i.e., its first few multiples are obtained by cyclic permutations of its digits.
Quadratic theory
Quadratic residues and nonresidues
As noted above, the quadratic nonresidues coincide with the primitive roots and the quadratic residues are the remaining elements.
The quadratic residues are: 1,2,4,8,9,13,15,16.
The quadratic nonresidues are: 3,5,6,7,10,11,12,14.
Adjacent quadratic residues
Further information: Formula for number of pairs of adjacent quadratic residues modulo a prime
For a prime that is congruent to 1 mod 4, the number of pairs of adjacent squares mod is and the number of adjacent (both nonzero) quadratic residues is . For , these numbers are respectively 5 and 3.
The 3 pairs of adjacent quadratic residues for 17 are: (1,2), (8,9), and (-2,-1) (which is the same as (15,16).
If we allow for 0 as one of the pair members, the 5 pairs of adjacent squares are: (0,1), (1,2), (8,9), and (-2,-1), and (-1,0).
Paley graph and Ramsey theory
The structure of quadratic residues are nonresidues for the prime 17 has a combinatorial significance. Specifically, consider the Paley graph of integers mod 17, defined as the graph on the integers mod 17 where two vertices are connected if their difference is a quadratic residue mod 17. This is a self-complementary graph and it does not have a clique of size four, hence it can be used to show that the Ramsey number is at least 18.
Condition for 17 to be a quadratic residue modulo a prime
Whether or not 17 is a quadratic residue modulo a prime depends only on the congruence class of the prime modulo 68 (obtainedas 4 times 17). This follows from quadratic reciprocity for odd primes.
By Dirichlet's theorem on primes in arithmetic progressions, we thus find that there are infinitely many primes for which 17 is a quadratic residue and infinitely many primes for which 17 is a quadratic nonresidue.
Square roots of -1
Since , -1 has a square root mod 17. Its two square roots mod 17 are 4 and -4 (which is 13 mod 17).
We can also see this from the fact that , and that the square roots of -1 mod are .
Waring representations
Sums of squares
Template:Square sums facts to check against
Item | Value |
---|---|
unique (up to plus/minus and ordering) representation as sum of two squares | . Note that existence and uniqueness both follow from it being a prime that is 1 mod 4. This also corresponds to the factorization in the ring of Gaussian integers . |
representations as sum of three squares (up to ordering and plus/minus equivalence) | |
Sums of cubes
Item | Value |
---|---|
representation as sum of two cubes | not possible, because is not possible |
representation as sum of three cubes | is the only one using nonnegative inputs. |
representation as sum of four cubes | none using nonnegative inputs. Using both positive and negative inputs: |
Sums of fourth powers
Item | Value |
---|---|
representation as sum of two fourth powers |
Cyclotomic theory
Cyclotomic extension of primitive roots of unity
Fill this in later
Constructibility of 17-gon
17 is a Fermat prime, hence the regular 17-gon is constructible by straightedge and compass. This is because the cyclotomic extension of adjoining 17th roots of unity can be obtained by taking successive quadratic extensions.
Polynomials
Prime-generating polynomials
Below are some polynomials that give prime numbers for small input values, which give the value 17 for suitable input choice.
Polynomial | Degree | Some values for which it generates primes | Input value at which it generates 17 |
---|---|---|---|
2 | all numbers 1,2,3,4, because 5 is one of the lucky numbers of Euler. | 4 | |
2 | all numbers 1-10, because 11 is one of the lucky numbers of Euler. | 3 | |
2 | all numbers 1-16, because 17 is one of the lucky numbers of Euler. | 1 |
Irreducible polynomials by Cohn's irreducibility criterion
By Cohn's irreducibility criterion, we know that if we write 17 in any base greater than or equal to 2, the corresponding polynomial is irreducible. We list here all the irreducible polynomials:
Base | 17 in base | Corresponding irreducible polynomial |
---|---|---|
2 | 10001 | |
3 | 122 | |
4 | 101 | |
5 | 32 | |
6 | 25 | |
7 | 23 | |
8 | 21 | |
9 | 18 | |
10 | 17 | |
11 | 16 | |
12 | 15 | |
13 | 14 | |
14 | 13 | |
15 | 12 | |
16 | 11 |
Multiples
Interesting multiples
Number | Prime factorization | What's interesting about it |
---|---|---|
561 | 3 times 11 times 17 | smallest Carmichael number, i.e., smallest absolute pseudoprime |
1105 | 5 times 13 times 17 | second Carmichael number, i.e., second absolute pseudoprime |
2465 | 5 times 17 times 29 | fourth Carmichael number, i.e., fourth absolute pseudoprime |