45
$\begingroup$

The problem is as follows:

Prove or disprove that if ${F_{n}}$ is $n$-th Fibonacci number, and $n>5$, then $${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$
14
  • $\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, 2015 at 2:12
  • 1
    $\begingroup$ What about $3^2-28=-19$ and $5^2-28=-3$? $\endgroup$ Jan 4, 2015 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$ Jan 4, 2015 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$ Jan 4, 2015 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$ Jan 4, 2015 at 3:12

5 Answers 5

45
$\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$
5
  • 1
    $\begingroup$ $F_{1944}^2-13$ is prime. $\endgroup$
    – P.-S. Park
    Jan 30, 2015 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, 2015 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$ Aug 5, 2015 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$ Aug 5, 2015 at 4:38
  • $\begingroup$ @TitoPiezasIII, thanks, good point, I slightly changed the text to warn the potential reader. $\endgroup$
    – VividD
    Aug 24, 2015 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$
11
  • 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, 2015 at 2:42
  • $\begingroup$ This case n=92 is really intimidating..., but so is n=20... $\endgroup$
    – VividD
    Jan 4, 2015 at 2:54
  • $\begingroup$ Except for $n=68,76$, there doesn't appear to be a repeated factor... $\endgroup$
    – abiessu
    Jan 4, 2015 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, 2015 at 3:02
  • $\begingroup$ Hey, 197 * 85584807236027447 / 3372041405099481407 is very close to 5. $\endgroup$
    – VividD
    Jan 4, 2015 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$
4
  • $\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, 2015 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, 2015 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, 2015 at 18:30
  • $\begingroup$ @VividD: Indeed. That works. $\endgroup$
    – robjohn
    Jan 4, 2015 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$
2
  • 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, 2015 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, 2015 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$
1
  • $\begingroup$ You can keep the answer as far as I am concerned. $\endgroup$
    – VividD
    Jan 4, 2015 at 2:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .