Let p
be a prime greater than 2, n a
natural number such that n≤p-2, and
a

(1) The congruence x

(Also, if a

U

There also exists an alternate U

(2) U

As will be shown, a

(3) The congruence x

As will be shown, V

(4) a

(5) V

is divisible by p. Denote this matrix by C. In order that it have at least k distinct real roots it is necessary that all p-k rowed minors of C be divisible by p. If also not all p-k-1 rowed minors are divisible by p, the congruence has exactly k distinct real roots. Kronecker's version of König's theorem will also be used in the proof. Kronecker's version is this; f(x)≡0(mod p) has exactly k roots if and only if the rank of C is exactly p-1-k.

Fermat's theorem is essential to the formulation of König's theorem. If f(x)≡0(mod p) has a root, then this root is also a root of x

by A. Then since U

by R. R(-U

(This is the matrix obtained from A by deleting its first n-1 columns and last n-1 rows.) Therefore B

Since p divides all p-n rowed minors of A, p divides all j rowed minors of A where j≥p-n. Therefore p divides the determinant of the (p-n+1)x(p-n+1) matrix

(This is the matrix obtained from A by deleting its first n-2 columns and last n-2 rows.) p divides the row 1, column 1 cofactor of this matrix (since p divides all p-n rowed minors of A), therefore p divides the determinant of the matrix obtained from the above matrix by changing the row 1, column 1 element to a zero. Denote this matrix by B

The proofs that U

Denote this matrix by B

(6) If U

Suppose U

(7) If i≠0, U

ζ

by T. Therefore T(V

(8) V

Also, V

(9) a

Finally, Theorem (3) will be proved. If U

Comptes Rendus Paris, 82, 1876, pp. 1303-5.

J. König

Jour. für Math., 99, 1886, 258-260; Math. Termes Ertesito, Magyar Tudon Ak., Budapest, 1, 1883, 296; 3, 1885, 178.

L. Kronecker

Jour. für Math., 99, 1886, 363, 366.

_{1}, a_{2}, a_{3}, ..., a_{n}integers. Let the U series be defined by the recurrence relation U_{i}+a_{1}U_{i-1}+a_{2}U_{i-2}+...+a_{n}U_{i-n}=0 where i=1, 2, 3, ..., U_{0}=1, and U_{i}=0 if i<0. The principal subject here is the proof of the following theorem;(1) The congruence x

^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}≡0(mod p), 0<x<p, has n roots if and only if U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ....(Also, if a

_{1}, a_{2}, a_{3}, ..., a_{n}are elements of a Galois field, then the equation x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}=0 has n roots if and only if U_{O+i-n}=U_{i-n}, i=1, 2, 3, ..., where O is the order of the Galois field.) Only n where n≤p-2 are considered since a mod p congruence of arbitrary degree can be reduced to degree p-2 or less by using Fermat's theorem that x^{p-1}≡1(mod p) if p does not divide x. As will be shown, If U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ..., n, then U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, .... This result combined with Theorem (1) gives a practical means of determining for which p a given nth degree congruence has n roots. (The same U series applies for all p such that n≤p-2.) For example, some U values corresponding to the congruence x^{3}-x^{2}-x+2≡0(mod p), 0<x<p, are;U_{1}=1 |
U_{2}=2 |
U_{3}=1 |
U_{4}=1 |
U_{5}=-2 |
U_{6}=-3 |
U_{7}=-7 |
U_{8}=-6 |

U_{9}=-7 |
U_{10}=1 |
U_{11}=6 |
U_{12}=21 |
U_{13}=25 |
U_{14}=34 |
U_{15}=17 |
U_{16}=1 |

U

_{16}≡1(mod 17) and U_{15}≡U_{14}≡0(mod 17), therefore this congruence has three roots if p=17. Also, this congruence does not have three roots for any p such that 5≤p<17.#### Relationship of U Series to Fibonacci Numbers

If n=2 and a_{1}=a_{2}=-1, then U_{i}is the (i+1)th Fibonacci number. (From the perspective here, the Fibonacci numbers are indexed improperly.) Alternately, the ith Fibonacci number can be defined to be equal to (ζ_{1}^{i}-ζ_{2}^{i})/(ζ_{1}-ζ_{2}) where ζ_{1}, ζ_{2}are the roots of ζ^{2}-ζ-1=0. A well known result is that p divides the (p-1)th Fibonacci number if and only if 5 (the discriminant of the equation ζ^{2}-ζ-1=0) is a quadratic residue of p. The congruence x^{2}-x-1≡0(mod p), 0<x<p, has two roots if and only if 5 is a quadratic residue of p. Theorem (1) is a generalization of these results.There also exists an alternate U

_{i}definition;(2) U

_{i}, i≥0, equals ∑ζ_{1}^{e1}ζ_{2}^{e2}ζ_{3}^{e3}···ζ_{n}^{en}where ζ_{1}, ζ_{2}, ζ_{3}, ..., ζ_{n}are the roots of ζ^{n}+a_{1}ζ^{n-1}+a_{2}ζ^{n-2}+...+a_{n}=0 and the summation is over all combinations of non-negative integers e_{1}, e_{2}, e_{3}, ..., e_{n}such that e_{1}+e_{2}+e_{3}+...+e_{n}=i.As will be shown, a

_{1}(U_{p-1}-1)+2a_{2}U_{p-2}+3a_{3}U_{p-3}+...+na_{n}U_{p-n}≡0(mod p). Therefore if n>1 and p does not divide a_{1}a_{2}a_{3}···a_{n}, the congruence to zero of any group of n-1 of U_{p-1}-1, U_{p-2}, U_{p-3}, ..., U_{p-n}implies the congruence to zero of all of U_{p-1}-1, U_{p-2}, U_{p-3}, ..., U_{p-n}. This result is of special significance in the case n=2. If n=2, a property of the U series is U_{p-1}≡(a_{1}^{2}-4a_{2})^{(p-1)/2}(mod p) (since if n=2, U_{p-1}=(ζ_{1}^{p}-ζ_{2}^{p})/(ζ_{1}-ζ_{2}), (ζ_{1}^{p}-ζ_{2}^{p})/(ζ_{1}-ζ_{2})≡(ζ_{1}-ζ_{2})^{p}/(ζ_{1}-ζ_{2})(mod p), and (ζ_{1}-ζ_{2})^{2}=[-(ζ_{1}+ζ_{2})]^{2}-4ζ_{1}ζ_{2}=a_{1}^{2}-4a_{2}). Therefore U_{p-1}≡1(mod p) where n=2 if and only if a_{1}^{2}-4a_{2}is a quadratic residue of p. If U_{p-1}≡1(mod p) and U_{p-2}≡0(mod p) where n=2, then p does not divide a_{2}(since by the recurrence relation, U_{p-2}=(-a_{1})^{p-2}+k_{1}a_{2}and U_{p-1}=(-a_{1})^{p-1}+k_{2}a_{2}where k_{1}, k_{2}are integers). Conversely, if a_{1}^{2}-4a_{2}is a quadratic residue of p and p does not divide a_{2}where n=2, then U_{p-1}≡1(mod p) and U_{p-2}≡0(mod p) (since a_{1}(U_{p-1}-1)+2a_{2}U_{p-2}≡0(mod p)). Therefore U_{p-1}≡1, U_{p-2}≡0(mod p) where n=2 if and only if a_{1}^{2}-4a_{2}is a quadratic residue of p and p does not divide a_{2}. This shows the equivalence of Theorem (1) in the case n=2 with the familiar result that the congruence x^{2}+a_{1}x+a_{2}≡0(mod p), 0<x<p, has two roots if and only if a_{1}^{2}-4a_{2}is a quadratic residue of p and p does not divide a_{2}.#### Relationship of U Series to Lucas' Series

Denote ∑ζ_{1}^{e1}ζ_{2}^{e2}ζ_{3}^{e3}···ζ_{n}^{en}where ζ_{1}, ζ_{2}, ζ_{3}, ..., ζ_{n}are the roots of ζ^{n}+a_{1}ζ^{n-1}+a_{2}ζ^{n-2}+...+a_{n}=0 and the summation is over all combinations of non-negative integers e_{1}, e_{2}, e_{3}, ..., e_{n}such that e_{1}+e_{2}+e_{3}+...+e_{n}=i and exactly h of e_{1}, e_{2}, e_{3}, ..., e_{n}are non-zero by V_{i,h}. If i<h, let V_{i,h}=0. The following theorem is also proved;(3) The congruence x

^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}≡0(mod p), 0<x<p, p does not divide a_{1}a_{2}a_{3}···a_{n}, has n roots if and only if V_{p,i}≡V_{1,i}(mod p), i=2, 3, 4, ..., n.As will be shown, V

