 mersenneforum.org Semi-prime factorization conjecture
 Register FAQ Search Today's Posts Mark Forums Read 2018-01-30, 13:43 #1 Alberico Lepore   May 2017 ITALY 40310 Posts Semi-prime factorization conjecture Let N be a semiprimo then N=a^2-b^2 will have two solutions a1=(N+1)/2 and b1=(N-1)/2 a2=? b2=? bruteforce on b2 starting from 0 A+B=a1 , A-B=a2 , C+D=b1 ,C-D=1 gcd(A,C)=p_a gcd(B,D)=p_b p=(p_a^2-p_b^2) gcd(A,D)=q_a gcd(B,C)=q_b q=(q_b^2-q_a^2) Example 15=a^2-b^2 a=4 b=1 a=8 b=7 A+B=8 , A-B=4 , C+D=7 , C-D=1 A=6 ,B=2 ,C=4 ,D=3 gcd(A,C)=2 gcd(B,D)=1 p=(2^2-1^2)=3 gcd(A,D)=3 gcd(B,C)=2 q=(3^2-2^2)=5 What do you think about it?   2018-01-30, 13:59   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts Quote:
 Originally Posted by Alberico Lepore What do you think about it?
And a3=-4 and b3=1
a4=-8 and b4=7
...   2018-01-30, 14:03   #3
Alberico Lepore

May 2017
ITALY

13×31 Posts Quote:
 Originally Posted by science_man_88 And a3=-4 and b3=1 a4=-8 and b4=7 ...
They are opposites   2018-01-30, 14:53   #4
Alberico Lepore

May 2017
ITALY

13×31 Posts Quote:
 Originally Posted by Alberico Lepore A+B=a1 , A-B=a2 , C+D=b1 ,C-D=1
A+B=a1 , A-B=a2 , C+D=b1 ,C-D=b2   2018-02-03, 01:30   #5
BudgieJane

"Jane Sullivan"
Jan 2011
Beckenham, UK

23×29 Posts Quote:
 Originally Posted by Alberico Lepore Let N be a semiprimo then What do you think about it?
Do you have an example where N has more than 2 digits. Something like 102 digits would be nice.   2018-02-03, 02:07   #6
carpetpool

"Sam"
Nov 2016

13·23 Posts Quote:
 Originally Posted by Alberico Lepore Let N be a semiprimo then N=a^2-b^2 will have two solutions a1=(N+1)/2 and b1=(N-1)/2 a2=? b2=? bruteforce on b2 starting from 0 A+B=a1 , A-B=a2 , C+D=b1 ,C-D=1 gcd(A,C)=p_a gcd(B,D)=p_b p=(p_a^2-p_b^2) gcd(A,D)=q_a gcd(B,C)=q_b q=(q_b^2-q_a^2) Example 15=a^2-b^2 a=4 b=1 a=8 b=7 A+B=8 , A-B=4 , C+D=7 , C-D=1 A=6 ,B=2 ,C=4 ,D=3 gcd(A,C)=2 gcd(B,D)=1 p=(2^2-1^2)=3 gcd(A,D)=3 gcd(B,C)=2 q=(3^2-2^2)=5 What do you think about it?
If n is a prime, then the solutions to a^2 = 1 (mod n) are a = +-1 (mod n). If n = p*q where p and q are primes, then the solutions to a^2 = 1 (mod n) are a = +-1, b, and c (mod n) where

b = 1 (mod p) and -1 (mod q)

c = -1 (mod p) and 1 (mod q)

Your "conjecture" follows from this fact.

Last fiddled with by carpetpool on 2018-02-03 at 02:08   2018-02-03, 02:41   #7
carpetpool

"Sam"
Nov 2016

1001010112 Posts Quote:
 Originally Posted by Alberico Lepore Let N be a semiprimo then N=a^2-b^2 will have two solutions a1=(N+1)/2 and b1=(N-1)/2 a2=? b2=? bruteforce on b2 starting from 0 A+B=a1 , A-B=a2 , C+D=b1 ,C-D=1 gcd(A,C)=p_a gcd(B,D)=p_b p=(p_a^2-p_b^2) gcd(A,D)=q_a gcd(B,C)=q_b q=(q_b^2-q_a^2) Example 15=a^2-b^2 a=4 b=1 a=8 b=7 A+B=8 , A-B=4 , C+D=7 , C-D=1 A=6 ,B=2 ,C=4 ,D=3 gcd(A,C)=2 gcd(B,D)=1 p=(2^2-1^2)=3 gcd(A,D)=3 gcd(B,C)=2 q=(3^2-2^2)=5 What do you think about it?
Let's turn this into a game (just for fun).

Here we have semiprimes N = p*q ranging from 90-100 digits. Show that for each one, p = q = 1 (mod n) for a specific n. That is, show each prime dividing N has the form k*n+1.

For example,

N = 5539113502033412895292115974558480983800647735117931750794894952942621260596968647983584706901 (n = 90)

is a semiprime. Show each prime dividing N has the form 90*k+1, or equivalently p = q = 1 (mod 90) where pq = N.

Here are a few more examples (try and show that each prime dividing N has the form k*n+1):

N = 448089051076275785687389418381162972987229036034444427278869256690561568953546204700396224357, (n = 36)

N = 12875011596982825641079225756329235926774793871954944034524736059975902131902515285746205781, (n = 42)

N = 325660878359113486502421634634373166016783555791941517818588883372438081215159258342011023201, (n = 100)

N = 2529326286788100617652188740443724847554819001546212172410115864297421395751726116717093396417, (n = 98)   2018-02-16, 08:27 #8 CRGreathouse   Aug 2006 133478 Posts Nice game! Could you show us how it works?  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 48 2017-12-30 09:43 Alberico Lepore Alberico Lepore 61 2017-09-23 21:52 carpetpool Miscellaneous Math 27 2017-01-19 21:00 miket Miscellaneous Math 6 2013-05-22 05:26 GP2 Marin's Mersenne-aries 2 2003-09-29 19:01

All times are UTC. The time now is 12:08.

Sat Aug 8 12:08:56 UTC 2020 up 22 days, 7:55, 1 user, load averages: 1.25, 1.70, 1.79