mersenneforum.org Semi-prime factorization conjecture
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-01-30, 13:43 #1 Alberico Lepore     May 2017 ITALY 2·241 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

2·241 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

2×241 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

2×53 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

14616 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

2×163 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 32·5·7·19 Posts Nice game! Could you show us how it works?

 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 03:56.

Thu May 6 03:56:54 UTC 2021 up 27 days, 22:37, 0 users, load averages: 2.91, 3.02, 3.02