_{p,i}is always congruent (mod p) to V_{1,i}when i=1. Lucas denoted (x_{1}^{i}-x_{2}^{i})/(x_{1}-x_{2}), i=1, 2, 3, ..., where x_{1}, x_{2}are the roots of x^{2}-Px+Q=0 and P, Q are relatively prime integers by u_{i}and x_{1}^{i}+x_{2}^{i}by v_{i}. If n=2 and a_{1}, a_{2}are relatively prime, then U_{0}, U_{1}, U_{2}, ... is Lucas' u_{1}, u_{2}, u_{3}, ... and V_{1,1}, V_{2,1}, V_{3,1}, ... is Lucas' v_{1}, v_{2}, v_{3}, .... The U_{i}, V_{i,1}series can then be considered generalizations of Lucas' u_{i}, v_{i}series. For typographical convenience, let c(i,j) denote i "choose" j (a binomial coefficient). The U and V series are related as follows;(4) a

_{j}U_{i}=(-1)^{j}∑c(j+k,j)V_{i+j,j+k}, j=1, 2, 3, ...,n where the summation is from k=0 to k=n-j.(5) V

_{i,j}=(-1)^{j}∑c(j+k,j)a_{j+k}U_{i-j-k}, j=1, 2, 3, ..., n where the summation is from k=0 to k=n-j.#### König's Theorem

