# Prime numbers $p$ not of the form $ab + bc + ac$ $(0 < a < b < c )$ (and related questions)

If we ask which natural numbers n are not expressible as $n = ab + bc + ca$ ($0 < a < b < c$) then this is a well known open problem. Numbers not expressible in such form are called Euler's "numerus idoneus" and it is conjectured that they are finite.

If we omit the condition $a < b < c$ and assume $0 < a \leq b \leq c$ then it was proved (assuming Generalized Riemann Hypothesis) that there is only a finite number of such numbers $n$.

I am interested in the problem of expressing a prime number $p$ as $p = ab + ac + bc$ for $a \geq 1$ and $b,c \geq 2$.

Anybody knows if there is some known result related to expressing prime numbers in such form? This would yield (as a corollary) a very beautiful theorem related to spanning trees in graphs.

Looking at the encyclopedia of integer sequnces, I've found that the set of numbers not expressible as ab + bc + ac 0 < a < b < c is finite.

http://oeis.org/A000926

Chowla showed that the list is finite and Weinberger showed that there is at most one further term.

• Very nice! Looking at the list of known examples, only 2,3,5,7,13 and 37 are prime. So there is at most one more prime we don't know about. Commented Nov 21, 2009 at 21:24
• If there is one more prime then Riemann Hypothesis is false (Weinberger's list depends on Riemann).
– user76479
Commented Sep 5, 2015 at 13:58

One can get every prime which is NOT a Sophie Germain prime; that is to say, such that (p+1)/2 is not prime. Proof: if (p+1)/2 is not prime, then we can factor p+1 = xy. If p+1 is not prime, we can impose that x and y are greater than 2 and, since p is prime, it is not of the form x^2-1 (except for p=3). So we can take 2 < x < y.

Then take (a,b,c) = (1,x-1,y-1).

13 and 37 cannot be achieved.

• I looked at the wikipedia entry for Sophie Germain prime and it stated it as a prime p where 2p+1 is prime. Your argument still works though p must not be 2q+1 where q is a Sophie Germain prime or it must not be the matching safe prime of a Sophie Germain prime. Commented Nov 21, 2009 at 20:36
• If a Sophie Germain prime p is of the form 2q+1 where q is prime then p+1/2-1 is prime so it looks like it will make a difference. Look at 37 37+1 = 38 =2*19 and your agument breaks down but 37 is not a Sophie Germain prime or a matching safe prime because it is equal to 1 mod 6 not 5 mod six. I think your argument works for everything except p and 2p-1 paris which is different from p, 2p+1 of the Sophie Germain prime Commented Nov 21, 2009 at 21:08

I can get all primes of the form $3n+2$. let $a=1, b=2$ and $c=n$ we get $1.2+1n+2n=3n+2$. $n$ is greater than than or equal to $2$. You cannot get $2,3$ and $5$ or $7$ as your smallest number is $8$. This gives an infinite number of primes due to Dirichlet's theorem on arithmetic progressions. So we get all primes of the form $3n+2$ greater than $8$. We can get some primes of the form $3n+1 1,3,4$ gives $1.3 +1.4+3.4=19$. We can get an infinite family $3,4,3n+1$ gives $3.4+ 9n+3+12n+4 = 21n+19$ all of these are of form $3n+1$ and again by Dirichlet's theorem there are an infinite number of these. From other posts we have the following argument: Now if $p$ is greater than $11$,$(p+1)/2$ is composite for any prime $p$,$p+1$ can be factored into $x,y$ both greater than $2$ and if we take $1, x-1,y-1$ we will get $(x-1)+(y-1)+(x-1)(y-1) =p$ Which eliminates all primes except those where $p+1/2$ is prime. I don't think these are Sophie Germaine primes, if they were we would be done as we have all primes of form $6n+5$ greater than $8$ already represented and Sophie Germaine primes are of the form $6n+5$. From another the following are not expressible $2,3,5,7,13$ and $37$ and there is at most one more possible prime not expressible from the above it must be of the form $3n+1$ it also must be larger than $100000000$ see the following:

• The argument is just to choose an $a$ and a $b$, in particular, $1$ and $2$, and then the problem reduces to "Which primes can be written as $2n+3$ for some $n\geq 2$. That's the same as $(2n+2)+1=2k+1$ for $k\geq 3$, so every odd number greater than seven, and in particular, every odd prime, can be written this way. Commented Nov 21, 2009 at 18:47
• I am not sure why is your argument correct. Can you find a representation for say 37? The only representation I find is 37 = 1*18 + 18 + 1 Commented Nov 21, 2009 at 20:05
• 37 is not of the form 3n+2 and your representation doesn't satisfy the strictly increasing condition. Commented Nov 21, 2009 at 20:07

Partial answer: Set a=1, so you want to enumerate the primes of the form b+c+bc = (b+1)(c+1)-1. This covers all primes p such that p+1 is a product of two factors of size at least 3. The leftovers (almost certainly covered by other values of a for sufficiently large primes) come from Sophie Germain pairs, which are conjectured to be infinite, but rather sparse.

More generally, the counterexamples are exactly those primes p such that for any positive n, p+n2 is not a product of two numbers strictly larger than n+1. It suffices to check for n up to p/4, since for larger n, (n+2)2 - n2 will be bigger than p.