41
$\begingroup$

The problem is as follows:

Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, than $${F_{n}}^2 - 28$$

cannot be a prime.

I came across this problem accidentally while trying to solve another problem.

I suspect that there is an identity involving ${F_{n}}^2 - 28$ that proves that it is a composite. On the other hand, it is a kind of odd and counter-intuitive to imagine an identity involving number $28$...

$\endgroup$
  • $\begingroup$ Is $F$ for Fermat or Fibonacci? What about $F_0,F_1$ in the first case, or $F_5$ in the second? $\endgroup$ – abiessu Jan 4 '15 at 2:12
  • 1
    $\begingroup$ What about $3^2-28=-19$ and $5^2-28=-3$? $\endgroup$ – Barry Cipra Jan 4 '15 at 2:31
  • 5
    $\begingroup$ By brute force, aside from $n = 4$ and $5$, there are no more $n \le 3000$ where $F_n^2 - 28$ is prime. $\endgroup$ – achille hui Jan 4 '15 at 2:46
  • 2
    $\begingroup$ @achillehui How did you run that brute force? The larger $F_n$ are too big for general-purpose factoring algorithms to work; did you sieve modulo small factors, and if so, what was the largest 'smallest factor' in that range? $\endgroup$ – Steven Stadnicki Jan 4 '15 at 2:53
  • 2
    $\begingroup$ @StevenStadnicki I use the primep() function in maxima to test for primality. It uses Miller-Rabin's and Lucas pseudo-primality test. If $primep(n)$ returns false, $n$ is a composite number. If it returns true, then $n$ is a prime number with very high probability. i.e it can return false positive but not false negative. $\endgroup$ – achille hui Jan 4 '15 at 3:12
41
$\begingroup$

${F_n}^2 - 28$ indeed can not be a prime number for $n>5$.

Let's suppose that ${F_n}^2 - 28$ is a prime. In that case, $n$ must be even, this was shown (easily using congruences) in other answers, so I'll omit this part for space saving. I'll also use known identity $5{F_n}^2 = {L_n}^2 - 4$ valid for even $n$ ($L_n$ is $n$-th Lucas number). It follows that that:

$$5({F_n}^2-28) = 5{F_n}^2-140 = ({L_n}^2 - 4) - 140 = {L_n}^2-144 = (L_n-12)(L_n+12)$$

${F_n}^2 - 28$ could be prime only if one of $L_n - 12$ and $L_n + 12$ are $1$, $5$, $-1$, $-5$, and those are just few cases of small $n$. For all others, ${F_n}^2 - 28$ can not be a prime.


Possible generalization: Expressions ${F_n}^2 - (k^2 - 4)/5$ (k is any natural number) could be candidates for a similar proof. However, some other bits and peaces (like proving that $n$ must be even) must be valid too, and this is often not true. However, it looks that, for instance, ${F_n}^2 - 145$ satisfies all conditions, and also can be reduced to $({L_n}^2 - 4) - 725$ and finally to $(L_n-27)(L_n+27)$.

Outside such generalization, it seems that the original statement (or its slightly modified version related only to condition $n>5$) is valid for ${F_n}^2 - 13$, ${F_n}^2 - 31$, ${F_n}^2 - 45$, ${F_n}^2 - 58$, ${F_n}^2 - 78$, ${F_n}^2 - 85$, ${F_n}^2 - 91$, ${F_n}^2 - 115$, ${F_n}^2 - 133$, ${F_n}^2 - 142$, ${F_n}^2 - 154$, ${F_n}^2 - 175$, ${F_n}^2 - 211$, ${F_n}^2 - 217$. (warning: I checked then with the help of a computer, and only for $n<1000$; please see comments for an interesting example involving $n>1000$)

Now, for the sake of curiosity, let us take a look at one of these cases. Case ${F_n}^2 - 85$ can be proven using congruences for $2$, $3$, $17$, and $107$ only. This means that one of $2$, $3$, $17$, and $107$ is always a divisor of ${F_n}^2 - 85$. Original case ${F_n}^2 - 28$ is fundamentally different, and, if I may say, "more beautiful", in the sense that it can have (and often has) only huge divisors, like in these examples:

$${F_{20}}^2 - 28 = 3023\times15139$$ $${F_{172}}^2 - 28 = 10348333\times53505724471\times315619755257\times10455376853041\times82024860865049\times1040059595540327$$


For users of Mathematica, this code:

