17

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, ... (never stops, infinitude of primes)	divide and check
Fermat number, Fermat prime	$F_{2}$, where $F_{n}=2^{2^{n}}+1$, starts $n=0$	3,5,17,257,65537	plug and check
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] 71, 73, 79, 83, 89, 97, 107, 109, 113, 127, 137, 139, 151, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 239, 241, 251, 269, 277, 281, 313, 317, 331, 337, 349, 359, 367, 373, 383, 397, 419, 431 View list on OEIS

Structure of integers mod 17

Discrete logarithm

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

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 $a$, the primitive roots are $a,a^{3},a^{5},\dots ,a^{15}$, i.e., the odd powers of $a$. 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.

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.

Curiosities

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 $R(4,4)$ is at least 18.

Significance of 10 being a primitive root

If 10 is a primitive root modulo a prime $p$, then the prime $p$ is a full reptend prime in base 10, i.e., the decimal expansion of $1/p$ has a repeating block of the maximum possible length $p-1$. The condition holds for $p=17$, and the corresponding decimal expansion of 1/17 is:

$0\cdot {\overline {0588235294117647}}$

The corresponding number:

$\!0588235294117647$

has the property that it is a cyclic number, i.e., its first few multiples are obtained by cyclic permutations of its digits.