Necessary and Sufficient Conditions for a Nth Degree Mod P Congruence to Have N Roots
Created | Updated Aug 19, 2011
Let p be a prime greater than 2, n a natural number such that n≤p-2, and a1, a2, a3, ..., an integers. Let the U series be defined by the recurrence relation Ui+a1Ui-1+a2Ui-2+...+anUi-n=0 where i=1, 2, 3, ..., U0=1, and Ui=0 if i<0. The principal subject here is the proof of the following theorem;
(1) The congruence xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has n roots if and only if Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ....
(Also, if a1, a2, a3, ..., an are elements of a Galois field, then the equation xn+a1xn-1+a2xn-2+...+an=0 has n roots if and only if UO+i-n=Ui-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 xp-1≡1(mod p) if p does not divide x. As will be shown, If Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n, then Up-1+i-n≡Ui-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 x3-x2-x+2≡0(mod p), 0<x<p, are;
U16≡1(mod 17) and U15≡U14≡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.
There also exists an alternate Ui definition;
(2) Ui, i≥0, equals ∑ζ1e1ζ2e2ζ3e3···ζnen where ζ1, ζ2, ζ3, ..., ζn are the roots of ζn+a1ζn-1+a2ζn-2+...+an=0 and the summation is over all combinations of non-negative integers e1, e2, e3, ..., en such that e1+e2+e3+...+en=i.
As will be shown, a1(Up-1-1)+2a2Up-2+3a3Up-3+...+nanUp-n≡0(mod p). Therefore if n>1 and p does not divide a1a2a3···an, the congruence to zero of any group of n-1 of Up-1-1, Up-2, Up-3, ..., Up-n implies the congruence to zero of all of Up-1-1, Up-2, Up-3, ..., Up-n. This result is of special significance in the case n=2. If n=2, a property of the U series is Up-1≡(a12-4a2)(p-1)/2(mod p) (since if n=2, Up-1=(ζ1p-ζ2p)/(ζ1-ζ2), (ζ1p-ζ2p)/(ζ1-ζ2)≡(ζ1-ζ2)p/(ζ1-ζ2)(mod p), and (ζ1-ζ2)2=[-(ζ1+ζ2)]2-4ζ1ζ2=a12-4a2). Therefore Up-1≡1(mod p) where n=2 if and only if a12-4a2 is a quadratic residue of p. If Up-1≡1(mod p) and Up-2≡0(mod p) where n=2, then p does not divide a2 (since by the recurrence relation, Up-2=(-a1)p-2+k1a2 and Up-1=(-a1)p-1+k2a2 where k1, k2 are integers). Conversely, if a12-4a2 is a quadratic residue of p and p does not divide a2 where n=2, then Up-1≡1(mod p) and Up-2≡0(mod p) (since a1(Up-1-1)+2a2Up-2≡0(mod p)). Therefore Up-1≡1, Up-2≡0(mod p) where n=2 if and only if a12-4a2 is a quadratic residue of p and p does not divide a2. This shows the equivalence of Theorem (1) in the case n=2 with the familiar result that the congruence x2+a1x+a2≡0(mod p), 0<x<p, has two roots if and only if a12-4a2 is a quadratic residue of p and p does not divide a2.
(3) The congruence xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, p does not divide a1a2a3···an, has n roots if and only if Vp,i≡V1,i(mod p), i=2, 3, 4, ..., n.
As will be shown, Vp,i is always congruent (mod p) to V1,i when i=1. Lucas denoted (x1i-x2i)/(x1-x2), i=1, 2, 3, ..., where x1, x2 are the roots of x2-Px+Q=0 and P, Q are relatively prime integers by ui and x1i+x2i by vi. If n=2 and a1, a2 are relatively prime, then U0, U1, U2, ... is Lucas' u1, u2, u3, ... and V1,1, V2,1, V3,1, ... is Lucas' v1, v2, v3, .... The Ui, Vi,1 series can then be considered generalizations of Lucas' ui, vi 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) ajUi=(-1)j∑c(j+k,j)Vi+j,j+k, j=1, 2, 3, ...,n where the summation is from k=0 to k=n-j.
(5) Vi,j=(-1)j∑c(j+k,j)aj+kUi-j-k, j=1, 2, 3, ..., n where the summation is from k=0 to k=n-j.
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 xp-1≡1(mod p) and hence p divides the determinant of the resultant of f(x) and xp-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 Ui+n+a1Ui+n-1+a2Ui+n-2+...+anUi and Up-1+i-Ui, i=0, 1, 2, ..., (p-2), equals the resultant of xn+a1xn-1+a2xn-2+...+an and xp-1-1. The condition Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., is then the analogue of Fermat's theorem.
by A. Then since Ui+a1Ui-1+a2Ui-2+...+anUi-n=0 and Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., (p-1), A(Up-2, Up-3, Up-4, ..., U0)≡(0, 0, 0, ..., 0)(mod p). Up-1+i-n≡0(mod p), i=1, 2, 3, ..., (n-1), therefore M0(Up-n-1, Up-n-2, Up-n-3, ..., U0)≡(0, 0, 0, ..., 0)(mod p) where M0 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) matrix
by R. R(-Up-n-1, -Up-n-2, -Up-n-3, ..., -U1)≡(a1, a2, a3, ..., 0, 0, 1)(mod p) (since Up-1≡1, Up-2≡Up-3≡Up-4≡...≡Up-n≡0(mod p)) and hence the last column of M0 is linearly dependent (mod p) on the other columns of M0. Similarly, M0(-Up-n, -Up-n-1, -Up-n-2, ..., -U1)≡(a2, a3, a4, ..., 0, 1, a1)(mod p) (since Up≡U1, Up-1≡U0, Up-2≡Up-3≡Up-4≡...≡Up-n+1≡0(mod p)). Let Mj, 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 M0 and as its last columns the first j columns of A. In general, Mj(-Up-n+j, -Up-n+j-1, -Up-n+j-2, ..., -U1), j=0, 1, 2, ..., (n-1), is congruent mod p to the (j+1)th column of A. Then since the last column of M0 is linearly dependent (mod p) on the other columns of M0, and the first column of A is linearly dependent (mod p) on the columns of M0, and the second column of A is linearly dependent (mod p) on the columns of M1, 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 xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has at least n roots. An nth degree mod p congruence has at most n roots, therefore xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has exactly n roots.
(This is the matrix obtained from A by deleting its first n-1 columns and last n-1 rows.) Therefore B1(yp-n-1, yp-n-2, yp-n-3, ..., y0)≡(0, 0, 0, ..., 0)(mod p) where not all of yp-n-1, yp-n-2, yp-n-3, ..., y0 are congruent to zero mod p. Then y1+a1y0≡0(mod p), y2+a1y1+a2y0≡0(mod p), y3+a1y2+a2y1+a3y0≡0(mod p), ..., yp-n-1+a1yp-n-2+a2yp-n-3+...+anyp-2n-1≡0(mod p) and hence p does not divide y0 (since otherwise p would divide all of yp-n-1,, yp-n-2, yp-n-3, ..., y0, a contradiction). Therefore (y1/y0)+a1≡0(mod p). Also U1+a1U0=0, therefore (y1/y0)≡U1(mod p). Similarly (y2/y0)+a1(y1/y0)+a2≡0(mod p) and U2+a1U1+a2U0=0, therefore (y2/y0)≡U2(mod p). By an induction argument, (yp--n-1/y0)≡Up-n-1(mod p), (yp-n-2/y0)≡Up-n-2(mod p), (yp-n-3/y0)≡Up-n-3(mod p), ..., (y1/y0)≡U1(mod p) and hence B1(Up-n-1, Up-n-2, Up-n-3, ..., U0)≡(0, 0, 0, ..., 0)(mod p). The product of the last row of B1 and (Up-n-1, Up-n-2, Up-n-3, ..., U0) gives a1Up-n-1+a2Up-n-2+a3Up-n-3+...+anUp-2n≡0(mod p). Then since Up-n+a1Up-n-1+a2Up-n-2+...+anUp-2n=0, Up-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
(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 B2. Then B2(Up-n, Up-n-1, Up-n-2, ..., U0)≡(0, 0, 0, ..., 0)(mod p). The product of the last row of B2 and (Up-n, Up-n-1, Up-n-2, ..., U0) gives a1Up-n+a2Up-n-1+a3Up-n-2+...+anUp-2n+1≡0(mod p). Then since Up-n+1+a1Up-n+a2Up-n-1+...+anUp-2n+1=0, Up-n+1≡0(mod p).
The proofs that Up-2≡0(mod p), Up-3≡0(mod p), Up-4≡0(mod p), ..., Up-n≡0(mod p) are similar. Finally, p divides the determinant of the (p-1)x(p-1) matrix
Denote this matrix by Bn. Then Bn(Up-2, Up-3, Up-4, ..., U0)≡(0, 0, 0, ..., 0)(mod p). The product of the last row of Bn and (Up-2, Up-3, Up-4, ..., U0) gives a1Up-2+a2Up-3+a3Up-4+...+anUp-n-1+1≡0(mod p). Then since Up-1+a1Up-2+a2Up-3+...+anUp-n-1=0, Up-1≡1(mod p). Therefore Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n.
(6) If Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n, then Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ....
Suppose Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n. Up+a1Up-1+a2Up-2+...+anUp-n=0, therefore Up+a1≡0(mod p). Also U1+a1U0=0, therefore Up≡U1(mod p), that is, Up-1+i-n≡Ui-n(mod p), i=n+1. Similarly Up+1+a1Up+a2Up-1+...+anUp-n+1=0, therefore Up+1+a1U1+a2U0≡0(mod p). Also U2+a1U1+a2U0=0, therefore Up+1≡U2(mod p), that is, Up-1+i-n≡Ui-n(mod p), i=n+2. An inducation argument gives Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, .... Therefore if xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has n roots, then Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, .... So xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has n roots if and only if Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ....
(7) If i≠0, Ui'=Vi,1+Vi,2+Vi,3+...+Vi,n.
ζn+a1ζn-1+a2ζn-2+...+an=(ζ-ζ1)(ζ-ζ2)(ζ-ζ3)···(ζ-ζn), therefore aj, 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, aj=(-1)jVj,j). If i≥0, each term in the summation giving Vi+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 Ui' and the other factor is a term in the summation giving aj. Conversely, if i≥0, every term in the summation giving ajUi' is in one of Vi+j,j, Vi+j,j+1, Vi+j,j+2, ..., Vi+j,d where d=min(i+j,n). Therefore if i≥0, ajUi'=(-1)j[c(j,j)Vi+j,j+c(j+1,j)Vi+j,j+1+c(j+2,j)Vi+j,j+2+...+c(d,j)Vi+j,d]. Then ajUi'=(-1)j[c(j,j)Vi+j,j+c(j+1,j)Vi+j,j+1+c(j+2,j)Vi+j,j+2+...+c(n,j)Vi+j,n], j=1, 2, 3, ..., n. Denote the nxn matrix
by T. Therefore T(Vi,1, Vi,2, Vi,3, ..., Vi,n)=(a1Ui-1', a2Ui-2', a3Ui-3', ..., anUi-n'). The sums of the columns of T equal -1, therefore -(Vi,1+Vi,2+Vi,3+...+Vi,n)=a1Ui-1'+a2Ui-2'+a3Ui-3'+...+anUi-n' and hence Ui'+a1Ui-1'+a2Ui-2'+...+anUi-n'=0, i=1, 2, 3, .... Therefore Ui'=Ui and Theorems (2) and (4) follow.
(8) Vp,1≡V1,1(mod p).
Also, V1,1=-a1 and -Vp,1=a1Up-1+2a2Up-2+3a3Up-3+...+nanUp-n (by Theorem (5)), therefore;
(9) a1(Up-1-1)+2a2Up-2+3a3Up-3+...+nanUp-n≡0(mod p).
Finally, Theorem (3) will be proved. If Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n, then by the matrix equation obtained in the proof of Theorems (2) and (4), Vp,2≡Vp,3≡Vp,4≡...≡Vp,n≡0(mod ), that is Vp,i≡V1,i(mod p), i=2, 3, 4, ..., n. Conversely, if Vp,i≡V1,i(mod p), i=2, 3, 4, ..., n, and p does not divide a1a2a3···an, then Up-1≡1, Up-2≡Up-3≡Up-4≡...≡Up-n≡0(mod p), that is, Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n. Theorem (3) then follows from Theorem (1).
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) The congruence xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has n roots if and only if Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ....
(Also, if a1, a2, a3, ..., an are elements of a Galois field, then the equation xn+a1xn-1+a2xn-2+...+an=0 has n roots if and only if UO+i-n=Ui-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 xp-1≡1(mod p) if p does not divide x. As will be shown, If Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n, then Up-1+i-n≡Ui-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 x3-x2-x+2≡0(mod p), 0<x<p, are;
| U1=1 | U2=2 | U3=1 | U4=1 | U5=-2 | U6=-3 | U7=-7 | U8=-6 |
| U9=-7 | U10=1 | U11=6 | U12=21 | U13=25 | U14=34 | U15=17 | U16=1 |
U16≡1(mod 17) and U15≡U14≡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 a1=a2=-1, then Ui 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 (ζ1i-ζ2i)/(ζ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 x2-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 Ui definition;
(2) Ui, i≥0, equals ∑ζ1e1ζ2e2ζ3e3···ζnen where ζ1, ζ2, ζ3, ..., ζn are the roots of ζn+a1ζn-1+a2ζn-2+...+an=0 and the summation is over all combinations of non-negative integers e1, e2, e3, ..., en such that e1+e2+e3+...+en=i.
As will be shown, a1(Up-1-1)+2a2Up-2+3a3Up-3+...+nanUp-n≡0(mod p). Therefore if n>1 and p does not divide a1a2a3···an, the congruence to zero of any group of n-1 of Up-1-1, Up-2, Up-3, ..., Up-n implies the congruence to zero of all of Up-1-1, Up-2, Up-3, ..., Up-n. This result is of special significance in the case n=2. If n=2, a property of the U series is Up-1≡(a12-4a2)(p-1)/2(mod p) (since if n=2, Up-1=(ζ1p-ζ2p)/(ζ1-ζ2), (ζ1p-ζ2p)/(ζ1-ζ2)≡(ζ1-ζ2)p/(ζ1-ζ2)(mod p), and (ζ1-ζ2)2=[-(ζ1+ζ2)]2-4ζ1ζ2=a12-4a2). Therefore Up-1≡1(mod p) where n=2 if and only if a12-4a2 is a quadratic residue of p. If Up-1≡1(mod p) and Up-2≡0(mod p) where n=2, then p does not divide a2 (since by the recurrence relation, Up-2=(-a1)p-2+k1a2 and Up-1=(-a1)p-1+k2a2 where k1, k2 are integers). Conversely, if a12-4a2 is a quadratic residue of p and p does not divide a2 where n=2, then Up-1≡1(mod p) and Up-2≡0(mod p) (since a1(Up-1-1)+2a2Up-2≡0(mod p)). Therefore Up-1≡1, Up-2≡0(mod p) where n=2 if and only if a12-4a2 is a quadratic residue of p and p does not divide a2. This shows the equivalence of Theorem (1) in the case n=2 with the familiar result that the congruence x2+a1x+a2≡0(mod p), 0<x<p, has two roots if and only if a12-4a2 is a quadratic residue of p and p does not divide a2.
Relationship of U Series to Lucas' Series
Denote ∑ζ1e1ζ2e2ζ3e3···ζnen where ζ1, ζ2, ζ3, ..., ζn are the roots of ζn+a1ζn-1+a2ζn-2+...+an=0 and the summation is over all combinations of non-negative integers e1, e2, e3, ..., en such that e1+e2+e3+...+en=i and exactly h of e1, e2, e3, ..., en are non-zero by Vi,h. If i<h, let Vi,h=0. The following theorem is also proved;(3) The congruence xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, p does not divide a1a2a3···an, has n roots if and only if Vp,i≡V1,i(mod p), i=2, 3, 4, ..., n.
As will be shown, Vp,i is always congruent (mod p) to V1,i when i=1. Lucas denoted (x1i-x2i)/(x1-x2), i=1, 2, 3, ..., where x1, x2 are the roots of x2-Px+Q=0 and P, Q are relatively prime integers by ui and x1i+x2i by vi. If n=2 and a1, a2 are relatively prime, then U0, U1, U2, ... is Lucas' u1, u2, u3, ... and V1,1, V2,1, V3,1, ... is Lucas' v1, v2, v3, .... The Ui, Vi,1 series can then be considered generalizations of Lucas' ui, vi 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) ajUi=(-1)j∑c(j+k,j)Vi+j,j+k, j=1, 2, 3, ...,n where the summation is from k=0 to k=n-j.
(5) Vi,j=(-1)j∑c(j+k,j)aj+kUi-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)=c0xp-2+c1xp-3+c2xp-4+...+cp-2 where the c's are integers and cp-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 matrix| c0 | c1 | c2 | . | . | . | cp-3 | cp-2 |
| c1 | c2 | c3 | . | . | . | cp-2 | c0 |
| c2 | c3 | c4 | . | . | . | c0 | c1 |
| . | |||||||
| . | |||||||
| . | |||||||
| cp-2 | c0 | c1 | . | . | . | cp-4 | cp-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 xp-1≡1(mod p) and hence p divides the determinant of the resultant of f(x) and xp-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 Ui+n+a1Ui+n-1+a2Ui+n-2+...+anUi and Up-1+i-Ui, i=0, 1, 2, ..., (p-2), equals the resultant of xn+a1xn-1+a2xn-2+...+an and xp-1-1. The condition Up-1+i-n≡Ui-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 Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, .... Denote the (p-1)x(p-1) cyclic matrix| a2 | a3 | a4 | ... | an | 0 | ... | 0 | 0 | 1 | a1 |
| a3 | a4 | a5 | ... | 0 | 0 | ... | 0 | 1 | a1 | a2 |
| a4 | a5 | a6 | ... | 0 | 0 | ... | 1 | a1 | a2 | a3 |
| . | ||||||||||
| . | ||||||||||
| . | ||||||||||
| 1 | a1 | a2 | ... | an-2 | an-1 | ... | 0 | 0 | 0 | 0 |
| a1 | a2 | a3 | ... | an-1 | an | ... | 0 | 0 | 0 | 1 |
by A. Then since Ui+a1Ui-1+a2Ui-2+...+anUi-n=0 and Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., (p-1), A(Up-2, Up-3, Up-4, ..., U0)≡(0, 0, 0, ..., 0)(mod p). Up-1+i-n≡0(mod p), i=1, 2, 3, ..., (n-1), therefore M0(Up-n-1, Up-n-2, Up-n-3, ..., U0)≡(0, 0, 0, ..., 0)(mod p) where M0 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) matrix
| 0 | 0 | 0 | ... | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | ... | 0 | 0 | 1 | a1 |
| 0 | 0 | 0 | ... | 0 | 1 | a1 | a2 |
| 0 | 0 | 0 | ... | 1 | a1 | a2 | a3 |
| . | |||||||
| . | |||||||
| . | |||||||
| an-2 | an-1 | an | ... | 0 | 0 | 0 | 0 |
| an-1 | an | 0 | ... | 0 | 0 | 0 | 0 |
| an | 0 | 0 | ... | 0 | 0 | 0 | 0 |
by R. R(-Up-n-1, -Up-n-2, -Up-n-3, ..., -U1)≡(a1, a2, a3, ..., 0, 0, 1)(mod p) (since Up-1≡1, Up-2≡Up-3≡Up-4≡...≡Up-n≡0(mod p)) and hence the last column of M0 is linearly dependent (mod p) on the other columns of M0. Similarly, M0(-Up-n, -Up-n-1, -Up-n-2, ..., -U1)≡(a2, a3, a4, ..., 0, 1, a1)(mod p) (since Up≡U1, Up-1≡U0, Up-2≡Up-3≡Up-4≡...≡Up-n+1≡0(mod p)). Let Mj, 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 M0 and as its last columns the first j columns of A. In general, Mj(-Up-n+j, -Up-n+j-1, -Up-n+j-2, ..., -U1), j=0, 1, 2, ..., (n-1), is congruent mod p to the (j+1)th column of A. Then since the last column of M0 is linearly dependent (mod p) on the other columns of M0, and the first column of A is linearly dependent (mod p) on the columns of M0, and the second column of A is linearly dependent (mod p) on the columns of M1, 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 xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has at least n roots. An nth degree mod p congruence has at most n roots, therefore xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has exactly n roots.
Proof of Theorem (1) (the Part Using König's Theorem)
Now suppose xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has n roots. Then by Fermat's theorem, A(xp-2, xp-3, xp-4, ..., x0)≡(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 B1);| 0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 0 | 1 | a1 |
| 0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 1 | a1 | a2 |
| 0 | 0 | 0 | ... | 0 | 0 | ... | 1 | a1 | a2 | a3 |
| . | ||||||||||
| . | ||||||||||
| . | ||||||||||
| 1 | a1 | a2 | ... | an-1 | an | ... | 0 | 0 | 0 | 0 |
| a1 | a2 | a3 | ... | an | 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 B1(yp-n-1, yp-n-2, yp-n-3, ..., y0)≡(0, 0, 0, ..., 0)(mod p) where not all of yp-n-1, yp-n-2, yp-n-3, ..., y0 are congruent to zero mod p. Then y1+a1y0≡0(mod p), y2+a1y1+a2y0≡0(mod p), y3+a1y2+a2y1+a3y0≡0(mod p), ..., yp-n-1+a1yp-n-2+a2yp-n-3+...+anyp-2n-1≡0(mod p) and hence p does not divide y0 (since otherwise p would divide all of yp-n-1,, yp-n-2, yp-n-3, ..., y0, a contradiction). Therefore (y1/y0)+a1≡0(mod p). Also U1+a1U0=0, therefore (y1/y0)≡U1(mod p). Similarly (y2/y0)+a1(y1/y0)+a2≡0(mod p) and U2+a1U1+a2U0=0, therefore (y2/y0)≡U2(mod p). By an induction argument, (yp--n-1/y0)≡Up-n-1(mod p), (yp-n-2/y0)≡Up-n-2(mod p), (yp-n-3/y0)≡Up-n-3(mod p), ..., (y1/y0)≡U1(mod p) and hence B1(Up-n-1, Up-n-2, Up-n-3, ..., U0)≡(0, 0, 0, ..., 0)(mod p). The product of the last row of B1 and (Up-n-1, Up-n-2, Up-n-3, ..., U0) gives a1Up-n-1+a2Up-n-2+a3Up-n-3+...+anUp-2n≡0(mod p). Then since Up-n+a1Up-n-1+a2Up-n-2+...+anUp-2n=0, Up-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
| an | 0 | 0 | ... | 0 | 0 | ... | 0 | 0 | 1 | a1 |
| 0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 1 | a1 | a2 |
| 0 | 0 | 0 | ... | 0 | 0 | ... | 1 | a1 | a2 | a3 |
| . | ||||||||||
| . | ||||||||||
| . | ||||||||||
| 1 | a1 | a2 | ... | an-1 | an | ... | 0 | 0 | 0 | 0 |
| a1 | a2 | a3 | ... | an | 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 B2. Then B2(Up-n, Up-n-1, Up-n-2, ..., U0)≡(0, 0, 0, ..., 0)(mod p). The product of the last row of B2 and (Up-n, Up-n-1, Up-n-2, ..., U0) gives a1Up-n+a2Up-n-1+a3Up-n-2+...+anUp-2n+1≡0(mod p). Then since Up-n+1+a1Up-n+a2Up-n-1+...+anUp-2n+1=0, Up-n+1≡0(mod p).
The proofs that Up-2≡0(mod p), Up-3≡0(mod p), Up-4≡0(mod p), ..., Up-n≡0(mod p) are similar. Finally, p divides the determinant of the (p-1)x(p-1) matrix
| 0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 0 | 1 | a1 |
| 0 | 0 | 0 | ... | 0 | 0 | ... | 0 | 1 | a1 | a2 |
| 0 | 0 | 0 | ... | 0 | 0 | ... | 1 | a1 | a2 | a3 |
| . | ||||||||||
| . | ||||||||||
| . | ||||||||||
| 1 | a1 | a2 | ... | an-1 | an | ... | 0 | 0 | 0 | 0 |
| a1 | a2 | a3 | ... | an | 0 | ... | 0 | 0 | 0 | 1 |
Denote this matrix by Bn. Then Bn(Up-2, Up-3, Up-4, ..., U0)≡(0, 0, 0, ..., 0)(mod p). The product of the last row of Bn and (Up-2, Up-3, Up-4, ..., U0) gives a1Up-2+a2Up-3+a3Up-4+...+anUp-n-1+1≡0(mod p). Then since Up-1+a1Up-2+a2Up-3+...+anUp-n-1=0, Up-1≡1(mod p). Therefore Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n.
(6) If Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n, then Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ....
Suppose Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n. Up+a1Up-1+a2Up-2+...+anUp-n=0, therefore Up+a1≡0(mod p). Also U1+a1U0=0, therefore Up≡U1(mod p), that is, Up-1+i-n≡Ui-n(mod p), i=n+1. Similarly Up+1+a1Up+a2Up-1+...+anUp-n+1=0, therefore Up+1+a1U1+a2U0≡0(mod p). Also U2+a1U1+a2U0=0, therefore Up+1≡U2(mod p), that is, Up-1+i-n≡Ui-n(mod p), i=n+2. An inducation argument gives Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, .... Therefore if xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has n roots, then Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, .... So xn+a1xn-1+a2xn-2+...+an≡0(mod p), 0<x<p, has n roots if and only if Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ....
Proofs of Theorems (2) and (4)
Denote ∑ζ1e1ζ2e2ζ3e3···ζnen where ζ1, ζ2, ζ3, ..., ζn are the roots of ζn+a1ζn-1+a2ζn-2+...+an=0 and the summation is over all combinations of non-negative integers e1, e2, e3, ..., en such that e1+e2+e3+...+en=i by Ui'. Then U0', U1', U2', ... are defined and U0'=1. If i<0, let Ui'=0. Then(7) If i≠0, Ui'=Vi,1+Vi,2+Vi,3+...+Vi,n.
ζn+a1ζn-1+a2ζn-2+...+an=(ζ-ζ1)(ζ-ζ2)(ζ-ζ3)···(ζ-ζn), therefore aj, 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, aj=(-1)jVj,j). If i≥0, each term in the summation giving Vi+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 Ui' and the other factor is a term in the summation giving aj. Conversely, if i≥0, every term in the summation giving ajUi' is in one of Vi+j,j, Vi+j,j+1, Vi+j,j+2, ..., Vi+j,d where d=min(i+j,n). Therefore if i≥0, ajUi'=(-1)j[c(j,j)Vi+j,j+c(j+1,j)Vi+j,j+1+c(j+2,j)Vi+j,j+2+...+c(d,j)Vi+j,d]. Then ajUi'=(-1)j[c(j,j)Vi+j,j+c(j+1,j)Vi+j,j+1+c(j+2,j)Vi+j,j+2+...+c(n,j)Vi+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)nc(n,n) |
by T. Therefore T(Vi,1, Vi,2, Vi,3, ..., Vi,n)=(a1Ui-1', a2Ui-2', a3Ui-3', ..., anUi-n'). The sums of the columns of T equal -1, therefore -(Vi,1+Vi,2+Vi,3+...+Vi,n)=a1Ui-1'+a2Ui-2'+a3Ui-3'+...+anUi-n' and hence Ui'+a1Ui-1'+a2Ui-2'+...+anUi-n'=0, i=1, 2, 3, .... Therefore Ui'=Ui and Theorems (2) and (4) follow.
Proof of Theorem (5)
Element (a,b), a≤b, of T is (-1)ac(b,a) and element (a,b) a>b, is zero, therefore element (a,b), a≤b, of T2 is ∑(-1)k+ac(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+ac(b,a)c(b-a,k-a) where the summation is from k=a to k=b equals c(b,a)∑(-1)kc(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 T2=I where I is the nxn identity matrix. Then since T(Vi,1, Vi,2, Vi,3, ..., Vi,n)=(a1Ui-1, a2Ui-2, a3Ui-3, ..., anUi-n), T(a1Ui-1, a2Ui-2, a3Ui-3, ..., anUi-n)=(Vi,1, Vi,2, Vi,3, ..., Vi,n). Therefore Vi,j=(-1)j[c(j,j)ajUi-j+c(j+1,j)aj+1Ui-j-1+c(j+2,j)aj+2Ui-j+2+...+c(n,j)anUi-n], j=1, 2, 3, ..., n. (Note that this is the formula relating Fibonacci and Lucas numbers if n=2, a1=a2=-1, and j=1.)Proofs of Remaining Theorems
Some previous assertions will now be proved. ζ1p+ζ2p+ζ3p+...+ζnp≡(ζ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 ζ1p+ζ2p+ζ3p+...+ζnp≡(ζ1+ζ2+ζ3+...+ζn)(mod p), that is;(8) Vp,1≡V1,1(mod p).
Also, V1,1=-a1 and -Vp,1=a1Up-1+2a2Up-2+3a3Up-3+...+nanUp-n (by Theorem (5)), therefore;
(9) a1(Up-1-1)+2a2Up-2+3a3Up-3+...+nanUp-n≡0(mod p).
Finally, Theorem (3) will be proved. If Up-1+i-n≡Ui-n(mod p), i=1, 2, 3, ..., n, then by the matrix equation obtained in the proof of Theorems (2) and (4), Vp,2≡Vp,3≡Vp,4≡...≡Vp,n≡0(mod ), that is Vp,i≡V1,i(mod p), i=2, 3, 4, ..., n. Conversely, if Vp,i≡V1,i(mod p), i=2, 3, 4, ..., n, and p does not divide a1a2a3···an, then Up-1≡1, Up-2≡Up-3≡Up-4≡...≡Up-n≡0(mod p), that is, Up-1+i-n≡Ui-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.
