13
$\begingroup$

Given $$\phi = \frac{1 + \sqrt 5}{2},$$ it follows that in $\mathbb{Z}[\phi]$ we have $5 = (\sqrt 5)^2 = (-1 + 2 \phi)^2$, as it is obvious that $\langle 5 \rangle$ is a ramifying ideal.

But what about other Fibonacci numbers that are also prime? $13$ is also prime, I have triple-checked it. It looks like $89$ is also prime but I feel like I have made a mistake somewhere along the way. I'll start by doublechecking my Jacobi symbol calculation.

Clearly there are primes that split in $\mathbb{Z}[\phi]$. But when those primes are also Fibonacci numbers, is their primality also guaranteed in $\mathbb{Z}[\phi]$?

EDIT: I did make a mistake in my Legendre symbol calculation. That prevented me from finding $$\left(\frac{7}{2} - \frac{9 \sqrt 5}{2}\right) \left(\frac{7}{2} + \frac{9 \sqrt 5}{2}\right) = (8 - 9 \phi)(-1 + 9 \phi) = -89.$$ I am grateful for all the answers, whether already posted or yet to post.

$\endgroup$
  • 3
    $\begingroup$ It's certainly laborious to compute $5^{44} \pmod{89}$ by hand, and a mistake is almost certain to creep in along the way. However, thanks to quadratic reciprocity, you know the Legendre symbols $$\left(\frac{5}{89}\right) = \left(\frac{89}{5}\right)$$ and you can just do $89^2 \equiv 1 \pmod 5$. $\endgroup$ – Robert Soupe May 21 '17 at 1:34
  • 4
    $\begingroup$ If $F_n$ is prime, then $n$ is prime. In this case, $F_n$ remains prime in the field $\mathbf{Q}(\sqrt{5})$ if $n \equiv 3,7 \mod 10$, and splits if $n \equiv 1,9 \mod 10$. So, for example, $F_{3} = 2$, $F_{13} = 233$, $F_{23} = 28657$, $F_{43} = 433494437$, remain prime, $F_{7} = 13$, $F_{17} = 1597$, $F_{47} = 2971215073$ remain prime, whereas $F_{11} = 89$, $F_{131} = 1066340417491710595814572169$ split, as do $F_{29} = 514229$ and $F_{359}$ which equals $$ 475420437734698220747368027166749382927701417016557193662268716376935476241.$$ Proof: $F^2_{n}$ modulo $5$ is periodic modulo $10$. $\endgroup$ – Gordon May 21 '17 at 7:45
13
$\begingroup$

If I've done my sums correctly, $89$ is not prime in $\mathbb Z[\phi]$.

The minimal polynomial of $\phi$ is $t^2 - t - 1$, which factorises as $$ t^2 - t - 1 = (t - 10)(t - 80)$$ in the ring $\mathbb Z_{89}[t]$.

Therefore, using a criterion by Dekekind, we find that the principal ideal $\langle 89 \rangle $ factorises as $$ \langle 89 \rangle = \langle 89, \phi - 10 \rangle \langle89 , \phi - 80\rangle.$$

$\endgroup$
  • $\begingroup$ $13^3 - 5 \cdot 4^4 = 89$ and $u^2 - 5 v^2$ represents exactly the same integers as $x^2 - xy - y^2.$ Any prime $p \equiv \pm 1 \pmod 5,$ or a product of such $\endgroup$ – Will Jagy May 20 '17 at 21:59
  • $\begingroup$ Is there a name for this criterion? That's very cool. $\endgroup$ – law-of-fives May 20 '17 at 22:03
  • $\begingroup$ @law-of-fives I think it's called the "Dedekind factorization criterion" or something like that. See here for the statement: math.stackexchange.com/questions/38431/… $\endgroup$ – Kenny Wong May 20 '17 at 22:06
8
+200
$\begingroup$

I want to believe that there is some deep connection between Binet's formula for the Fibonacci numbers and splitting of primes in $\textbf Z[\phi]$. Looking at the formula discourages me from this line of thought, however:

$$F_n = \frac{\phi^n - (1 - \phi)^n}{-1 + 2 \phi}$$

At their core, the Fibonacci numbers seem to be essentially additive in nature, rather than multiplicative. Note also that $N(\phi) = N(1 - \phi) = -1$.

What really matters for determining if prime $F_n$ splits or is inert in $\textbf Z[\phi]$ is its congruence modulo $20$. We know that from $13$ on, prime $p = F_n \equiv 1 \pmod 4$. Then, by quadratic reciprocity, $$\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right) = p^2 \bmod 5.$$ If $p \equiv 1 \textrm { or } 9 \bmod 20$, then $p^2 \equiv 1 \bmod 5$. But if $p \equiv 13 \textrm { or } 17 \bmod 20$, then $p^2 \equiv -1 \bmod 5$.

Therefore, $13, 233, 1597, 28657, 433494437, 2971215073, \ldots$ are inert in $\textbf Z[\phi]$, while $89, 514229, 1066340417491710595814572169, \ldots$ split.

