Closed form solution of x^2 = 2 mod Fermat number

[mpenguin]

Sorry if this is known, but didn't find it on the net.
The solution of x^2 = I in C leads to solution to x^2 = 2 mod (2^(2^n)+1).
It is also possible to compute sqrt(2+sqrt(2)) mod (2^(2^n)+1) and
similar roots rising from solutions in C.

Any use of this?

--Code--
n0:=8;
n:=2^(2^n0)+1;
ii:=powermod(2,2^(n0-1),n);
ii2:=powermod(2,2^(n0-2),n);
ii3:=powermod(2,2^(n0-3),n);
sq2:=mods(ii2*2/(1+ii),n); /* sq2^2 mod n == 2*/
sq2a:=mods(ii3*2/((ii*sq2+1-ii)),n); /* sqrt(2+sqrt(2)) mod n*/
print("ii",ii,mods(ii^2,n),ii2,mods(ii2^2,n),"sqrt(2)=",sq2,
"sqrt(2)^2=",mods(sq2^2,n),"sqrt(2+sqrt(2))=",sq2a,"^2=",mods(sq2a^2,n));
quit;
--------

[alpertron]

I translated the sqrt(2) program to UBASIC

 10   input N0
 20   N=2^(2^N0)+1
 30   Ii=modpow(2,2^(N0-1),N)
 40   Ii2=modpow(2,2^(N0-2),N)
 50   Sq2=(Ii2*2*modinv((1+Ii),N))@N
 60   print Sq2,Sq2^2@N

This is interesting, but it would be far more interesting to find another sqrt(2) that is not the negative of this one (mod F_n). This would allow to factor F_n and you will appear in math books :-) .

[alpertron]

Unfortunately with the following code:

10   input N0
20   N=2^(2^N0)+1
30   Ii=modpow(2,2^(N0-1),N)
40   Ii2=modpow(2,2^(N0-2),N)
50   Ii3=modpow(2,2^(N0-3),N)
60   Sq2=(Ii2*2*modinv((1+Ii),N))@N
70   Sq2a=(Ii3*2*modinv((Ii*Sq2+1-Ii),N)@N)
80   print Sq2,Sq2^2@N
90   print ((Sq2a*Sq2a)-2)@N

I found that the values of sqrt(2) generated by calculating directly the sqrt(2) and calculating B=sqrt(2+sqrt(2)) and then B^2-2 = sqrt(2) are the same, so they cannot be used to factor F_n.

[mpenguin]

I am theory lamer, but according to wikipedia:

>Let n ≥ 3 be a positive odd integer. Then n is a Fermat prime if and only if for every a >coprime to n, a is a primitive root mod n if and only if a is a quadratic nonresidue mod >n.

Looks like sqrt(2) is not primitive root, so showing that it is nonresidue shows compositeness of Fn ?

The original program computes sq2a^2 = 2+sqrt(2)=sqrt(2)*(1+sqrt(2)) (at least in C)
so showing that any of sqrt(2),1+sqrt(2),1-sqrt(2) is nonresidue shows compositeness of Fn?

The above reasoning may be quite buggy :)

[mpenguin]

When one takes the smaller absolute value of sq2 and sq2a ("signed mod") they have strange factorizations F[n] | sq2[n+i] and F[n] | sq2a[n+j].

[alpertron]

Using n=5, F₅ = 4294967297.

With your method you find sqrt(2) = 4278190337.

If you somehow find sqrt(2) = 1370209359, you will be able to factor F₅ since gcd(F₅, 4278190337 - 1370209359) = 6700417 which is a proper factor of the original number.

[mpenguin]

sqrt(2) follows from:
fn(n) = fn(n-1)^2-2*(fn(n-2)-1)^2

fn(n) is the nth Fermat number

[alpertron]

The code for sqrt(2) in UBASIC using your last post is:

10   input N0
20   N=2^(2^N0)+1
30   Ii=2^(2^(N0-1))
40   Ii2=2^(2^(N0-2))
50   Sq2=(Ii2*2*modinv((1+Ii),N))@N
60   print Sq2,Sq2^2@N
70   print (Ii+1)*modinv(Ii2,N)@N

Obviously both values of sqrt(2) are the same, since if the number computed in line 70 is B, the line 50 computes 2/B (mod N).

[mpenguin]

sqrt(2+sqrt(2+sqrt(2+sqrt(2+....sqrt(2))) are computable from Z and iterating x -> x^2 -2 may reach zero in n+1 steps.

mupad code:

fn:=proc(n) begin 2^(2^n)+1;end_proc;
n0:=7;
n:=fn(n0);
sq2:=mods(fn(n0-1)/(fn(n0-2)-1),n);
mods(sq2^2,n);
vk:=(fn(n0-2)/(2^(2^(n0-3))));
print(" ^2 -sq2[-1] ",1,mods(vk,n),mods(vk^2,n)-sq2);
for i from 2 to n0-2 do
	vt:=sqrt(vk+2);
	print(" ^2 -sq2[-1] ",i,vt,mods(vt,n),mods(vk,n),mods(vt^2,n),
	"== 2, ",mods(vt^2-vk,n));
	vk:=vt;
end_for;
s1:=mods(3*sq2/2,n);
print(" + ",i,mods(s1,n),mods(vk,n),mods(s1^2-vk,n));

for i from 1 to n0+1 do
	print(" x -> x^2-2 ",i,gcd(s1,n),s1);
	s1:=mods(s1^2-2,n);
end_for;
quit;

[Yamato]

Let F(n) = 2^(2^n) + 1.

Then the "trivial" square root of 2 is

sqrt(2) = F(n-1) * inv(F(n-2) - 1) (mod F(n))
(inv is the inverse number mod F(n))

because of the real factorization

F(n) = F(n-1)^2 - x^2

where x = (F(n-2) - 1)*sqrt(2)

[mpenguin]

Originally Posted by Yamato

Let F(n) = 2^(2^n) + 1.

Then the "trivial" square root of 2 is

Yes, the square root of 2 is trivial mod Fn.

(2+2^(1/2))^2 and (2+(2+2^(1/2))^(1/2))^(1/2) mod Fn are a little more subtle.