Select[Table[Fibonacci[n], {n, 1, 1000}], PrimeQ[#*# + 3] &]

returns primes of the form ${F_n}^2+3$, for $1\le n\le 1000$. In this case there are $6$ such primes:

{

 2,

 8,

 3524578,

 27777890035288, 

 2011595611835338993891308327102733537615455242513357158345612749706882\
 9146295425939723629305572732574726246290673965789878845363842331040064\
 16432124798818261534841714338,

 2949592466076064248964701302014885591673737506156850406413751530665307\
 5810241060939483954895520932111023343610904846943097162533007651451709\
 723277579925520157875345780869307228929160

}

$\endgroup$
  • 1
    $\begingroup$ $F_{1944}^2-13$ is prime. $\endgroup$ – P.-S. Park Jan 30 '15 at 16:33
  • $\begingroup$ Yes, I checked only for n<1000. Good point, it is an example how far a counterexample can exist! @P.-S.Park $\endgroup$ – VividD Jan 30 '15 at 17:04
  • $\begingroup$ @VividD: I corrected a small typo. It should be $2,3,\color{blue}{17},107$ since $17\mid F_{36m}^2-85$. $\endgroup$ – Tito Piezas III Aug 5 '15 at 4:24
  • $\begingroup$ @VividD: There are small counter-examples. If the original statement is for $n>5$, note that $F_{\color{brown}6}^2-45$ and $F_{\color{brown}8}^2-58$ in fact are primes. $\endgroup$ – Tito Piezas III Aug 5 '15 at 4:38
  • $\begingroup$ @TitoPiezasIII, thanks, good point, I slightly changed the text to warn the potential reader. $\endgroup$ – VividD Aug 24 '15 at 11:25
17
$\begingroup$

You're correct: $F_n^2-28$ is never a prime for $n\geq 6$, i.e., all $n$ where $F_n^2-28\gt 0$; arguably it's prime for $n=4$ ($F_4^2-28=-19$) and $n=5$ ($F_5^2-28=-3$).

First of all, note that if $3\not\mid F_n$, then $F_n^2\equiv 1\equiv 28\pmod 3$, so $3\mid F_n^2-28$. We can therefore assume in what follows that $3\mid F_n$ and therefore that $4\mid n$.

Now, (defining $G_n=F_n^2-28$ for convenience in what follows:) numeric evidence suggests the conjecture that for all $n$ divisible by $4$ there's some $a$ with $G_n=5a^2+24a = a\times(5a+24)$. We can prove this (and thus provide a factorization for all $n$) as follows:

Suppose that $G_n=5a^2+24a$; in other words, $5a^2+24a-G_n=0$. The (positive) solution to this quadratic equation is $a=\frac1{10}\left(-24+\sqrt{24^2+20G_n}\right)$. We'll first show that this quantity is rational, and then that it's integral. Note that $24^2+20G_n=24^2+20(F_n^2-28)=16+20F_n^2$, so $\sqrt{24^2+20G_n}=2\sqrt{4+5F_n^2}$. But since $n$ is even, we have $4+5F_n^2=L_n^2$ where $L_n$ is the $n$th Lucas number (a sort of conjugate to the Fibonacci numbers, satisfying the same recurrence). Clearly $2L_n-24$ is divisible by $2$; its divisibility by $5$ is equivalent to saying that $2L_n\equiv -1\bmod 5$ or that $L_n=2\bmod 5$. But this follows since, as noted at the start, we're in the case $4\mid n$ (and because the period of the Lucas numbers mod $5$ is $4$). This implies the integrality of $a$, which in turn implies the desired factorization of $G_n$.

$\endgroup$
  • 1
    $\begingroup$ Thanks for bringing this approach, Steven. Really interesting method, maybe it can lead in some modified form to the full solution. $\endgroup$ – VividD Jan 4 '15 at 2:42
  • $\begingroup$ This case n=92 is really intimidating..., but so is n=20... $\endgroup$ – VividD Jan 4 '15 at 2:54
  • $\begingroup$ Except for $n=68,76$, there doesn't appear to be a repeated factor... $\endgroup$ – abiessu Jan 4 '15 at 2:58
  • $\begingroup$ It looks to me that factors can be divided into 2 groups, and one group (as product of its members) is around 5 times larger that the other. But I didn't check all. $\endgroup$ – VividD Jan 4 '15 at 3:02
  • $\begingroup$ Hey, 197 * 85584807236027447 / 3372041405099481407 is very close to 5. $\endgroup$ – VividD Jan 4 '15 at 3:13
11
$\begingroup$

The recurrence for the squares of the Fibonacci numbers is $$ x_n=2x_{n-1}+2x_{n-2}-x_{n-3} $$ Thus a repeat of a subsequence of length $3$ implies a repeat of the entire sequence.


mod $2$, we get $$ \overbrace{0,1,1},\overbrace{0,1,1},\dots $$ Thus, for $n\equiv0\pmod3$, we have that $F_n^2-28\equiv0\pmod2$


mod $3$, we get $$ \overbrace{0,1,1},1,\overbrace{0,1,1},\dots $$ Thus, for $n\not\equiv0\pmod4$, we have $F_n^2-28\equiv0\pmod3$


mod $7$, we get $$ \overbrace{0,1,1},4,2,4,1,1,\overbrace{0,1,1},\dots $$ Thus, for $n\equiv0\pmod8$, we have that $F_n^2-28\equiv0\pmod7$


The only thing not covered above is $n\equiv4\pmod{24}$ and $n\equiv20\pmod{24}$.

Recall that $F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$ where $\alpha$ and $\beta$ are the roots of $x^2-x-1=0$. Note that $(\alpha-\beta)^2=5$ and $\alpha\beta=-1$. Using these relations, it is not difficult to obtain $$ \begin{align} 5(F_{2k}^2-28) &=5F_{2k}^2-140\\ &=\alpha^{4k}+\beta^{4k}-142\\ &=\left(\alpha^{2k}+\beta^{2k}\right)^2-144\\ &=\left(L_{2k}-12\right)\left(L_{2k}+12\right) \end{align} $$ where $L_n=\alpha^n+\beta^n$ is a Lucas Number. In an argument similar to those above, it can be shown that $L_{2k}-12\equiv0\pmod5$ for even $k$ and $L_{2k}+12\equiv0\pmod5$ for odd $k$.

This covers the case of all even values of $n$ for $n\ge6$ since $L_6=18$ and $L_n$ is monotonically increasing after that.


The cases above cover all $n\ge6$, which are the cases for which $F_n^2-28\ge0$. Specifically:

If $n$ is odd, $F_n^2-28=3\cdot\frac{F_n^2-28}3$

If $n=0\pmod4$, $F_n^2-28=\frac{L_n-12}{5}(L_n+12)$

If $n=2\pmod4$, $F_n^2-28=9\cdot\frac{L_n-12}3\frac{L_n+12}{15}$

The argument above can be simplified by ignoring the cases mod $2$ and mod $7$ since only the case mod $3$ and the Lucas number argument is needed.

I see that the Lucas number identity has already been noted in another answer while I've worked on this answer, but I will include it for completeness.

$\endgroup$
  • $\begingroup$ should also be a degree two recurrence, but with a constant term or one of those annoying $(-1)^n$ $\endgroup$ – Will Jagy Jan 4 '15 at 5:10
  • 1
    $\begingroup$ @WillJagy: That's true, but I used a degree 3 recurrence to get rid of the $(-1)^n$. $\endgroup$ – robjohn Jan 4 '15 at 5:16
  • 1
    $\begingroup$ I think that the same statement for $F_n^2 - 85$ can be proven using only congruences for 2, 3, 17 and 107. Case "28" is so different than case "85". $\endgroup$ – VividD Jan 4 '15 at 18:30
  • $\begingroup$ @VividD: Indeed. That works. $\endgroup$ – robjohn Jan 4 '15 at 19:41
4
$\begingroup$

After Steven and robjohn's answers, it seemed useful to write a command (C++ with GMP) to do Fermat's factoring, try to write some large number $n$ as $x^2 - y^2$ with small $y.$ slight generalization, needed for this problem, write $$ \color{magenta}{ zn = x^2 - y^2} $$ with small $z,y.$ So, I did that; much variety for the first few. See how this method, stopped early, does not detect small factors such as $2,3,7.$ If there are several ways to do the task, the program prints out the first dozen $(z,y)$ pairs; in any case, $z^2 + y^2$ is no larger than a bound provided by the programmer (me).

6  8      Fermat:  ( 1 , 0 );  ( 1 , 8 );  ( 2 , 3 );  ( 2 , 7 );  ( 2 , 17 );  ( 3 , 6 );  ( 3 , 26 );  ( 4 , 0 );  ( 4 , 5 );  ( 4 , 9 );  ( 4 , 16 );  ( 5 , 4 ); 
7  13      Fermat:  ( 1 , 22 );  ( 3 , 19 );  ( 5 , 16 );  ( 7 , 13 );  ( 9 , 10 );  ( 11 , 7 );  ( 13 , 4 );  ( 15 , 1 );  ( 17 , 2 );  ( 19 , 5 );  ( 21 , 8 );  ( 23 , 11 ); 
8  21      Fermat:  ( 1 , 26 );  ( 3 , 19 );  ( 5 , 12 );  ( 7 , 5 );  ( 9 , 2 );  ( 11 , 9 );  ( 13 , 16 );  ( 15 , 23 );  ( 20 , 24 );  ( 24 , 17 );  ( 28 , 10 ); 
9  34      Fermat:  ( 3 , 29 );  ( 4 , 23 );  ( 5 , 17 );  ( 6 , 11 );  ( 7 , 5 );  ( 8 , 1 );  ( 9 , 7 );  ( 10 , 13 );  ( 11 , 19 );  ( 12 , 25 );  ( 25 , 19 );  ( 26 , 16 ); 
10  55      Fermat:  ( 1 , 22 );  ( 3 , 15 );  ( 5 , 12 );  ( 8 , 7 );  ( 16 , 3 );  ( 20 , 24 );  ( 21 , 8 ); 
11  89      Fermat: 
12  144      Fermat:  ( 5 , 12 );  ( 6 , 19 );  ( 20 , 24 );  ( 22 , 7 ); 
13  233      Fermat: 
14  377      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
15  610      Fermat:  ( 2 , 25 );  ( 17 , 1 ); 
16  987      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
17  1597      Fermat: 
18  2584      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
19  4181      Fermat: 
20  6765      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
21  10946      Fermat: 
22  17711      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
23  28657      Fermat: 
24  46368      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
25  75025      Fermat: 
26  121393      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
27  196418      Fermat: 
28  317811      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
29  514229      Fermat: 
30  832040      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
31  1346269      Fermat: 
32  2178309      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
33  3524578      Fermat: 
34  5702887      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
35  9227465      Fermat: 
36  14930352      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
37  24157817      Fermat: 
38  39088169      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
39  63245986      Fermat: 
40  102334155      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
41  165580141      Fermat: 
42  267914296      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
43  433494437      Fermat: 
44  701408733      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
45  1134903170      Fermat: 
46  1836311903      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
47  2971215073      Fermat: 
48  4807526976      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
49  7778742049      Fermat: 
50  12586269025      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
51  20365011074      Fermat: 
52  32951280099      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
53  53316291173      Fermat: 
54  86267571272      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
55  139583862445      Fermat: 
56  225851433717      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
57  365435296162      Fermat: 
58  591286729879      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
59  956722026041      Fermat: 
60  1548008755920      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
61  2504730781961      Fermat: 
62  4052739537881      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
63  6557470319842      Fermat: 
64  10610209857723      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
65  17167680177565      Fermat: 
66  27777890035288      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
67  44945570212853      Fermat: 
68  72723460248141      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
69  117669030460994      Fermat: 
70  190392490709135      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
71  308061521170129      Fermat: 
72  498454011879264      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
73  806515533049393      Fermat: 
74  1304969544928657      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
75  2111485077978050      Fermat: 
76  3416454622906707      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
77  5527939700884757      Fermat: 
78  8944394323791464      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
79  14472334024676221      Fermat: 
80  23416728348467685      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
81  37889062373143906      Fermat: 
82  61305790721611591      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
83  99194853094755497      Fermat: 
84  160500643816367088      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
85  259695496911122585      Fermat: 
86  420196140727489673      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
87  679891637638612258      Fermat: 
88  1100087778366101931      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
89  1779979416004714189      Fermat: 
90  2880067194370816120      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
91  4660046610375530309      Fermat: 
92  7540113804746346429      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
93  12200160415121876738      Fermat: 
94  19740274219868223167      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
95  31940434634990099905      Fermat: 
96  51680708854858323072      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
97  83621143489848422977      Fermat: 
98  135301852344706746049      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
99  218922995834555169026      Fermat: 
100  354224848179261915075      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
101  573147844013817084101      Fermat: 
102  927372692193078999176      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
103  1500520536206896083277      Fermat: 
104  2427893228399975082453      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
105  3928413764606871165730      Fermat: 
106  6356306993006846248183      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
107  10284720757613717413913      Fermat: 
108  16641027750620563662096      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
109  26925748508234281076009      Fermat: 
110  43566776258854844738105      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
111  70492524767089125814114      Fermat: 
112  114059301025943970552219      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
113  184551825793033096366333      Fermat: 
114  298611126818977066918552      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
115  483162952612010163284885      Fermat: 
116  781774079430987230203437      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
117  1264937032042997393488322      Fermat: 
118  2046711111473984623691759      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
119  3311648143516982017180081      Fermat: 
120  5358359254990966640871840      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
121  8670007398507948658051921      Fermat: 
122  14028366653498915298923761      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
123  22698374052006863956975682      Fermat: 
124  36726740705505779255899443      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
125  59425114757512643212875125      Fermat: 
126  96151855463018422468774568      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
127  155576970220531065681649693      Fermat: 
128  251728825683549488150424261      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
129  407305795904080553832073954      Fermat: 
130  659034621587630041982498215      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
131  1066340417491710595814572169      Fermat: 
132  1725375039079340637797070384      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
133  2791715456571051233611642553      Fermat: 
134  4517090495650391871408712937      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
135  7308805952221443105020355490      Fermat: 
136  11825896447871834976429068427      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
137  19134702400093278081449423917      Fermat: 
138  30960598847965113057878492344      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
139  50095301248058391139327916261      Fermat: 
140  81055900096023504197206408605      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
141  131151201344081895336534324866      Fermat: 
142  212207101440105399533740733471      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
143  343358302784187294870275058337      Fermat: 
144  555565404224292694404015791808      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
145  898923707008479989274290850145      Fermat: 
146  1454489111232772683678306641953      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
147  2353412818241252672952597492098      Fermat: 
148  3807901929474025356630904134051      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
149  6161314747715278029583501626149      Fermat: 
150  9969216677189303386214405760200      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
151  16130531424904581415797907386349      Fermat: 
152  26099748102093884802012313146549      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
153  42230279526998466217810220532898      Fermat: 
154  68330027629092351019822533679447      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
155  110560307156090817237632754212345      Fermat: 
156  178890334785183168257455287891792      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
157  289450641941273985495088042104137      Fermat: 
158  468340976726457153752543329995929      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
159  757791618667731139247631372100066      Fermat: 
160  1226132595394188293000174702095995      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
161  1983924214061919432247806074196061      Fermat: 
162  3210056809456107725247980776292056      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
163  5193981023518027157495786850488117      Fermat: 
164  8404037832974134882743767626780173      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
165  13598018856492162040239554477268290      Fermat: 
166  22002056689466296922983322104048463      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
167  35600075545958458963222876581316753      Fermat: 
168  57602132235424755886206198685365216      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
169  93202207781383214849429075266681969      Fermat: 
170  150804340016807970735635273952047185      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
171  244006547798191185585064349218729154      Fermat: 
172  394810887814999156320699623170776339      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
173  638817435613190341905763972389505493      Fermat: 
174  1033628323428189498226463595560281832      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
175  1672445759041379840132227567949787325      Fermat: 
176  2706074082469569338358691163510069157      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
177  4378519841510949178490918731459856482      Fermat: 
178  7084593923980518516849609894969925639      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
179  11463113765491467695340528626429782121      Fermat: 
180  18547707689471986212190138521399707760      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
181  30010821454963453907530667147829489881      Fermat: 
182  48558529144435440119720805669229197641      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
183  78569350599398894027251472817058687522      Fermat: 
184  127127879743834334146972278486287885163      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
185  205697230343233228174223751303346572685      Fermat: 
186  332825110087067562321196029789634457848      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
187  538522340430300790495419781092981030533      Fermat: 
188  871347450517368352816615810882615488381      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
189  1409869790947669143312035591975596518914      Fermat: 
190  2281217241465037496128651402858212007295      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
191  3691087032412706639440686994833808526209      Fermat: 
192  5972304273877744135569338397692020533504      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
193  9663391306290450775010025392525829059713      Fermat: 
194  15635695580168194910579363790217849593217      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
195  25299086886458645685589389182743678652930      Fermat: 
196  40934782466626840596168752972961528246147      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
197  66233869353085486281758142155705206899077      Fermat: 
198  107168651819712326877926895128666735145224      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
199  173402521172797813159685037284371942044301      Fermat: 
200  280571172992510140037611932413038677189525      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
201  453973694165307953197296969697410619233826      Fermat: 
202  734544867157818093234908902110449296423351      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
203  1188518561323126046432205871807859915657177      Fermat: 
204  1923063428480944139667114773918309212080528      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
205  3111581989804070186099320645726169127737705      Fermat: 
206  5034645418285014325766435419644478339818233      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
207  8146227408089084511865756065370647467555938      Fermat: 
208  13180872826374098837632191485015125807374171      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
209  21327100234463183349497947550385773274930109      Fermat: 
210  34507973060837282187130139035400899082304280      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
211  55835073295300465536628086585786672357234389      Fermat: 
212  90343046356137747723758225621187571439538669      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
213  146178119651438213260386312206974243796773058      Fermat: 
214  236521166007575960984144537828161815236311727      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
215  382699285659014174244530850035136059033084785      Fermat: 
216  619220451666590135228675387863297874269396512      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
217  1001919737325604309473206237898433933302481297      Fermat: 
218  1621140188992194444701881625761731807571877809      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
219  2623059926317798754175087863660165740874359106      Fermat: 
220  4244200115309993198876969489421897548446236915      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
221  6867260041627791953052057353082063289320596021      Fermat: 
222  11111460156937785151929026842503960837766832936      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
223  17978720198565577104981084195586024127087428957      Fermat: 
224  29090180355503362256910111038089984964854261893      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
225  47068900554068939361891195233676009091941690850      Fermat: 
226  76159080909572301618801306271765994056795952743      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
227  123227981463641240980692501505442003148737643593      Fermat: 
228  199387062373213542599493807777207997205533596336      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
229  322615043836854783580186309282650000354271239929      Fermat: 
230  522002106210068326179680117059857997559804836265      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
231  844617150046923109759866426342507997914076076194      Fermat: 
232  1366619256256991435939546543402365995473880912459      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
233  2211236406303914545699412969744873993387956988653      Fermat: 
234  3577855662560905981638959513147239988861837901112      Fermat:  ( 5 , 12 );  ( 20 , 24 ); 
jagy@phobeusjunior:

Here is the command:

string mp_Factored_Fermat( mpz_class  i, int bound)
{

  int squarefac = 0;
  string fac;
  fac = "   Fermat: ";

  int count = 0;

  for(int z = 1; count < 12 &&  z * z <= bound; ++z){
  for(int x = 0;  count < 12 && x * x + z * z <= bound; ++x){
    if (  mp_SquareQ( z * i + x * x )   )
    {
      ++count;
      fac += " ( ";
      fac += stringify( z) ;
          fac += " , ";
      fac += stringify( x) ;
       fac += " ); ";
    }

  }}


  return fac;
} // mp_Factored_Fermat

In case anyone gets interested, this calls

string stringify(unsigned int x)
 {
   ostringstream o;
   o << x  ;
   return o.str();
 }

I should find out whether there is a direct "stringify" command that makes a string from an mpz_class. Probably. YES. If n is an mpz_class, we get a C++ string from n.get_str()

Well, live and loin. The odd index entries are divisible by small primes, 2 or 3, detectable quickly by trial division, the even index entries have huge factors, detectable quickly by a slight modification of Fermat's favorite technique.

6  8    = 2^2 cdot 3^2
7  13    = 3  cdot 47
8  21    = 7  cdot 59
9  34    = 2^3 cdot 3  cdot 47
10  55    = 3^4  cdot 37
11  89    = 3^2  cdot 877
12  144    = 2^2 cdot 31  cdot 167
13  233    = 3^2  cdot 6029
14  377    = 3^3 cdot 19  cdot 277
15  610    = 2^3 cdot 3 cdot 37  cdot 419
16  987    = 7 cdot 317  cdot 439
17  1597    = 3 cdot 271  cdot 3137
18  2584    = 2^2 cdot 3^2 cdot 31^2  cdot 193
19  4181    = 3  cdot 5826911
20  6765    = 3023  cdot 15139
21  10946    = 2^3 cdot 3  cdot 4992287
22  17711    = 3^3 cdot 19 cdot 53 cdot 83  cdot 139
23  28657    = 3^2 cdot 37 cdot 47 cdot 137  cdot 383
24  46368    = 2^2 cdot 7 cdot 139 cdot 373  cdot 1481
25  75025    = 3^2 cdot 47 cdot 953  cdot 13963
26  121393    = 3^6 cdot 1117  cdot 18097
27  196418    = 2^3 cdot 3 cdot 6803  cdot 236293
28  317811    = 37 cdot 311 cdot 457  cdot 19207
29  514229    = 3 cdot 103 cdot 227  cdot 3769891
30  832040    = 2^2 cdot 3^2 cdot 62017  cdot 310081
31  1346269    = 3  cdot 604146740111
32  2178309    = 7 cdot 19 cdot 53 cdot 691  cdot 974167
33  3524578    = 2^3 cdot 3  cdot 517610419919
34  5702887    = 3^3 cdot 251 cdot 1093 cdot 1129  cdot 3889
35  9227465    = 3^4 cdot 197 cdot 223  cdot 23928127
36  14930352    = 2^2 cdot 727 cdot 22961  cdot 3338527
37  24157817    = 3^3  cdot 21614819340943
38  39088169    = 3^3 cdot 1942307  cdot 29134597
39  63245986    = 2^3 cdot 3 cdot 47 cdot 384487  cdot 9223063
40  102334155    = 7 cdot 19 cdot 103 cdot 449 cdot 14561  cdot 116927
41  165580141    = 3 cdot 47  cdot mbox{BIG} 
42  267914296    = 2^2 cdot 3^2 cdot 31 cdot 587 cdot 34019  cdot 3220831
43  433494437    = 3 cdot 643 cdot 4575983  cdot 21288763
44  701408733    = 271 cdot 1157489  cdot 1568397619
45  1134903170    = 2^3 cdot 3 cdot 3391 cdot 26459  cdot 598143187
46  1836311903    = 3^4 cdot 1979 cdot 138323  cdot 152078453
47  2971215073    = 3^2 cdot 21821  cdot 44952207150209
48  4807526976    = 2^2 cdot 7 cdot 31 cdot 37 cdot 2099 cdot 9887  cdot 34677281
49  7778742049    = 3^2 cdot 69191  cdot 97168751659867
50  12586269025    = 3^3 cdot 19^2 cdot 59 cdot 137 cdot 643  cdot 3127083679
51  20365011074    = 2^3 cdot 3 cdot 3547 cdot 3947  cdot 1234325623303
52  32951280099    = 131 cdot 26431 cdot 557537  cdot 562452689
53  53316291173    = 3 cdot 37 cdot 10771  cdot mbox{BIG} 
54  86267571272    = 2^2 cdot 3^2 cdot 141511 cdot 227191  cdot 6430005121
55  139583862445    = 3 cdot 47 cdot 1783 cdot 2939579  cdot 26364214181
56  225851433717    = 7 cdot 1487 cdot 5431 cdot 2656807  cdot 339622837
57  365435296162    = 2^3 cdot 3 cdot 47 cdot 19433 cdot 477767  cdot 12751341727
58  591286729879    = 3^3 cdot 19 cdot 29173  cdot mbox{BIG} 
59  956722026041    = 3^2 cdot 19853  cdot mbox{BIG} 
60  1548008755920    = 2^2 cdot 3089 cdot 116819  cdot mbox{BIG} 
61  2504730781961    = 3^2 cdot 37 cdot 277 cdot 176317  cdot mbox{BIG} 
62  4052739537881    = 3^4 cdot 83 cdot 20627 cdot 20693 cdot 39209  cdot 145978529
63  6557470319842    = 2^3 cdot 3 cdot 131  cdot mbox{BIG} 
64  10610209857723    = 7 cdot 103 cdot 3407  cdot mbox{BIG} 
65  17167680177565    = 3 cdot 2297  cdot mbox{BIG} 
66  27777890035288    = 2^2 cdot 3^2 cdot 37 cdot 59 cdot 88169 cdot 398011  cdot 279789416173
67  44945570212853    = 3 cdot 131 cdot 1571 cdot 1901  cdot mbox{BIG} 
68  72723460248141    = 19 cdot 139  cdot mbox{BIG} 
69  117669030460994    = 2^3 cdot 3 cdot 20897  cdot mbox{BIG} 
70  190392490709135    = 3^3 cdot 139 cdot 4451  cdot mbox{BIG} 
71  308061521170129    = 3^3 cdot 47 cdot 1229  cdot mbox{BIG} 
72  498454011879264    = 2^2 cdot 7 cdot 31 cdot 383 cdot 36877  cdot mbox{BIG} 
73  806515533049393    = 3^4 cdot 47  cdot mbox{BIG} 
74  1304969544928657    = 3^3 cdot 569 cdot 1627  cdot mbox{BIG} 
75  2111485077978050    = 2^3 cdot 3 cdot 103 cdot 15091  cdot mbox{BIG} 
76  3416454622906707    = 19 cdot 53 cdot 3838231  cdot mbox{BIG} 
77  5527939700884757    = 3 cdot 1091 cdot 7109  cdot mbox{BIG} 
78  8944394323791464    = 2^2 cdot 3^2 cdot 31 cdot 131  cdot mbox{BIG} 
79  14472334024676221    = 3 cdot 203617  cdot mbox{BIG} 
80  23416728348467685    = 7 cdot 2137 cdot 119087  cdot mbox{BIG} 
81  37889062373143906    = 2^3 cdot 3 cdot 953 cdot 2801 cdot 2290829  cdot mbox{BIG} 
82  61305790721611591    = 3^5 cdot 227 cdot 3929 cdot 10099 cdot 37579 cdot 1334947  cdot 34229552551
83  99194853094755497    = 3^2 cdot 168143  cdot mbox{BIG} 
84  160500643816367088    = 2^2 cdot 68099 cdot 95063  cdot mbox{BIG} 
85  259695496911122585    = 3^2 cdot 317  cdot mbox{BIG} 
86  420196140727489673    = 3^3 cdot 19 cdot 37 cdot 53 cdot 4202911  cdot mbox{BIG} 
87  679891637638612258    = 2^3 cdot 3 cdot 47 cdot 29401 cdot 357197  cdot mbox{BIG} 
88  1100087778366101931    = 7 cdot 137 cdot 4903 cdot 10223 cdot 187373 cdot 10234897  cdot 13128204456583
89  1779979416004714189    = 3 cdot 47 cdot 1117  cdot mbox{BIG} 
90  2880067194370816120    = 2^2 cdot 3^2 cdot 283 cdot 35363 cdot 5160157 cdot 5881991  cdot mbox{BIG} 
91  4660046610375530309    = 3 cdot 37 cdot 811  cdot mbox{BIG} 
92  7540113804746346429    = 197  cdot mbox{BIG} 
93  12200160415121876738    = 2^3 cdot 3  cdot mbox{BIG} 
94  19740274219868223167    = 3^3 cdot 19 cdot 7673 cdot 62851 cdot 137707  cdot mbox{BIG} 
95  31940434634990099905    = 3^2 cdot 283 cdot 10369 cdot 1328077  cdot mbox{BIG} 
96  51680708854858323072    = 2^2 cdot 7 cdot 223 cdot 6111047  cdot mbox{BIG} 
97  83621143489848422977    = 3^2 cdot 59951  cdot mbox{BIG} 
98  135301852344706746049    = 3^4 cdot 3491 cdot 7027  cdot mbox{BIG} 
99  218922995834555169026    = 2^3 cdot 3 cdot 37 cdot 3527 cdot 402137  cdot mbox{BIG} 
100  354224848179261915075    = 367 cdot 1063 cdot 860113  cdot mbox{BIG} 
101  573147844013817084101    = 3 cdot 647 cdot 81703  cdot mbox{BIG} 
102  927372692193078999176    = 2^2 cdot 3^2 cdot 31 cdot 617 cdot 1201 cdot 5813323  cdot mbox{BIG} 
103  1500520536206896083277    = 3 cdot 47  cdot mbox{BIG} 
104  2427893228399975082453    = 7 cdot 19 cdot 37 cdot 1121453  cdot mbox{BIG} 
105  3928413764606871165730    = 2^3 cdot 3 cdot 47  cdot mbox{BIG} 
106  6356306993006846248183    = 3^3 cdot 83 cdot 197 cdot 691 cdot 1123 cdot 6131  cdot mbox{BIG} 
107  10284720757613717413913    = 3^3  cdot mbox{BIG} 
108  16641027750620563662096    = 2^2 cdot 31 cdot 59 cdot 1394177  cdot mbox{BIG} 
109  26925748508234281076009    = 3^3  cdot mbox{BIG} 
110  43566776258854844738105    = 3^3 cdot 2239  cdot mbox{BIG} 
111  70492524767089125814114    = 2^3 cdot 3 cdot 59753  cdot mbox{BIG} 
112  114059301025943970552219    = 7 cdot 19  cdot mbox{BIG} 
113  184551825793033096366333    = 3 cdot 781063 cdot 1419973  cdot mbox{BIG} 
114  298611126818977066918552    = 2^2 cdot 3^2 cdot 139 cdot 337 cdot 1307  cdot mbox{BIG} 
115  483162952612010163284885    = 3 cdot 137  cdot mbox{BIG} 
116  781774079430987230203437    = 139^2  cdot mbox{BIG} 
117  1264937032042997393488322    = 2^3 cdot 3  cdot mbox{BIG} 
118  2046711111473984623691759    = 3^4 cdot 349187  cdot mbox{BIG}

I adjusted the Fermat command to also show the resulting number; in this case every other Lucas number

6  8      Fermat:   ( 5 , 12 , 18 );   
8  21      Fermat:  ( 5 , 12 , 47 );    ( 20 , 24 , 94 );  
10  55      Fermat:   ( 5 , 12 , 123 );   ( 20 , 24 , 246 );  
12  144      Fermat:  ( 5 , 12 , 322 );   ( 20 , 24 , 644 );  
14  377      Fermat:  ( 5 , 12 , 843 );  ( 20 , 24 , 1686 ); 
16  987      Fermat:  ( 5 , 12 , 2207 );  ( 20 , 24 , 4414 ); 
18  2584      Fermat:  ( 5 , 12 , 5778 );  ( 20 , 24 , 11556 ); 
20  6765      Fermat:  ( 5 , 12 , 15127 );  ( 20 , 24 , 30254 ); 
22  17711      Fermat:  ( 5 , 12 , 39603 );  ( 20 , 24 , 79206 ); 
24  46368      Fermat:  ( 5 , 12 , 103682 );  ( 20 , 24 , 207364 ); 
26  121393      Fermat:  ( 5 , 12 , 271443 );  ( 20 , 24 , 542886 ); 
28  317811      Fermat:  ( 5 , 12 , 710647 );  ( 20 , 24 , 1421294 ); 
30  832040      Fermat:  ( 5 , 12 , 1860498 );  ( 20 , 24 , 3720996 ); 
32  2178309      Fermat:  ( 5 , 12 , 4870847 );  ( 20 , 24 , 9741694 ); 
34  5702887      Fermat:  ( 5 , 12 , 12752043 );  ( 20 , 24 , 25504086 ); 
36  14930352      Fermat:  ( 5 , 12 , 33385282 );  ( 20 , 24 , 66770564 ); 
38  39088169      Fermat:  ( 5 , 12 , 87403803 );  ( 20 , 24 , 174807606 ); 
40  102334155      Fermat:  ( 5 , 12 , 228826127 );  ( 20 , 24 , 457652254 ); 
42  267914296      Fermat:  ( 5 , 12 , 599074578 );  ( 20 , 24 , 1198149156 ); 
44  701408733      Fermat:  ( 5 , 12 , 1568397607 );  ( 20 , 24 , 3136795214 ); 
46  1836311903      Fermat:  ( 5 , 12 , 4106118243 );  ( 20 , 24 , 8212236486 ); 
48  4807526976      Fermat:  ( 5 , 12 , 10749957122 );  ( 20 , 24 , 21499914244 ); 
50  12586269025      Fermat:  ( 5 , 12 , 28143753123 );  ( 20 , 24 , 56287506246 ); 
52  32951280099      Fermat:  ( 5 , 12 , 73681302247 );  ( 20 , 24 , 147362604494 ); 
54  86267571272      Fermat:  ( 5 , 12 , 192900153618 );  ( 20 , 24 , 385800307236 ); 
56  225851433717      Fermat:  ( 5 , 12 , 505019158607 );  ( 20 , 24 , 1010038317214 ); 
58  591286729879      Fermat:  ( 5 , 12 , 1322157322203 );  ( 20 , 24 , 2644314644406 ); 
60  1548008755920      Fermat:  ( 5 , 12 , 3461452808002 );  ( 20 , 24 , 6922905616004 ); 
62  4052739537881      Fermat:  ( 5 , 12 , 9062201101803 );  ( 20 , 24 , 18124402203606 ); 
64  10610209857723      Fermat:  ( 5 , 12 , 23725150497407 );  ( 20 , 24 , 47450300994814 ); 
66  27777890035288      Fermat:  ( 5 , 12 , 62113250390418 );  ( 20 , 24 , 124226500780836 ); 
68  72723460248141      Fermat:  ( 5 , 12 , 162614600673847 );  ( 20 , 24 , 325229201347694 ); 
70  190392490709135      Fermat:  ( 5 , 12 , 425730551631123 );  ( 20 , 24 , 851461103262246 ); 
72  498454011879264      Fermat:  ( 5 , 12 , 1114577054219522 );  ( 20 , 24 , 2229154108439044 ); 
74  1304969544928657      Fermat:  ( 5 , 12 , 2918000611027443 );  ( 20 , 24 , 5836001222054886 ); 
76  3416454622906707      Fermat:  ( 5 , 12 , 7639424778862807 );  ( 20 , 24 , 15278849557725614 ); 
78  8944394323791464      Fermat:  ( 5 , 12 , 20000273725560978 );  ( 20 , 24 , 40000547451121956 ); 
80  23416728348467685      Fermat:  ( 5 , 12 , 52361396397820127 );  ( 20 , 24 , 104722792795640254 ); 
$\endgroup$
  • 1
    $\begingroup$ It took me a while to see what is going on, but yes, $(5,12)$ for the even indices follows from the equation $5(F_{2n}^2-28)=L_{2n}^2-12^2$. $(20,24)$ is just a scaled version of $(5,12)$, as would be $(45,36)$. (+1) $\endgroup$ – robjohn Jan 4 '15 at 18:06
  • $\begingroup$ @robjohn, got some help with one command from stackoverflow, now the Fermat command also prints the result, here every other Lucas number. Currently last block of output in the answer. $\endgroup$ – Will Jagy Jan 4 '15 at 22:21
3
$\begingroup$

Edit:

I'll keep my original at the bottom since it has some value under this question.

Without considering $n:F_n^2-28\lt 0$ (for example, $n=4,F_4^2-28=9-28=-19$ or similarly for $n=5$), the first couple values certainly are composite, but not in an immediately-obvious manner.

Here is an answer looking at the Fermat numbers, which are not under discussion for this question but are mildly interesting in this light anyway:

Disregarding $F_0=2^{2^0}+1$, we have $3\nmid 2^{2^n}+1$ for all positive integers $n$, making $F_n^2\equiv 1\pmod 3$, and as $28\equiv 1\pmod 3$ we have $F_n^2-28\equiv 0\pmod 3$ for all $n\gt 0$.

$\endgroup$
  • $\begingroup$ You can keep the answer as far as I am concerned. $\endgroup$ – VividD Jan 4 '15 at 2:31

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.