The proof of Theorem (1) is based on König's theorem (proposed by Julius König in 1882). König's theorem is this; Let f(x)=c_{0}x^{p-2}+c_{1}x^{p-3}+c_{2}x^{p-4}+...+c_{p-2}where the c's are integers and c_{p-2}is not divisible by the prime p. Then f(x)≡0(mod p) has real roots if and only if the determinant of the cyclic matrixc_{0} |
c_{1} |
c_{2} |
. | . | . | c_{p-3} |
c_{p-2} |

c_{1} |
c_{2} |
c_{3} |
. | . | . | c_{p-2} |
c_{0} |

c_{2} |
c_{3} |
c_{4} |
. | . | . | c_{0} |
c_{1} |

. | |||||||

. | |||||||

. | |||||||

c_{p-2} |
c_{0} |
c_{1} |
. | . | . | c_{p-4} |
c_{p-3} |

is divisible by p. Denote this matrix by C. In order that it have at least k distinct real roots it is necessary that all p-k rowed minors of C be divisible by p. If also not all p-k-1 rowed minors are divisible by p, the congruence has exactly k distinct real roots. Kronecker's version of König's theorem will also be used in the proof. Kronecker's version is this; f(x)≡0(mod p) has exactly k roots if and only if the rank of C is exactly p-1-k.

Fermat's theorem is essential to the formulation of König's theorem. If f(x)≡0(mod p) has a root, then this root is also a root of x

^{p-1}≡1(mod p) and hence p divides the determinant of the resultant of f(x) and x^{p-1}-1, i.e., the cyclic matrix C. This is the motivation for part of the U series definition; the U series has been defined so that the "resultant" of U_{i+n}+a_{1}U_{i+n-1}+a_{2}U_{i+n-2}+...+a_{n}U_{i}and U_{p-1+i}-U_{i}, i=0, 1, 2, ..., (p-2), equals the resultant of x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}and x^{p-1}-1. The condition U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ..., is then the analogue of Fermat's theorem.#### Proof of Theorem (1) (the Part Using Kronecker's Theorem)