This is not to say that there isn't a deep connection between Binet's formula and $\textbf Z[\phi]$. It might exist but it might be much too deep for me to see it.

$\endgroup$
  • 2
    $\begingroup$ Actually, you can go easier, modulo 5, since $1^2 \equiv 4^2 \equiv 1 \pmod 5$ and $2^2 \equiv 3^2 \equiv -1 \pmod 5$. $\endgroup$ – Robert Soupe May 26 '17 at 15:58
  • 1
    $\begingroup$ We can simplify more. If $F_n$ is prime, then $n$ is odd (as $F_{2n} = F_n L_n$ where $L_n$ is a Lucas number). For $n$ odd, we have $F_n = \pm 1 \bmod 5$ if and only if $n = \pm 1 \bmod 5$. $\endgroup$ – David E Speyer Jul 18 '17 at 13:33
6
$\begingroup$

next $$ 10 - 5 \cdot 3^2 = 55 = 5 \cdot 11$$ $$ 13 - 5 \cdot 4^2 = 89$$ $$ 134 - 5 \cdot 7^2 = 17711 = 89 \cdot 199$$ $$ 305 - 5 \cdot 65^2 = 75025 = 5^2 \cdot 3001$$ $$ 893 - 5 \cdot 238^2 = 514229$$ $$ 26129 - 5 \cdot 10170^2 = 165580141 = 2789 \cdot 59369 $$

is the next prime Fibonacci that is $\pm 1 \pmod 5$ therefore can be written as $x^2 + xy - y^2$ in integers. $$ \color{blue}{ (u+v)^2 + (u+v)(-2v)- (-2v)^2 = u^2 - 5 v^2} $$

8 =  2^3
13 =  13
21 =  3 7
34 =  2 17
55 =  5 11
89 =  89
144 =  2^4 3^2
233 =  233
377 =  13 29
610 =  2 5 61
987 =  3 7 47
1597 =  1597
2584 =  2^3 17 19
4181 =  37 113
6765 =  3 5 11 41
10946 =  2 13 421
17711 =  89 199
28657 =  28657
46368 =  2^5 3^2 7 23
75025 =  5^2 3001
121393 =  233 521
196418 =  2 17 53 109
317811 =  3 13 29 281
514229 =  514229
832040 =  2^3 5 11 31 61
1346269 =  557 2417
2178309 =  3 7 47 2207
3524578 =  2 89 19801
5702887 =  1597 3571
9227465 =  5 13 141961
14930352 =  2^4 3^3 17 19 107
24157817 =  73 149 2221
39088169 =  37 113 9349
63245986 =  2 233 135721
102334155 =  3 5 7 11 41 2161
165580141 =  2789 59369
267914296 =  2^3 13 29 211 421
433494437 =  433494437
701408733 =  3 43 89 199 307
1134903170 =  2 5 17 61 109441
$\endgroup$
  • $\begingroup$ Would it be possible for you to explain the method in more detail? I stared at the sums but couldn't quite figure out how to use them to factorise the principal ideals. Since I'm not a specialist algebraic number theorist, I don't know all the tricks of the trade, so this is most likely my fault! $\endgroup$ – Kenny Wong May 20 '17 at 22:17
  • $\begingroup$ @KennyWong, the norm is the binary quadratic form $x^2 - xy - y^2,$ it might be a plus sign in the middle rather than the - I put. This form integrally represents exactly the same integers as $u^2 - 5 v^2.$ A number can only be primitively represented when all factors are either $5$ or primes $q \equiv \pm 1 \pmod 5.$ (indeed, primitively or not, for a number to be represented, all prime factors $q \equiv \pm 2 \pmod 5$ must occur to even exponents). From my little computer run, few Fibonacci numbers can be so expressed. $\endgroup$ – Will Jagy May 20 '17 at 22:24
  • $\begingroup$ Thanks! I suppose the thing I'm missing is the link between integral/primitive representations by quadratic forms and factorisation of principal ideals. Do you know a web link that explains this at an elementary level? Of course, this could well be beyond me. :) $\endgroup$ – Kenny Wong May 20 '17 at 22:54
  • 1
    $\begingroup$ @KennyWong how would you calculate the norm of the element $x + y \phi$ where $x,y$ are rational integers? I think it comes out $x^2 +xy - y^2.$ en.wikipedia.org/wiki/… $\endgroup$ – Will Jagy May 20 '17 at 23:05
  • 2
    $\begingroup$ Oh I totally get it!!! $\mathbb Q(\sqrt 5)$ has class number one, so the prime factor I'm looking for is itself a principal ideal $\langle x + \phi y \rangle$ with $N(x + \phi y) = p$. (And yes, it comes out as $x^2 + xy - y^2$ with the plus sign rather than the minus sign.) Thank you very much for being so patient while I was being so dumb! :) $\endgroup$ – Kenny Wong May 20 '17 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.