Found an online .pdf with the formula on the first page (for those interested): [url]http://matwbn.icm.edu.pl/ksiazki/aa/aa39/aa3936.pdf[/url]

[QUOTE=Zeta-Flux;87707]is it computationally easy to find a,b such that q=a^2+b^2?
[/QUOTE]
Yes, it is. See for example in my personal Web site: [url]http://www.alpertron.com.ar/4SQUARES.HTM[/url] . I also have an applet where you can decompose numbers of several hundred digits in sum of squares in a few seconds: [url]http://www.alpertron.com.ar/FSQUARES.HTM[/url]

alperton,

Do you think that implementing the rational quartic formula into a siever would be worthwhile?

[QUOTE=ET_;87449]I read something about it on the thread pointed by William, but still need some help... [/QUOTE]

I have found out how to calculate the form of the primes P which have A as a quadratic residue. A C program is attached, compile it with `gcc -o qr qr.c' and run it as `./qr A' where A is the value you are interested in.

For example, [CODE]./qr 2[/CODE] prints [CODE]2 QR wrt p => p=1,7 (mod 8)[/CODE] which is the Mersenne case.

Use the information in the same way for other bases. e.g. after constructing `mod' and `map' as in the program for a specific value A:

[CODE]for (p = first_prime(); p < max_prime; p = next_prime(p))
if (map[p%mod])
/* p might divide A^n-1*/[/CODE]

[QUOTE=geoff;87751][CODE]for (p = first_prime(); p < max_prime; p = next_prime(p))
if (map[p%mod])
/* p might divide A^n-1*/[/CODE][/QUOTE]

Correction: The second line should be[CODE]if (map[p%mod] == 1)[/CODE]

[QUOTE=geoff;87751]I have found out how to calculate the form of the primes P which have A as a quadratic residue. A C program is attached, compile it with `gcc -o qr qr.c' and run it as `./qr A' where A is the value you are interested in.

For example, [CODE]./qr 2[/CODE] prints [CODE]2 QR wrt p => p=1,7 (mod 8)[/CODE] which is the Mersenne case.

Use the information in the same way for other bases. e.g. after constructing `mod' and `map' as in the program for a specific value A:

[CODE]for (p = first_prime(); p < max_prime; p = next_prime(p))
if (map[p%mod])
/* p might divide A^n-1*/[/CODE][/QUOTE]


Thank you very much Geoff :lol:

Luigi

Alperton,

I was playing with the equations, and think I understand them a little better now. Suppose we have p|(5^(odd) - 1), and p==1 mod 4. Then 5 is a quartic residue modulo p. By quadratic reciprocity (5/p)=(p/5)=1. Thus p== +- 1 mod 5. Write 5=a^2+b^2=2^2+1^2, and write p=c^2+d^2 (where c is even).

For simplicity we will consider the case p==1 mod 5. In this case p is a quartic residue modulo 5. The rational biquadratic reciprocity formula, (p/5)_4 (5/p)_4 = (-1)^(5-1)/4 (ad-bc / 5), reduces in this case to 1=(-1)(2d-c / 5). At this point, one can use your algorithm to find c and d, then find whether 2d-c is a quadratic residue modulo 5. If not, then 1=(-1)(-1) checks out. However, if 2d-c is a quadratic residue modulo 5, then 1=(-1)1 gives a contradiction.

One can look even further in this case. Since p==1 mod 5, we see that c^2+d^2==1 mod 5, and so the only choices for c^2, d^2 modulo 5 are 1,0 or 0,1 (respectively). Thus, if the odd component of p=c^2+d^2 is congruent to 0 mod 5, we have that 2d-c== -c == +-1 mod 5 which are both quadratic residues, and we get a contradiction in this case!

Thus, if p=c^2+d^2 with c==0 mod 10, then p cannot divide 5^(odd)-1. :D

In the case p==-1 mod 5, the opposite turns out to be true.

Best,
Zeta-Flux