First suppose that U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, .... Denote the (p-1)x(p-1) cyclic matrixa_{2} |
a_{3} |
a_{4} |
... | a_{n} |
0 | ... | 0 | 0 | 1 | a_{1} |

a_{3} |
a_{4} |
a_{5} |
... | 0 | 0 | ... | 0 | 1 | a_{1} |
a_{2} |

a_{4} |
a_{5} |
a_{6} |
... | 0 | 0 | ... | 1 | a_{1} |
a_{2} |
a_{3} |

. | ||||||||||

. | ||||||||||

. | ||||||||||

1 | a_{1} |
a_{2} |
... | a_{n-2} |
a_{n-1} |
... | 0 | 0 | 0 | 0 |

a_{1} |
a_{2} |
a_{3} |
... | a_{n-1} |
a_{n} |
... | 0 | 0 | 0 | 1 |

by A. Then since U

_{i}+a_{1}U_{i-1}+a_{2}U_{i-2}+...+a_{n}U_{i-n}=0 and U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ..., (p-1), A(U_{p-2}, U_{p-3}, U_{p-4}, ..., U_{0})≡(0, 0, 0, ..., 0)(mod p). U_{p-1+i-n}≡0(mod p), i=1, 2, 3, ..., (n-1), therefore M_{0}(U_{p-n-1}, U_{p-n-2}, U_{p-n-3}, ..., U_{0})≡(0, 0, 0, ..., 0)(mod p) where M_{0}is the (p-1)x(p-n) matrix obtained from A by deleting its first n-1 columns. Denote the (p-1)x(p-n-1) matrix0 | 0 | 0 | ... | 0 | 0 | 0 | 1 |

0 | 0 | 0 | ... | 0 | 0 | 1 | a_{1} |

0 | 0 | 0 | ... | 0 | 1 | a_{1} |
a_{2} |

0 | 0 | 0 | ... | 1 | a_{1} |
a_{2} |
a_{3} |

. | |||||||

. | |||||||

. | |||||||

a_{n-2} |
a_{n-1} |
a_{n} |
... | 0 | 0 | 0 | 0 |

a_{n-1} |
a_{n} |
0 | ... | 0 | 0 | 0 | 0 |

a_{n} |
0 | 0 | ... | 0 | 0 | 0 | 0 |

by R. R(-U

_{p-n-1}, -U_{p-n-2}, -U_{p-n-3}, ..., -U_{1})≡(a_{1}, a_{2}, a_{3}, ..., 0, 0, 1)(mod p) (since U_{p-1}≡1, U_{p-2}≡U_{p-3}≡U_{p-4}≡...≡U_{p-n}≡0(mod p)) and hence the last column of M_{0}is linearly dependent (mod p) on the other columns of M_{0}. Similarly, M_{0}(-U_{p-n}, -U_{p-n-1}, -U_{p-n-2}, ..., -U_{1})≡(a_{2}, a_{3}, a_{4}, ..., 0, 1, a_{1})(mod p) (since U_{p}≡U_{1}, U_{p-1}≡U_{0}, U_{p-2}≡U_{p-3}≡U_{p-4}≡...≡U_{p-n+1}≡0(mod p)). Let M_{j}, j=1, 2, 3, ..., (n-1), be the (p-1)x(p-n+j) matrix having as its first (p-n) columns the columns of M_{0}and as its last columns the first j columns of A. In general, M_{j}(-U_{p-n+j}, -U_{p-n+j-1}, -U_{p-n+j-2}, ..., -U_{1}), j=0, 1, 2, ..., (n-1), is congruent mod p to the (j+1)th column of A. Then since the last column of M_{0}is linearly dependent (mod p) on the other columns of M_{0}, and the first column of A is linearly dependent (mod p) on the columns of M_{0}, and the second column of A is linearly dependent (mod p) on the columns of M_{1}, etc., there are at most p-n-1 linearly independent columns of A. Since the rank of a matrix is the dimension of its column space, the rank of A is at most p-1-n. Then by Kronecker's version of König's theorem, the congruence x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}≡0(mod p), 0<x<p, has at least n roots. An nth degree mod p congruence has at most n roots, therefore x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}≡0(mod p), 0<x<p, has exactly n roots.#### Proof of Theorem (1) (the Part Using König's Theorem)

