Some heuristics and conjectures about the Pisano Period, primes and Fibonacci primes.

This week I did some tests regarding the Pisano period (and a question at MSE) and I found the following four conditions to be true for the first 10.000 values of pi(n) (Pisano period for n).

I do not understand the reasons for the results: points 1-3 would work as a primality test, but it does not detect all the possible primes, only a subset of them, e.g. {2,5,47,107,113,139,…}do not comply with points 1-3 and are not detected. And specially the last point, if the test is correct, would mean that the Pisano period of a Fibonacci prime is exactly four times the index of the Fibonacci prime in the Fibonacci sequence when the index is greater than 5 (being F5=5) . For instance: pi(1597)=68 and 68/4=17 which is exactly the index of 1597 in the Fibonacci sequence, F(17)=1597.

According to the answer and comments in the question at MSE it is not clear if it would be true or not yet (there could be big pseudoprime counterexamples). After doing the question, I noticed that the first one (1) was already registered at the OEIS sequence in the "formula" section. It does not mean that it is correct, but at least nobody removed that information since 2002, so it might be significative. My other observations are not registered at OEIS though.

Hobbymath's wanderings #13

Hermite Polynomials (Wikipedia).

Hardy-Littlewood circle method (Wikipedia).

Introduction to the circle method.

Chinese Remainder Theorem.

On Higly Composite and Similar Numbers (Alaoglu, Erdős) (pdf).

Bézout's identity (Wikipedia).

Pisano period (Wikipedia).

Legendre symbol (Wikipedia).

Voronoi Diagram (Wikipedia).

Lloyd's algorithm (Wikipedia).

Voronoi pole (Wikipedia).

Golden_ratio (Wikipedia).

Fermat's spiral (Wikipedia).

Heegner number (Wikipedia).

Minkowski Space (Wikipedia).

Richard_Dedekind (Wikipedia).

Prime ideal (Wikipedia).

Quadratic Integer (Wikipedia).

Cardinality (Wikipedia).

How to solve simple Chinese Remainder Theorem problems when there are fractions in the congruence equations

Lately I have been trying to learn the use of the Chinese Remainder Theorem (CRT), and usually it gets quite complicated because sometimes will appear fractions in the congruence equations, I was looking for information at MSE (credits go for all the nice people answering questions there!) and finally I was able to solve a simple case of CRT including fractions! These are my personal notes, it is just not to forget it and probably there are some lags, so be careful if you use it. Initially I think the explanation is correct and at least will be able to guide the beginners like me in this kind of problems.

Generic Problem: 1/B = C (mod D) where I want to know the value of  C and I know B and D. Constraint: B must be coprime to D.

We will use these equivalences:

Bx+1 = 0 (mod Bx+1)
1 = -Bx (mod Bx+1)
(a) 1/B = -x = -x+(Bx+1) = (B-1)x+1 (mod Bx+1)

Bx+1=D, then x=(D-1)/B, replacing x at (a) we have:

(b) 1/B = ((B-1)(D-1)/B)+1 (mod D)

Example:

1/2 = ? (mod 7)

2 is coprime to 7

2x+1=0 (mod 2x+1)

1=-2x (mod 2x+1)

1/2=-x=-x+2x+1=x+1 (mod 2x+1)

2x+1=7, thus x=3, then:

1/2 = 4 (mod 7)

Generic Problem: A/B = C (mod D) where I want to know the value of  C and I know A,B and D. Constraint: A!=1 and B must be coprime to D.

A/B = C (mod D)

This is equivalent to solve the following couple of congruences:

(a) Ax = C (mod D)

(b) Bx = 1 (mod D) 

First solve (b) Bx = 1 (mod D) by a special case of the Euclidean Algorithm (original from Gauss), I will call it GEA:

-------------------------

Algorithm GEA: we want to find the values x for Bx = R (mod D) knowing B,R and D:

(1) Convert R/B into NR/NB ( for the least N such as NB >= D) 

(2) Reduce mod D both terms of the fraction and then simplify the fraction if possible

(3) If denominator is 1 finish, if not again (1)

(4) The numerator N is the solution so:

x = N (mod D)

That implies:

x=Dk+N for a certain k

-------------------------

 We have solved (b), so now replacing at (a) x = Dk+N

(c) A(Dk+N) = C (mod D)

So now we can simplify the expression to obtain the value of C that will depend on the variable k.

Example:

6/5 = ? (mod 7)

5 is coprime with 7

is equivalent to:

(a) 6x=? (mod 7)

(b) 5x=1 (mod 7)

Solve (b)

GEA: 1/5 = 2/10 = 2/3 = 6/9 = 6/2 = 3 , thus:

(b) x=3 (mod 7)

meaning:

x=7k+3

Replacing in (a)

(a) 6(7k+3) (mod 7) = 42k+18 (mod 7) = 0+4 (mod 7)  = 4 (mod 7)

meaning that:

6/5 = 4 (mod 7)

As I said these are my personal notes, please use them carefully!