7
$\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$
  • 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$ – Jeppe Stig Nielsen Jan 28 '16 at 14:18
  • 2
    $\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 Jan 28 '16 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$ – Jeppe Stig Nielsen Jan 28 '16 at 14:26
  • $\begingroup$ @Peter: And what are its middle digits ? :-$)$ $\endgroup$ – Lucian Jan 28 '16 at 18:07
  • 1
    $\begingroup$ Especially the middlest digit would be interesting, but there is no way to find it out. $\endgroup$ – Peter Jan 28 '16 at 19:45
8
$\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
    $\begingroup$ No further factors found below $10^{11}$. $\endgroup$ – Martin Hopf Oct 15 '18 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.