Now suppose x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}≡0(mod p), 0<x<p, has n roots. Then by Fermat's theorem, A(x^{p-2}, x^{p-3}, x^{p-4}, ..., x^{0})≡(0, 0, 0, ..., 0)(mod p). Furthermore, by König's theorem, p divides all p-n rowed minors of A. One such minor is the determinant of the following matrix (denoted by B_{1});0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 0 | 1 | a_{1} |

0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 1 | a_{1} |
a_{2} |

0 | 0 | 0 | ... | 0 | 0 | ... | 1 | a_{1} |
a_{2} |
a_{3} |

. | ||||||||||

. | ||||||||||

. | ||||||||||

1 | a_{1} |
a_{2} |
... | a_{n-1} |
a_{n} |
... | 0 | 0 | 0 | 0 |

a_{1} |
a_{2} |
a_{3} |
... | a_{n} |
0 | ... | 0 | 0 | 0 | 0 |

(This is the matrix obtained from A by deleting its first n-1 columns and last n-1 rows.) Therefore B

_{1}(y_{p-n-1}, y_{p-n-2}, y_{p-n-3}, ..., y_{0})≡(0, 0, 0, ..., 0)(mod p) where not all of y_{p-n-1}, y_{p-n-2}, y_{p-n-3}, ..., y_{0}are congruent to zero mod p. Then y_{1}+a_{1}y_{0}≡0(mod p), y_{2}+a_{1}y_{1}+a_{2}y_{0}≡0(mod p), y_{3}+a_{1}y_{2}+a_{2}y_{1}+a_{3}y_{0}≡0(mod p), ..., y_{p-n-1}+a_{1}y_{p-n-2}+a_{2}y_{p-n-3}+...+a_{n}y_{p-2n-1}≡0(mod p) and hence p does not divide y_{0}(since otherwise p would divide all of y_{p-n-1,}, y_{p-n-2}, y_{p-n-3}, ..., y_{0}, a contradiction). Therefore (y_{1}/y_{0})+a_{1}≡0(mod p). Also U_{1}+a_{1}U_{0}=0, therefore (y_{1}/y_{0})≡U_{1}(mod p). Similarly (y_{2}/y_{0})+a_{1}(y_{1}/y_{0})+a_{2}≡0(mod p) and U_{2}+a_{1}U_{1}+a_{2}U_{0}=0, therefore (y_{2}/y_{0})≡U_{2}(mod p). By an induction argument, (y_{p--n-1}/y_{0})≡U_{p-n-1}(mod p), (y_{p-n-2}/y_{0})≡U_{p-n-2}(mod p), (y_{p-n-3}/y_{0})≡U_{p-n-3}(mod p), ..., (y_{1}/y_{0})≡U_{1}(mod p) and hence B_{1}(U_{p-n-1}, U_{p-n-2}, U_{p-n-3}, ..., U_{0})≡(0, 0, 0, ..., 0)(mod p). The product of the last row of B_{1}and (U_{p-n-1}, U_{p-n-2}, U_{p-n-3}, ..., U_{0}) gives a_{1}U_{p-n-1}+a_{2}U_{p-n-2}+a_{3}U_{p-n-3}+...+a_{n}U_{p-2n}≡0(mod p). Then since U_{p-n}+a_{1}U_{p-n-1}+a_{2}U_{p-n-2}+...+a_{n}U_{p-2n}=0, U_{p-n}≡0(mod p).Since p divides all p-n rowed minors of A, p divides all j rowed minors of A where j≥p-n. Therefore p divides the determinant of the (p-n+1)x(p-n+1) matrix

