Huge factors of enormous integers

I claim the factorizations below are presently the "beta" factorizations to John Cosgrave's "alpha" factorizations .

For a quick scan by someone with knowledge of a little number theory , perhaps the most interesting parts below are the paragraph which begins with the word "Geometrically" and the section titled "On huge factors of enormous integers" .

On remainders .

Dividing a larger integer , called the dividend , by a smaller integer ,
called the divisor , yields a quotient and a remainder .
By convention , the remainder is guaranteed to be an integer between 0
and 1 less than the divisor .
( Otherwise , a lazy wiseacre would dare to tell you that 41 divided by
7 is 0 with a remainder of 41 .
)
E.g. , 41 / 7 = 5 , with remainder 6 .
On average , the remainder is about 1/2 the divisor .
E.g. , if the divisor is 3000000 and the dividend ranges through all
3000000 integers from 3000000000 and 3002999999 , the 3000000 remainders
will be each of the integers from 0 to 2999999 , once each , and the
average remainder will be 1499999.5 .


On primes and factorization .

Geometrically , the definition of prime integer is familiar
to some 5- and 6-year-old children who have played with
coins , marbles or toy soldiers , and arranged them
in ranks , or equivalently , in rows and columns .
For a prime number of objects ,
rectangularization forces linearization .
This is the definition of prime ,
the most accessible definition of prime .

Algebraically , a prime integer is  > 1  and
has no divisor  > 1 , except itself .

