## Re: Fwd: Euler's 3n+1 theory

Expand Messages
• ... I assume you mean when 3n+1 is prime. 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
Message 1 of 2 , Jun 29, 2004
• 0 Attachment
wrote:
> Hello ,
> how to compute x and y
>
> x^2 + 3y^2 = 3n + 1
>
> where n is prime > 3

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

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
Your message has been successfully submitted and would be delivered to recipients shortly.