a_{n} |
0 | 0 | ... | 0 | 0 | ... | 0 | 0 | 1 | a_{1} |

0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 1 | a_{1} |
a_{2} |

0 | 0 | 0 | ... | 0 | 0 | ... | 1 | a_{1} |
a_{2} |
a_{3} |

. | ||||||||||

. | ||||||||||

. | ||||||||||

1 | a_{1} |
a_{2} |
... | a_{n-1} |
a_{n} |
... | 0 | 0 | 0 | 0 |

a_{1} |
a_{2} |
a_{3} |
... | a_{n} |
0 | ... | 0 | 0 | 0 | 0 |

(This is the matrix obtained from A by deleting its first n-2 columns and last n-2 rows.) p divides the row 1, column 1 cofactor of this matrix (since p divides all p-n rowed minors of A), therefore p divides the determinant of the matrix obtained from the above matrix by changing the row 1, column 1 element to a zero. Denote this matrix by B

_{2}. Then B_{2}(U_{p-n}, U_{p-n-1}, U_{p-n-2}, ..., U_{0})≡(0, 0, 0, ..., 0)(mod p). The product of the last row of B_{2}and (U_{p-n}, U_{p-n-1}, U_{p-n-2}, ..., U_{0}) gives a_{1}U_{p-n}+a_{2}U_{p-n-1}+a_{3}U_{p-n-2}+...+a_{n}U_{p-2n+1}≡0(mod p). Then since U_{p-n+1}+a_{1}U_{p-n}+a_{2}U_{p-n-1}+...+a_{n}U_{p-2n+1}=0, U_{p-n+1}≡0(mod p).The proofs that U

_{p-2}≡0(mod p), U_{p-3}≡0(mod p), U_{p-4}≡0(mod p), ..., U_{p-n}≡0(mod p) are similar. Finally, p divides the determinant of the (p-1)x(p-1) matrix0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 0 | 1 | a_{1} |

0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 1 | a_{1} |
a_{2} |

0 | 0 | 0 | ... | 0 | 0 | ... | 1 | a_{1} |
a_{2} |
a_{3} |

. | ||||||||||

. | ||||||||||

. | ||||||||||

1 | a_{1} |
a_{2} |
... | a_{n-1} |
a_{n} |
... | 0 | 0 | 0 | 0 |

a_{1} |
a_{2} |
a_{3} |
... | a_{n} |
0 | ... | 0 | 0 | 0 | 1 |

Denote this matrix by B

_{n}. Then B_{n}(U_{p-2}, U_{p-3}, U_{p-4}, ..., U_{0})≡(0, 0, 0, ..., 0)(mod p). The product of the last row of B_{n}and (U_{p-2}, U_{p-3}, U_{p-4}, ..., U_{0}) gives a_{1}U_{p-2}+a_{2}U_{p-3}+a_{3}U_{p-4}+...+a_{n}U_{p-n-1}+1≡0(mod p). Then since U_{p-1}+a_{1}U_{p-2}+a_{2}U_{p-3}+...+a_{n}U_{p-n-1}=0, U_{p-1}≡1(mod p). Therefore U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ..., n.(6) If U

_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ..., n, then U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ....Suppose U

_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ..., n. U_{p}+a_{1}U_{p-1}+a_{2}U_{p-2}+...+a_{n}U_{p-n}=0, therefore U_{p}+a_{1}≡0(mod p). Also U_{1}+a_{1}U_{0}=0, therefore U_{p}≡U_{1}(mod p), that is, U_{p-1+i-n}≡U_{i-n}(mod p), i=n+1. Similarly U_{p+1}+a_{1}U_{p}+a_{2}U_{p-1}+...+a_{n}U_{p-n+1}=0, therefore U_{p+1}+a_{1}U_{1}+a_{2}U_{0}≡0(mod p). Also U_{2}+a_{1}U_{1}+a_{2}U_{0}=0, therefore U_{p+1}≡U_{2}(mod p), that is, U_{p-1+i-n}≡U_{i-n}(mod p), i=n+2. An inducation argument gives U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, .... Therefore if x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}≡0(mod p), 0<x<p, has n roots, then U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, .... So x^{n}+a_{1}x^{n-1}+a_{2}x^{n-2}+...+a_{n}≡0(mod p), 0<x<p, has n roots if and only if U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ....#### Proofs of Theorems (2) and (4)

