# Least prime of the form $38^n+31$

I search the least n such that

$$38^n+31$$

is prime.

I checked the $n$ upto $3000$ and found none, so the least prime of that form must have more than $4000$ digits. I am content with a probable prime, it need not be a proven prime.

-
If $n$ is odd, then $3 \vert (38^n+31)$. If $n$ is of the form $4k+2$, then $5 \vert (38^n+31)$. The only case to be proved is $38^{4k}+31$ is not a prime. –  user17762 Dec 7 '13 at 19:49
@lhf Yes, for multiple of $4$, interestingly the prime factors get larger if $n \neq 12k+4$. If $n=12k+4$, then $7$ divides $38^n+31$. Hence, the only $n$'s that needs to be checked are $n=12k$ and $n=12k+8$. –  user17762 Dec 7 '13 at 19:53
Are you trying to crack some secret key? What got you interested in these numbers? –  1015 Dec 7 '13 at 20:36
Obviously, since nothing is lesser than $-\infty$, and since $39^{-\infty}+31=0+31=31$ is prime, this is then “the least n such that $39^n+31$ is prime”. :-) –  Lucian Feb 25 '14 at 14:26
If my idle-time computer calculation is correct, the expression is not prime for $n<185000$. –  Peter Košinár Feb 25 '14 at 23:39

This is not a proof, but does not conveniently fit into a comment.

I'll take into account that $n=4k$ is required, otherwise $38^n+31$ will be divisible by $3$ or $5$ as pointed in the comments.

Now, if we treat the primes as "pseudorandom" in the sense that any large number $n$ has a likelihood $1/\ln(n)$ of being prime (which is the prime number density for large $n$), the expected number of primes for $n=4,8,\ldots,4N$ will increase with $N$ as $$\sum_{k=1}^N\frac{1}{\ln(38^{4k}+31)} \approx\frac{\ln N+\gamma}{4\ln 38} \text{ where }\gamma=0.57721566\ldots$$ and for the expected number of primes to exceed 1, you'll need $N$ in the order of 1,200,000.

Of course, you could get lucky and find it at much lower $n$, but a priori I don't see any particular reason why it should be...or shouldn't.

Basically, in general for numbers $a^n+b$, the first prime will usually come fairly early, otherwise often very late (or not at all if $a$ and $b$ have a common factor).

Of course, this argument depends on assuming "pseudorandom" behaviour of the primes, and so cannot be turned into a formal proof. However, it might perhaps be possible to say something about the distribution of $n$ values giving the first prime over different pairs $(a,b)$.

-
Also, a value of $n$ over $11030099$ would represent the largest known prime number. Based on your formula above, this gives an expected number of primes still just slightly over $1$. –  PhiNotPi Mar 24 '14 at 0:31

Primality of numbers of the form $a^n+b$ is a very hard problem in general. For instance, existence of primes of the form $4294967296^n+1=(2^{32})^n+1$ is an old open problem in number theory (wiki), although it is also easy to show that this can be a prime only for $n$ of a special form (powers of $2$). Your problem $2085136^n+31=(38^4)^n+31$ does not seem much easier.

In other words, a theory-based answer to your problem is very unlikely in the near future. For a practice-based answer you will probably need to use some distributed computing project for searching for prime numbers like PrimeGrid, which has found most of the known large primes of the form $ab^n+c$.

-

This should be a comment for @Einar Rødland, but it's too long so I'm making it an answer.

Your argument gives a heuristic that there should be infinitely many primes of this form, but I'm not sure I believe it and here's why:

You are only taking into account the first two "bad" arithmetic sequences when you restrict to looking at things divisible by 4. In fact we have infinitely many "bad" arithmetic sequences we need to throw out.

If we try the same argument for numbers of the form $2^n + 1$ and we throw out $n \equiv 1 \mod 2$ and $n \equiv 2 \mod 4$ as they will all be divisible by 3 or 5, then running your argument would tell us to expect infinitely many primes of this form. However if we throw out all the "bad" arithmetic sequences (which in this case are much easier to classify) then we only are left with $n = 2^k$, taking this into account your heuristic gives finite expectation.

These two problems don't seem that different to me on the surface, and without a better understanding of the higher order "bad" arithmetic sequences, it's not clear to me what the right heuristic should be.

-
This is one of the reasons it is a heuristic argument. In some cases when this type of arguments are formalised, we talk of the generic case which e.g. could be that it would work for "most" expressions of the form $a^n+b$. (In algebraic geometry, "generic" means that the cases are parametrised by some space and the counter-examples are a subspace of lower dimension.) The case $a^n+1$ fails because $a^q+1|a^{qr}+1$ for any odd $r$, and so requires $n=2^k$ for $a^n+1$ to be prime. –  Einar Rødland Apr 23 '14 at 18:58

Enter the following code in Mathematica:

Simplify[PrimeQ[38^n + 31], n \[Element] Integers && n >= 1]


The result is False. This means for all natural numbers $n$, $38^n+31$ are not prime numbers.

-
It gives the same result when we replace $38$ with $0$. Are you saying that $31$ is not a prime ? :-) –  Lucian Mar 25 '14 at 2:23
@Lucian Thank you for your comment. Do you know where the problem is? Did I enter a wrong code, or Mathematica has a bug? :-) –  Wei-Cheng Liu Mar 25 '14 at 2:29
Why would there be a problem? I simply don't think that the instruction in question can be used the way you intend to. And since the software has no clue what to do with it, it probably just returns the default answer. –  Lucian Mar 25 '14 at 2:34
This is because PrimeQ is not something which can be simplified. It's not a normal mathematical formula, but rather a complex software subroutine. –  PhiNotPi Mar 25 '14 at 2:36
Thanks for Lucian and PhiNotPi's comments. –  Wei-Cheng Liu Mar 25 '14 at 3:54

## protected by Community♦Mar 22 '14 at 7:55

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.