MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a primes $p$ sufficiently large, does there always exists positive integers $k,a,b\in\mathbb{N}$ such that $p=(k+1)(ab)+k(a+b)$ or equivalently $p\equiv (ab)\bmod ((a+b)+ab)$?

Please note that from Frobeneius $p=(k+1)X+kY$ is solvable in non-negative integers $X,Y$ provided p>XY-(X+Y), what I am looking for is the existence of a sub-class of positive intger solutions where X=ab and Y=a+b.

share|cite|improve this question
I think looking up stuff related to covering families of congruences might help. – Eric Naslund Jan 21 '11 at 4:10

If $2p+1$ is composite there is a solution with $k=1$ and if it is prime then there is none with $k=1$. In general there is a solution with $k=K$ if and only if $(K+1)p+K^2$ factors as the product of two factors both congruent to -1 $\mod K$. I suspect that there are infinitely many exceptions however this would imply that that there are infinitely many Sophie Germain primes (2p+1 also prime). This is not known to be true although there is every reason to expect that there are about $\frac{n}{\log^2n}$ such less than $n$.

$p=(k+1)(ab)+k(a+b)$ is true exactly if $(k+1)p+k^2=((k+1)a+k)((k+1)b+k)$. So the number $(k+1)p+k^2=(k+1)(p+k-1)+1$ must factor as the product of two numbers congruent to $-1 \mod k+1$

The largest that $k$ could be is $\frac{p-2}{5}$ in case $(a,b)=(1,1)$. Of course then $2p+1$ is not prime (if $p \ne 2$)

It may be that there are only finitely many primes with $(k+1)p+k^2$ prime for all $k$ up to $p/5$ however we don't need them all prime, just to not have any factor congruent to $k \mod k+1.$

The first few Sophie Germain primes are $$2, 3, 5, 11, 23, 29, 41, 53, \mathbf{ 83}, 89, 113, 131, 173, 179, 191, 233, 239, 251, \mathbf {281}, 293,\mathbf{359}$$ None of these satisfy an equivalence as above except 83 for $(a,b)=(2,3),(2,7),(3,7)$ ,281 for $(a,b)=(2,3),(4,5),(4,9),(5,9),(2,25),(3,25)$ and 359 for $(a,b)=(2,7),(2,15),(7,15)$

In all there are 65 primes under 10000 which do not satisfy an equivalence of the desired type. All of the exceptions are Sophie Germain primes. The largest Sophie Germain primes under 1000 are

$$9371, \mathbf{9419, 9473, 9479}, 9539, \mathbf{9629, 9689, 9791}$$ and all of these DO satisfy a congruence of the desired type with the exceptions of 9371 and 9539.

share|cite|improve this answer
Does either list (bad primes, or its complement) show up in the Online Encyclopedia of Integer Sequences? – Gerry Myerson Jan 21 '11 at 4:12
That is strange, it works for some Sophie Germain's but not others? I wonder what is special in the bad cases. – Eric Naslund Jan 21 '11 at 8:04
I don't fully grasp it but my addition at the bottom is relevant. The bad ones are sort of super Sophie Germain: With p=11, 23,37,53,71 are all prime ($(k+1)p+k^2$ for $k=1,2,3,4,5$) at $k=6$ we have $91=7*13$ but that does not factor into two numbers of the form $6j+5$. With p=83 and $k=2$ we have $3*83+4=11*23$ and the factors are $3a+2=3*3+2$ and $3b+2=3*7+2$ so we have a solution with $(a,b,k)=(3,7,2)$ – Aaron Meyerowitz Jan 21 '11 at 8:37
Doesn't the original poster exclude your $k=0$ when insisting on positive integers? – jerr18 Jan 21 '11 at 10:23
Yes but then the OP says "or equivalently...." and says something which is not equivalent unless one adds ab<p. – Aaron Meyerowitz Jan 21 '11 at 12:41

Thanks for your interesting comments particularly about the Sophie Gemaine Primes. It is interesting that when $2p+1$ is composite with $2p+1=cd$ where $c\equiv 1(\bmod 4)$ and $d\equiv 3\bmod 4)$ there is always a solution. Another avenue of exploration I have been thinking about is to use some argument around constructing Covering Systems of Congruences, but this is a vague idea at best.

share|cite|improve this answer
Or even when $2p+1$ is composite with $2p+1=cd$ where $c\equiv 1(\bmod 2)$ and $d\equiv 1(\bmod 2)$ and $c,d>1$ – Aaron Meyerowitz Jan 21 '11 at 9:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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