Denote ∑ζ_{1}^{e1}ζ_{2}^{e2}ζ_{3}^{e3}···ζ_{n}^{en}where ζ_{1}, ζ_{2}, ζ_{3}, ..., ζ_{n}are the roots of ζ^{n}+a_{1}ζ^{n-1}+a_{2}ζ^{n-2}+...+a_{n}=0 and the summation is over all combinations of non-negative integers e_{1}, e_{2}, e_{3}, ..., e_{n}such that e_{1}+e_{2}+e_{3}+...+e_{n}=i by U_{i}'. Then U_{0}', U_{1}', U_{2}', ... are defined and U_{0}'=1. If i<0, let U_{i}'=0. Then(7) If i≠0, U

_{i}'=V_{i,1}+V_{i,2}+V_{i,3}+...+V_{i,n}.ζ

^{n}+a_{1}ζ^{n-1}+a_{2}ζ^{n-2}+...+a_{n}=(ζ-ζ_{1})(ζ-ζ_{2})(ζ-ζ_{3})···(ζ-ζ_{n}), therefore a_{j}, j=1, 2, 3, ..., n, equals (-1)^{j}times the sum of all combinations of products of ζ_{1}, ζ_{2}, ζ_{3}, ..., ζ_{n}taken j at a time (that is, a_{j}=(-1)^{j}V_{j,j}). If i≥0, each term in the summation giving V_{i+j,j+k}, 0≤k≤i, k≤n-j, can be factored in c(j+k,j) ways so that one factor is a term in the summation giving U_{i}' and the other factor is a term in the summation giving a_{j}. Conversely, if i≥0, every term in the summation giving a_{j}U_{i}' is in one of V_{i+j,j}, V_{i+j,j+1}, V_{i+j,j+2}, ..., V_{i+j,d}where d=min(i+j,n). Therefore if i≥0, a_{j}U_{i}'=(-1)^{j}[c(j,j)V_{i+j,j}+c(j+1,j)V_{i+j,j+1}+c(j+2,j)V_{i+j,j+2}+...+c(d,j)V_{i+j,d}]. Then a_{j}U_{i}'=(-1)^{j}[c(j,j)V_{i+j,j}+c(j+1,j)V_{i+j,j+1}+c(j+2,j)V_{i+j,j+2}+...+c(n,j)V_{i+j,n}], j=1, 2, 3, ..., n. Denote the nxn matrix-c(1,1) | -c(2,1) | -c(3,1) | ... | -c(n,1) |

0 | c(2,2) | c(3,2) | ... | c(n,2) |

0 | 0 | -c(3,3) | ... | -c(n,3) |

. | ||||

. | ||||

. | ||||

0 | 0 | 0 | ... | (-1)^{n}c(n,n) |

by T. Therefore T(V

_{i,1}, V_{i,2}, V_{i,3}, ..., V_{i,n})=(a_{1}U_{i-1}', a_{2}U_{i-2}', a_{3}U_{i-3}', ..., a_{n}U_{i-n}'). The sums of the columns of T equal -1, therefore -(V_{i,1}+V_{i,2}+V_{i,3}+...+V_{i,n})=a_{1}U_{i-1}'+a_{2}U_{i-2}'+a_{3}U_{i-3}'+...+a_{n}U_{i-n}' and hence U_{i}'+a_{1}U_{i-1}'+a_{2}U_{i-2}'+...+a_{n}U_{i-n}'=0, i=1, 2, 3, .... Therefore U_{i}'=U_{i}and Theorems (2) and (4) follow.#### Proof of Theorem (5)

