8
$\begingroup$

What is the smallest prime factor of the number

$$N\ :=\ 14^{14^{14}}+13\ ?$$

The number of digits of $N$ is $12,735,782,555,419,983$ (The number of digits of $N$ has itself $17$ digits). The first digits of $N$ are $1698324865652...$ and the last digits are $...6015154651149$

It is hopeless to apply a primilaty test for $N$ because $N$ is far too large. I applied trial division and found no prime factor below $6\times 10^9$.

I do not think that there are any better methods to find a factor of such a number than trial division, so I invite number-theory-enthusiasts to join in the search for prime factors.

$\endgroup$
5
  • 1
    $\begingroup$ How did you come up with this question? Is it a problem you are supposed to solve (assigned to you by a teacher etc.)? Otherwise, why do you think anyone knows a prime divisor? $\endgroup$ Commented Jan 28, 2016 at 14:18
  • 3
    $\begingroup$ No, I do not think that anyone knows a factor. And no, it is of personal interest. But why should not some number theorists run a computer program and search for factors ? $\endgroup$
    – Peter
    Commented Jan 28, 2016 at 14:23
  • $\begingroup$ At least it would be possible to raise the search limit well above $6\cdot 10^9$ by patiently waiting for some (good) software. $\endgroup$ Commented Jan 28, 2016 at 14:26
  • 1
    $\begingroup$ @Peter: And what are its middle digits ? :-$)$ $\endgroup$
    – Lucian
    Commented Jan 28, 2016 at 18:07
  • 2
    $\begingroup$ Especially the middlest digit would be interesting, but there is no way to find it out. $\endgroup$
    – Peter
    Commented Jan 28, 2016 at 19:45

1 Answer 1

11
$\begingroup$

The smallest prime factor of $ 14^{14^{14}}+13$ is $13990085729$.

Trial division should be the only way to find factors of such big numbers.

Pollards-RHO Method and ECM both need $gcd(q,N)$ for some small $q$ while $N$ is far out of range for such computations.

The trial division with modular exponentiation I used in Pari/GP:

forprime(p=2,10^11,if(!(Mod(14,p)^11112006825558016+13),return(p)))

returns the result

time = 10min, 58,230 ms.
%1 = 13990085729

Note: precomputing $14^{14}=11112006825558016$ speeds up the algorythm about 7%.

$\endgroup$
1
  • 2
    $\begingroup$ No further factors found below $10^{11}$. $\endgroup$ Commented Oct 15, 2018 at 7:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .