wrote:> Hello ,

I assume you mean when 3n+1 is prime.

> how to compute x and y

>

> x^2 + 3y^2 = 3n + 1

>

> where n is prime > 3

First we find an a^2+3*b^2 that is some multiple of p, say kp

Then we use three methods to find a c^2+3*d^2 that is a smaller

multiple of p,

Repeat until the "multiple" is 1.

The first trick is to divide any common factors of a and b.

The second trick is for a and b both odd, use

(a^2+3b^2)/4 = ((a+3b)/4)^2+3((a-b)/4)^2=((a-3b)/4)^2+3((a+b)/4)^2,

whichever one gives integers.

The third trick is to use modular arithemetic to find a smaller

multiple of k that is x^2+3*y^2. The use

(a^2+3*b^2)*(x^2+3*y^2)=(ax+3by)^2+3(ay-bx)^2=(ax-3by)^2+3(ay+bx)^2

whichever one makes both terms divisible by k.

Here's a nontrivial example for p=30000001

We know that p divides a^(p-1)-1

p-1=3n, so this is a^(3n)-1 = (a^n-1)*(a^2n+a^n+1)

consider a=2. 2^n mod p = 13428344

p does not divide (2^n-1), so p does divide (2^2n+2^n+1)

(2^2n+2^n+1) = (2^(n-1)+1)^2 + 3*(2^(n-1)^2)

(2^9999999+1)^2 + 3 * (2^9999999)^2 is divisible by p

2^9999999 mod p = 6714172

taking the expression mod p, we know that

6714173^2 + 3*6714172^2 is divisible by p

6714173^2 + 3*6714172^2 = 6010681p

6714172 mod 6010681 = 703491

so 703492^2+3*703491^2 is divisible by 6010681

(703492^2+3*703491^2)*( 6714173^2 + 3*6714172^2) is divisible by

p*6010681^2

Using (a^2+3*b^2)*(x^2+3*y^2)=(ax+3by)^2+3(ay-bx)^2, this is

18893445715472^2 + 3*6010681^2

dividing by 6010681^2,

3143312^2+3*1^2 is divisble by p

3143312^2+3*1^2 = 329349p

3143312 mod 329349 = 179189

179189^2+3*1^2 is divisible by 329349

(179189^2+3*1^2)*( 3143312^2+3*1^2) is divisible by p*329349^2

Using (a^2+3*b^2)*(x^2+3*y^2)=(ax+3by)^2+3(ay-bx)^2, this is

563246933971^2+3*2964123^2

dividing by 329349^2

1710193^2+3*9^2 is divisible by p

1710193^2+3*9^2 are both odd

Using (a^2+3b^2)/4 = ((a+3b)/4)^2+3((a-b)/4)^2

427555^2+3*427546^2 is divisible by p

427555^2+3*427546^2 = 24373p

427555 mod 24373 = -11159

427546 mod 24373 = -11168

11159^2+3*11168^2 is divisible by 24373

(11159^2+3*11168^2)*(427555^2+3*427546^2) is divisible by p*24373^2

Using (a^2+3*b^2)*(x^2+3*y^2)=(ax+3by)^2+3(ay-bx)^2, this is

19095587429^2+3*3948426^2

dividing by 24373^2

783473^2+3*162^2 is divisible by p

783473^2+3*162^2 = 20461p

783473 mod 20461 = 5955

5955^2+3*162^2 is divisible by 20461

(5955^2+3*162^2)*(783473^2+3*162^2) is divisible by p*20461^2

Using (a^2+3*b^2)*(x^2+3*y^2)=(ax+3by)^2+3(ay-bx)^2, this is

4665660447^2+3*125957916^2

dividing by 20461^2

228027^2+3*6156^2 is divisible by p

3 divides 228027 and 6156

76009^2+3*2052^2 is divisible by p

76009^2+3*2052^2 = 193p

76009 mod 193 = -33

2052 mod 193 = -71

33^2+3*71^2 is divisible by 193

(33^2+3*71^2)*(76009^2+3*2052^2) is divisible by p*193^2

Using (a^2+3*b^2)*(x^2+3*y^2)=(ax+3by)^2+3(ay-bx)^2, this is

2945373^2+3* 5328923^2

dividing by 193^2

15261^2+3*27611^2 is divisible by p

15261 and 27611 are both odd

Using (a^2+3b^2)/4 = ((a-3b)/4)^2+3((a+b)/4)^2

16893^2+3*10718^2 is divisible by p

16893^2+3*10718^2 = 21*p

16893 mod 21 = 9

10718 mod 21 = 8

9^2+3*8^2 is divisible by 21

(9^2+3*8^2)*(16893^2+3*10718^2) is divisible by p*21^2

Using (a^2+3*b^2)*(x^2+3*y^2)=(ax+3by)^2+3(ay-bx)^2, this is

409269^2+3*38682^2

dividing by 21^2

19489^2+3*1842^2 is divisible by p

19489^2+3*1842^2 = 13p

19489 mod 13 = 2

1842 mod 13 = -4

2^2+3*4^2 is divisible by 13

2 and 4 are even, so

1^2+3*2^2 is divisible by 13

(1^2+3*2^2)*(19489^2+3*1842^2) is divisible by p*13^2

Using (a^2+3*b^2)*(x^2+3*y^2)=(ax-3by)^2+3(ay+bx)^2, this is

8437^2+3*40820^2

dividing by 13^2

649^2+3*3140^2 is divisible by p

649^2+3*3140^2 = p

======================

ElevenSmooth http://ElevenSmooth.com

Distributed factoring of 2^3326400-1