5 Using generating functions modulo m

Let us examine now some properties of the sequences . Defining and as the smallest positive indice such that, respectively, and , we want to reformulate the results, and shorten the proofs of [4]. In this section, will ever denotes a positive integer coprime with , because of :

Proposition 6  

When , the recurrence can be followed backwards and :

Proof. Follows from Binet's formula Eq. 11. When , a more complicated formula can be obtained by using Eq. 12.

Proposition 7  

The sequences are periodic. This periodicity is direct if and only if .

Proof. Since is finite, there must exist such that and . Due to the recurrence, is periodic from that point on. When the recurrence can be followed backwards, the periodicity is direct. On the other hand, Eq. 4 gives .

Proposition 8  

The period of any sequence divides the period of . When , both periods are equal.

Proof. The period of a basis is the lcm of all the periods, and is a basis if and only if has an inverse in .

Proposition 9  

It exists such that divides if and only if divides .

Proof. Consider the set . By definition, . By periodicity , is infinite. By Proposition 4, we have as soon as . This characterize an ideal of .

Theorem 3 (Robinson)  

Consider coprime with , as in Proposition 9, the multiplicative order of modulo , i.e the smallest such that and the multiplicative order of . Then the period of is given by  :

Proof. [A shorter proof]Let , . By Eq. 9, we have and , allowing to exist. From Proposition 4 and Eq. 6, the generating function of is : french

From Eq. 11, . From Eq. 9, . From Eq. 22, . Substituting these relations into , we obtain :

Therefore and is a period of . Conversely, let be the shortest period of . From , divides . From the value of , the smallest positive such that is .

To obtain the second part of Eq. 27, we remark that by Eq. 9 and by Eq. 4 so that . Equating the orders of both sides, we obtain our proof by :

We will now prove a usefull lemma, then examine what can be said for composite moduli, then for prime moduli and conclude by a closer look over the special case (e.g. the genuine Fibonacci).

Proposition 10  

Define where and is prime. Except from the special case , , odd, , is inversible in the ring :

Proof. From , and is invertible in except perhaps when . In this case, and . Suppose and even. Then , leading to that could not happen. It remains only to examine , .

If is even, is odd. Otherwise is even in the special case and odd otherwise.

Theorem 4   For composite modulus, ever assuming , we have :

1. When and are coprimes, then is the of and while is the of and .
2. For all primes , either or .
3. For all primes and all indices , except perhaps from the case  :
   
   

4. The oddest prime, . When is even, . When is odd, . In the special case of Proposition 10, implies .

Proof. Point 1 results from the Chinese remainder theorem. To obtain point 2, remark that the -sequence is the Fibonacci sequence associated to a recurrence whose poles are equal . Then apply thm:AL-primes, part 1 (that will be proved independantly). In point 3, the result is obvious if is really equal to 0, since in such a case .

Let , where and assume , . We have :

Substituting in Binet Eq. 11, we obtain an expansion of that starts by . When this is the only term. In the special case, and . Otherwise, and by Fermat, starts by . When , there are other terms, but the coefficients are binomials and therefore provide another factor except from the term in and we have again . The result concerning follows by recurrence over .

Concerning , let , , where . Resolving in and and substituting in Binet Eq. 11 leads to an expansion in where the coefficients are again binomials, and therefore divisible by except the coefficient of . This can be written as  :

leading to , except perhaps from the case . In this case, a direct examination shows that leads to , while leads to .

Theorem 5   The following rules apply when is prime (and ) :

(i) When divides , then and .

(ii) When is a quadratic residue , then is a divisor of .

(iii) Otherwise, divides , and divides .

Proof. This theorems results from :

(i) We have and .

(ii) Binet (11b). We have , thus by Fermat.

(iii) We have , thus by Frobenius. Therefore and . From the proof of thm:robinson, divides and divides .

Theorem 6   Assume that is odd and doesnt divide nor . Then :

(i) When then either is odd, is QR (quadratic residue ) and or is even, is QR and . Moreover, either and *** is QR or and *** is QR.

(ii) When then is QR and .

(iii) then either , is QR and or , is QR and .

(iv) Define . If is QR then (and divides ). Otherwise or .

Proof. Everywhere in this proof, we use the fact that solving a product is solving the factors. Therefore the current results arent granted for composite moduli.

Case . Assume odd, substitute , , , in Eq. 18 and obtain :

This requires french QR (and additionally QR). Then substitute in Eq. 9.

Case . Assume even and substitute in Eq. 18. Solve, substitute in Eq. 9 and obtain :

From the minimality of , case cannot occur. Case requires QR and implies odd while case leads to even.

Cases . ****

Cases . Assume even, and substitute , , in Eq. 18. Solve, substitute in Eq. 9 and obtain :

Therefore, case requires QR and implies while case requires QR and implies .

Case . Assume , substitute , , , in Eq. 18 and obtain :

This requires french QR (and additionally QR). Then substitute in Eq. 9.

(iv-a). Suppose that is QR. Then Eq. 18 applied to and gives :

so that either and or and . Substituting in Eq. 9, we obtain that equals when and otherwise.

(iv-b). Suppose that is not QR. Then Eq. 18 applied to and gives :

so that either and or and . Substituting in Eq. 9, we obtain that equals when and otherwise.

Theorem 7   When is an odd prime not dividing or , the behaviour of is ruled by the quadratic nature of , and . In the general case, there are eight classes, whose behaviour is given by tab:Behaviour.

Table 1: Behaviour of the eight classes of primes (assuming , , ).

			cases
			4	0		0		0	2
			3	1			0	0
			1, 4, 5	0		all		all
			1, 3, 5	1			all	all	4
			2b	1					1
			2a, 3, 4	0		0		0
			1, 5	1
			all	0		all	all	all	all

When is a perfect square, there are only four cases. When , as in the genuine Fibonacci case, is ever even (), and is either , or according to the column of tab:Behaviour.

Proof. Column comes from the equivalence of QR with and the definition . Column is (iv) above. Column is obtained as follows : when is odd and then and is odd ; when , then while : thus if is odd and if is even.

In line , we have while . Thus and have the same valuation and must be odd. Otherwise, the columns "cases", and are obtained by discarding all the possibilities that contradict the previous theorem.

When is QR , we can consider the Fibonacci sequence associated with the recurrence where . Then and both sequences share the same value.

When , then since has been excluded. By Robinson Eq. 27, is ever even and . When is odd, must be even and thus, again by Eq. 27, .

Proposition 11  

Assuming , and we have : if then is QR ; if then is QR ; otherwise and is QR.

Proposition 12  

Considering the genuine Fibonacci sequence, where . The special primes are and . It happens that while . For other primes, define . Then enforces , enforces and enforces . In the remaining case (), there are that gives .

Proposition 13  

When considering the Fibonacci sequence associated with , the only special prime is . It happens that . For other primes, define . Then enforces , enforces and enforces . In the remaining case (), there are that gives .

Proof. It is well known (Gauss) that is QR when and is QR (and therefore 8) when .

In the old ancient times, where the Fermat's last theorem was not allready proved, it has been nevertheless proved that a subcase of would imply the existence of a prime such that in the genuine Fibonacci sequence. Therefore, intensive computer aided searchs have been undertaken, ever with a negative result [1]. The fact that such primes actually exists for OTHER Fibonacci sequences (e.g. and in the sequence of Proposition 13) indicates that only specific methods can be used for this conjecture.