The Fundamental Theorem of Arithmetic is the
foundation of factorization .
It asserts that only one breakage of a number
into prime factors exists .
E.g. , 12 has prime factors 2 , 2 and 3 .
Every other set of factors of 12 eventually splits into these , in
some order ( together with as many 1's as desired ) .
( People who know a little abstract algebra will recognize that here ,
number and integer really mean natural or positive integer and that
units are disregarded .
)


On huge factors of enormous integers .

Define  np ( n1 )  =  n1^n1 + (n1+1)^(n1+1) .

For  n1 = 1 , 2 and 3 ,  the first three values are  5 , 31 and 283 .
These are the only known primes of this form .

Let  a  =  70 .
Let  p  =  np ( a )  /  ( 3 * 229 * 1657^2 * 55793 * 54844140931 ) .
Let  b  =  p * (p-1) + a .  p  has 107 digits and  b  has 214 digits .
Let  c  =  np ( b ) .
Now , p  is a prime factor of  c .
c  is far greater than  googolplex^googol  and , using a small radix ,
cannot be represented within the known universe .

Let  a  =  802 .
Let  p  =  np ( a )  /  ( 3 * 7^4 * 13^2 * 29 * 337^2 ) .
Let  b  =  p * (p-1) + a .  p  has 2320 digits and  b  has 4640 digits .
Let  c  =  np ( b ) .
Now , p  is a prime factor of  c .

Let  a  =  3376 .
Let  p  =
 np ( a )  /  ( 3 * 7^2 * 13^2 * 19 * 3361 * 41761^2 * 3884884187 ) .
p  is an 11888-digit strongly-probable prime .
                 p*(p-1) + a  has 23776 digits .
            np ( p*(p-1) + a )  has more .
p  divides  np ( p*(p-1) + a ) .
np ( p*(p-1) + a )  =  3 * 107 * 14503^2 * 330943^2 * p * c?BIG ,
where c?BIG is a large , presumably composite , integer .


Let  a  =  4576 .
Let  p  =  np ( a )  /  ( 3 * 557 * 1609^2 * 4339^2 * 61483 ) .
p  is an 16733-digit strongly-probable prime .
                 p*(p-1) + a  has 33466 digits .
            np ( p*(p-1) + a )  has more .
p  divides  np ( p*(p-1) + a ) .
np ( p*(p-1) + a )  =
 3 * 7^2 * 193 * 79^2 * 17077 * 43481 * 43577 * 71711 * p * c?BIG

Let  a  =  4576 .
Let  p  =  np ( a )  /  ( 3 * 557 * 1609^2 * 4339^2 * 61483 ) .
p  is an 16733-digit strongly-probable prime .
Let  b  =  p * (p-1) + a .  b  has 33466 digits .
Let  c  =  np ( b ) .       c  has more .
p  divides  c .
c  =  3 * 7^2 * 79^2 * 193 * 17077 * 43481 * 43577 * 71711 * p * c?BIG

3 , 7 , 79 , 193 , 17077 , 43481 , 43577 , and 71711  are all prime
factors of  c .


On remainders , again .

Asserting that  p  divides  c  is a rather strong statement , in a
statistical sense .
If  c  were a random enormous integer , dividing it by a 16733-digit
integer would probably give a 16733- or 16732-digit remainder .
One of the multitude of "2-sigma authorities" on statistics would tell
you that it is impossible to find a remainder of less than about 16731
digits .
No one would be expected to live long enough to achieve a remainder less
than 16000 digits .
Yet  c  divided by  p  yields a remainder which is not only less than
10000 digits , less than 1000 digits , less than 10 digits , but
actually 0 .

Appreciation and links .

It would be ungrateful of me not to mention my debt to powermod = modexpo = exponentiation under a modulus .
And GMP, GMP-ECM, NTL, Primo, and UBASIC .
In Cosgrave's article look for the phrases "developments in later years" and "light years" .
Some of the larger strongly-probable primes are accessible under the name "Walter Nissen" under Probable Primes .

---- ----

Appendix - The largest known such factorizations (4576^4576+4577^4577)/(3*557*1609^2*4339^2*61483),16733 custom code : trial division to 10^8 PrimeForm v. 0.4 Upd.4 : PRP bases 151 , 157 , 163 , 167 custom code : strongly-probable prime to prime bases 61531061 , 61562411 , 61626029 , 61633909 , 61671833 and 22 others Define np ( n1 ) = n1^n1 + (n1+1)^(n1+1) . Let a = 4576 . Let p = np ( a ) / ( 3 * 557 * 1609^2 * 4339^2 * 61483 ) . p is a 16733-digit strongly-probable prime . p*(p-1) + a has 33466 digits . np ( p*(p-1) + a ) has more . p divides np ( p*(p-1) + a ) . (4223^4223+4224^4224)/(233*185531746148849),15299 custom code : trial division to 10^8 GMP 4.2-ECM 6.1 : PRP PrimeForm v. 0.4 Upd.4 : PRP bases 11 , 13 , 233 , 241 , 251 custom code : strongly-probable prime to prime bases 61962811 , 61963619 , 61977551 , 61979837 and 5 others Define np ( n1 ) = n1^n1 + (n1+1)^(n1+1) . Let a = 4223 . Let p = np ( a ) / ( 233 * 185531746148849 ) . p is an 15299-digit strongly-probable prime . p*(p-1) + a has 30597 digits . np ( p*(p-1) + a ) has more . p divides np ( p*(p-1) + a ) . (3758^3758+3759^3759)/(9067*3706499*250191823789),13417 custom code : trial division to 10^8 GMP 4.2-ECM 6.1 : PRP PrimeForm v. 0.4 Upd.4 : PRP bases 17 , 37 , 47 , 67 custom code : strongly-probable prime to prime bases 61433509 , 61439617 , 61444441 , 61479461 and 3 others Define np ( n1 ) = n1^n1 + (n1+1)^(n1+1) . Let a = 3758 . Let p = np ( a ) / ( 9067 * 3706499 * 250191823789 ) . p is an 13417-digit strongly-probable prime . p*(p-1) + a has 26834 digits . np ( p*(p-1) + a ) has more . p divides np ( p*(p-1) + a ) . (3376^3376+3377^3377)/(3*7^2*13^2*19*3361*41761^2*3884884187),11888 custom code : trial division to 10^8 GMP 4.2-ECM 6.1 : PRP PrimeForm v. 0.4 Upd.4 : PRP bases 179 , 191 , 199 , 227 custom code : strongly-probable prime to prime bases 62063993 , 62064571 , 62065303 , 62071133 and 1 other Define np ( n1 ) = n1^n1 + (n1+1)^(n1+1) . Let a = 3376 . Let p = np ( a ) / ( 3*7^2*13^2*19*3361*41761^2*3884884187 ) . p is an 11888-digit strongly-probable prime . p*(p-1) + a has 23776 digits . np ( p*(p-1) + a ) has more . p divides np ( p*(p-1) + a ) . np ( p*(p-1) + a ) = 3 * 107 * 14503^2 * 330943^2 * p?11888 * c?BIG (3294^3294+3295^3295)/12740953,11585 custom code : trial division to 10^8 PrimeForm v. 0.4 Upd.4 : PRP bases 53 , 73 , 79 , 83 , 113 custom code : strongly-probable prime to prime bases 62076851 , 62081443 , 62081777 , 62083391 and 1 other Define np ( n1 ) = n1^n1 + (n1+1)^(n1+1) . Let a = 3294 . Let p = np ( a ) / 12740953 . p is a 11585-digit strongly-probable prime which divides np ( p*(p-1) + a ) . p*(p-1) + a has 23169 digits . (3140^3140+3141^3141)/(1571*323819),10976 custom code : trial division to 10^8 PrimeForm v. 0.4 Upd.4 : PRP bases 71 , 113 custom code : strongly-probable prime to prime bases 62084777 , 62085403 , 62085899 , 62086229 Define np ( n1 ) = n1^n1 + (n1+1)^(n1+1) . Let a = 3140 . Let p = np ( a ) / ( 1571 * 323819 ) . p is a 10976-digit probable prime which divides np ( p*(p-1) + a ) . p*(p-1) + a has 21952 digits .

-

2000 Mathematics Subject Classification : Primary 11A51 ; Secondary 11A05 , 11A41 , 11A51 , 11N05 , 11N25 , 11Y05 , 11Y11 , 11Y55 .

Walter Nissen
originally posted 2008-01-30
updated 2008-06-16