Element (a,b), a≤b, of T is (-1)^{a}c(b,a) and element (a,b) a>b, is zero, therefore element (a,b), a≤b, of T^{2}is ∑(-1)^{k+a}c(k,a)c(b,k) where the summation is from k=a to k=b, and element (a,b), a>b, is zero. If a≤k≤b, then c(k,a)c(b,k)=c(b,a)c(b-a,k-a). Also, ∑(-1)^{k+a}c(b,a)c(b-a,k-a) where the summation is from k=a to k=b equals c(b,a)∑(-1)^{k}c(b-a,k) where the summation is from k=0 to k=b-a, and these summations equal 0 if a<b or 1 if a=b. Therefore T^{2}=I where I is the nxn identity matrix. Then since T(V_{i,1}, V_{i,2}, V_{i,3}, ..., V_{i,n})=(a_{1}U_{i-1}, a_{2}U_{i-2}, a_{3}U_{i-3}, ..., a_{n}U_{i-n}), T(a_{1}U_{i-1}, a_{2}U_{i-2}, a_{3}U_{i-3}, ..., a_{n}U_{i-n})=(V_{i,1}, V_{i,2}, V_{i,3}, ..., V_{i,n}). Therefore V_{i,j}=(-1)^{j}[c(j,j)a_{j}U_{i-j}+c(j+1,j)a_{j+1}U_{i-j-1}+c(j+2,j)a_{j+2}U_{i-j+2}+...+c(n,j)a_{n}U_{i-n}], j=1, 2, 3, ..., n. (Note that this is the formula relating Fibonacci and Lucas numbers if n=2, a_{1}=a_{2}=-1, and j=1.)#### Proofs of Remaining Theorems

Some previous assertions will now be proved. ζ_{1}^{p}+ζ_{2}^{p}+ζ_{3}^{p}+...+ζ_{n}^{p}≡(ζ_{1}+ζ_{2}+ζ_{3}+...+ζ_{n})^{p}(mod p) (by properties of symmetric functions and the binomial coefficients) and (ζ_{1}+ζ_{2}+ζ_{3}+...+ζ_{n})^{p}≡(ζ_{1}+ζ_{2}+ζ_{3}+...+ζ_{n})(mod p) (by Fermat's theorem), therefore ζ_{1}^{p}+ζ_{2}^{p}+ζ_{3}^{p}+...+ζ_{n}^{p}≡(ζ_{1}+ζ_{2}+ζ_{3}+...+ζ_{n})(mod p), that is;(8) V

_{p,1}≡V_{1,1}(mod p).Also, V

_{1,1}=-a_{1}and -V_{p,1}=a_{1}U_{p-1}+2a_{2}U_{p-2}+3a_{3}U_{p-3}+...+na_{n}U_{p-n}(by Theorem (5)), therefore;(9) a

_{1}(U_{p-1}-1)+2a_{2}U_{p-2}+3a_{3}U_{p-3}+...+na_{n}U_{p-n}≡0(mod p).Finally, Theorem (3) will be proved. If U

_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ..., n, then by the matrix equation obtained in the proof of Theorems (2) and (4), V_{p,2}≡V_{p,3}≡V_{p,4}≡...≡V_{p,n}≡0(mod ), that is V_{p,i}≡V_{1,i}(mod p), i=2, 3, 4, ..., n. Conversely, if V_{p,i}≡V_{1,i}(mod p), i=2, 3, 4, ..., n, and p does not divide a_{1}a_{2}a_{3}···a_{n}, then U_{p-1}≡1, U_{p-2}≡U_{p-3}≡U_{p-4}≡...≡U_{p-n}≡0(mod p), that is, U_{p-1+i-n}≡U_{i-n}(mod p), i=1, 2, 3, ..., n. Theorem (3) then follows from Theorem (1).#### References

E. LucasComptes Rendus Paris, 82, 1876, pp. 1303-5.

J. König

Jour. für Math., 99, 1886, 258-260; Math. Termes Ertesito, Magyar Tudon Ak., Budapest, 1, 1883, 296; 3, 1885, 178.

L. Kronecker

Jour. für Math., 99, 1886, 363, 366.