### 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 .
```

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