A392773 - OEIS

%I #45 Feb 02 2026 17:24:52

%S 6,60,4080,16776960,281474976645120,79228162514264337589248983040,

%T 6277101735386680763835789423207666416083908700390324961280

%N The smallest x for which x^2 == 2 (mod F(n)), where F(n) is the n-th Fermat number.

%C Useful for factoring algorithms that contain a Gaussian elimination stage (e.g., MPQS, NFS).

%C There are no values of x for either F(0)=3 or F(1)=5 as they are too small to have defined values for F(n-2), therefore the first value in the sequence applies to F(2)= 17.

%C Due to quadratic reciprocity, there is always a second reflection value at (F(n) - x). E.g. a(3) = 60, therefore reflection value = (F(3) - a(3)) = (257 - 60) = 197  cf.  197^2 == 2 (mod 257).

%D Henri Cohen, A course in Computational Algebraic Number Theory, Springer-Verlag, 1993, pp. 487-492.

%D David Wells, Prime Numbers (The most mysterious figures in math), John Wiley, 2005, p. 95.

%H Paolo Xausa, <a href="/A392773/b392773.txt">Table of n, a(n) for n = 2..12</a>

%F a(n) = (F(n-2) - 1)*(F(n-1) - 2) with F(n) = 2^(2^n) + 1.

%e a(2) = (F(0) - 1)*(F(1) - 2) = 2*3 = 6        cf.  6^2 == 2 (mod 17)

%e a(3) = (F(1) - 1)*(F(2) - 2) = 4*15 = 60      cf.  60^2 == 2 (mod 257)

%e a(4) = (F(2) - 1)*(F(3) - 2) = 16*255 = 4080  cf.  4080^2 == 2 (mod 65537)

%t A392773[n_] := 8^# - 2^# & [2^(n-2)]; Array[A392773, 8, 2] (* _Paolo Xausa_, Feb 02 2026 *)

%o (Rexx)

%o Trace Off

%o Numeric Digits 1024

%o out_str = ""

%o Do inc = 0 To 8

%o    fermat.inc = (2 ** (2 ** inc)) + 1

%o    If inc > 1 Then Do

%o       temp1 = inc - 1 ; temp2 = inc - 2

%o       out_str = out_str||", "||(fermat.temp2 - 1) * (fermat.temp1 - 2)

%o    End

%o End

%o Say Substr(out_str,3)

%o Exit

%o (Python)

%o def A392773(n): return (m:=(1<<(1<<n-2)))*(m**2-1) # _Chai Wah Wu_, Feb 01 2026

%Y Cf. A000215 (F(n)).

%K nonn,easy

%O 2,1

%A _Martin Hutchings_, Jan 22 2026