Mind your p's and q's cubed

Firstly, $q\mid p^3-1=(p-1)(p^2+p+1)$ . Clearly $q$ does not divide $p-1$ (since $0<p-1<q$ ), hence $q\mid p^2+p+1$ .

Now $p\mid q^3-1=(q-1)(q^2+q+1)$ , so there are two cases.

~~

Case 1: $p$ divides $q-1$ . Then clearly $q\geq p+1$ .

Consider the integer $n=\frac{p^2+p+1}{q}$ . On one hand, since both the numerator and denominator of this fraction are $\equiv 1 \pmod{p}$ , $n$ is also $\equiv 1\pmod{p}$ . On the other hand, $n\leq\lfloor\frac{p^2+p+1}{p+1}\rfloor=\lfloor p+\frac{1}{p+1}\rfloor=p$ , since $q\geq p+1$ . Therefore $n=1$ , and thus $q=p^2+p+1$ .

Checking for all prime values of $p\leq31$ (since $37^2+37+1>1000$ ), we see that the solutions in this case are $(p,q) = (2,7),(3,13),(5,31),(17,307)$ . (For all other values of $p$ , $q=p^2+p+1$ is not prime.)

~~

Case 2: $p\mid q^2+q+1$ . Then since $q\mid p^2+p+1$ we have $pq\mid p^2+q^2+p+q+1$ .

To find the solutions in this case, let us consider the more general equation $a^2+b^2+a+b+1 = mab$ , where $a,b,m$ are positive integers. Without loss of generality assume $a\geq b$ .

We will now use the method of Vieta jumping to solve this equation. The basic idea is as follows: if $(a_0,b_0)$ is a solution to the equation, we will create another "smaller" solution $(a_1,b_1)$ in terms of $a_0,b_0$ , such that $a_1+b_1<a_0+b_0$ . By the same method we can create $(a_2,b_2)$ in terms of $a_1,b_1$ , and so on. But we cannot repeat this "jumping downwards" indefinitely, since $a_0+b_0,a_1+b_1,a_2+b_2,\ldots$ is a decreasing sequence of positive integers. Hence we must end at some point, say $(a_n,b_n)$ , and by investigating what this solution can be, we will eventually be able to reconstruct $(a_0,b_0)$ by "jumping upwards" from $(a_n,b_n)$ .

To apply this method to the equation, rewrite the equation as a quadratic in $a$ : $a^2+(1-mb)a+(b^2+b+1)=0.$ Assume that $(a_0,b_0)$ is a solution to the above equation, with $a_0\geq b_0$ . Since this equation is a quadratic in $a$ when we fix $b=b_0$ , the equation has two solutions in $a$ , namely $a=a_0$ and another root, say $a=a'$ . Then Vieta's formulas give the following: $a_0+a'=mb_0-1\\ a_0a'=b_0^2+b_0+1$ The first equation tells us that $a'=mb_0-1-a_0$ is an integer, and the second equation tells us that $a'=\frac{b_0^2+b_0+1}{a_0}$ is positive.

Moreover, if $a_0\geq\frac{b_0^2+b_0+1}{b_0}$ , then $a'=\frac{b_0^2+b_0+1}{a_0}\leq b_0$ , and we can thus choose $(a_1,b_1)=(b_0,a')$ as a "smaller" solution to the equation.

Repeating this procedure, we create a sequence of solutions

$(a_0,b_0),(a_1,b_1),(a_2,b_2),\ldots$ ,

each smaller than the previous, until we encounter a solution $(a_n,b_n)$ where $a_n<\frac{b_n^2+b_n+1}{b_n}$ , and we can no longer jump downwards. Let us now investigate the possible values for $(a_n,b_n)$ .

Note that $b_n\leq a_n<\frac{b_n^2+b_n+1}{b_n}\leq b_n+2$ , so either $a_n=b_n$ or $a_n=b_n+1$ . Substituting both cases back into the equation and taking $\pmod{a_n}$ , we see that the only possible solution is $(a_n,b_n)=(1,1)$ . Hence $m=5$ .

Now note that $(a_i,b_i)=(b_{i-1},5b_{i-1}-a_{i-1}-1)$ for all $i$ . Hence $b_{i-1}=a_i$ and $a_{i-1}=5b_{i-1}-b_i-1=5a_i-b_i-1$ . For example: $(a_{n-1},b_{n-1})=(5a_n-b_n-1,a_n)=(3,1);$ $(a_{n-2},b_{n-2})=(5a_{n-1}-b_{n-1}-1,a_{n-1})=(13,3);$ $(a_{n-3},b_{n-3})=(5a_{n-2}-b_{n-2}-1,a_{n-2})=(61,13),$ and so on.

Now it is simple to prove by induction that the sequence $1,1,3,13,61,291,\ldots$ defined by $x_0=x_1=1$ , $x_{i+1}=5x_i-x_{i-1}-1$ for all $i\geq1$ , satisfies $(a_{n-i},b_{n-i})=(x_{i+1},x_i)$ for all $i\geq0$ .

Thus all solutions $(a_0,b_0)$ must be of the form $(x_{n+1},x_n)$ for some $n\geq0$ .

Finally, to answer our original question, $(q,p)=(x_{n+1},x_n)$ for some $n$ . In addition, both $x_{n+1}$ and $x_n$ are prime, and $x_{n+1}<1000$ . Checking all $n\leq4$ (since $x_6>1000$ ), we have only the solutions $(p,q)=(3,13),(13,61)$ .

~~

In conclusion, the only solutions to the problem are

$(p,q)=(2,7),(3,13),(5,31),(13,61),(17,307)$ ,

and thus the answer to the problem is $7+13+31+61+307=419$ .

First, we note that $p^3-1=(p-1)(p^2+p+1)$ , so $q \mid p^3-1 \Rightarrow q \mid p-1$ or $q \mid p^2+p+1$ . But $q > p > p-1$ , so $q \nmid p-1$ . So $q \mid p^2+p+1$ . Similarly, $p \mid q^3-1 \Rightarrow p \mid q-1$ or $p \mid q^2+q+1$ . So we will need to consider two cases: $p \mid q-1$ and $p \mid q^2+q+1$ .

Case 1: $p \mid q-1$

Let $q-1=ap$ . Then $q=ap+1$ . Since $q>p$ , then $a \geq 1$ . Also since $q \mid p^2+p+1$ , we can let $p^2+p+1=kq$ for some positive integer $k$ ( $k$ is clearly non-zero). Express $k$ in the form $bp+c$ , where $b,c$ are non-negative integers with $0 \leq c < p$ . Then $p^2+p+1=(bp+c)(ap+1)$ . Taking modulo $p$ , we easily see that $c \equiv 1 \pmod{p}$ , so $c=1$ . Thus, $p^2+p+1=(bp+1)(ap+1)$ . If $b \geq 1$ , then $p^2+p+1 \geq (p+1)(p+1) = p^2+2p+1$ , which is clearly false. So $b=0$ . Therefore, $p^2+p+1=(0p+1)(ap+1)=ap+1=q$ . Indeed, if $q=p^2+p+1$ , then $p \mid q-1$ (and hence $p \mid q^3-1$ ) and $q \mid p^2+p+1$ (and hence $q \mid p^3-1$ ). So we just need to find all primes $q$ of the form $p^2+p+1$ (where $p$ is prime) below $1000$ . Since $q < 1000$ , $p < \sqrt{1000} < 32$ . The possible $p$ are $2,3,5,7,11,13,17,19,23,29$ and $31$ . If $p \equiv 1 \pmod{3}$ , then $q \equiv 1^2+1+1 \equiv 0 \pmod{3}$ is not prime (note that $q>3$ since $2^2+2+1>3$ ). So we only need to check $p=2,3,5,11,17,23$ and $29$ . The corresponding $q$ are $7,13,31,133,307,553$ and $871$ . The only primes among these are $7,13,31$ and $307$ ( $133$ and $553$ are divisible by $7$ ; $871$ is divisible by $13$ ), so the only pairs of $(p,q)$ are $(2,7),(3,13),(5,31)$ and $(17,307)$ .

Case 2: $p \mid q^2+q+1$

Instead of primes $p,q$ , we first consider generally two integers $s,t$ , where $1 \leq s \leq t$ , such that $t \mid s^2+s+1$ and $s \mid t^2+t+1$ . Note that $s=p$ and $t=q$ is subsumed under this general definition. Let $tr=s^2+s+1$ for some positive integer $r$ ( $r$ is clearly non-zero). Clearly, $gcd(s,t) \mid tr-s^2-s \Rightarrow gcd(s,t) \mid 1 \Rightarrow gcd(s,t)=1$ . Since $tr \equiv 1 \pmod{s}$ , then $t^2(r^2+r+1) \equiv (tr)^2+t(tr)+t^2 \equiv 1+t+t^2 \equiv 0 \pmod{s}$ . Since $gcd(s,t)=1$ , then we can deduce that $r^2+r+1 \equiv 0 \pmod{s}$ , i.e. $s \mid r^2+r+1$ . Thus, if $t \mid s^2+s+1$ and $s \mid t^2+t+1$ , then $s \mid r^2+r+1$ and $r \mid s^2+s+1$ (remember that $tr=s^2+s+1$ ). This means that from any pair of integers $(s,t)$ satisfying $t \mid s^2+s+1$ and $s \mid t^2+t+1$ , we can generate another pair of integers $(r,s)$ satisfying $s \mid r^2+r+1$ and $r \mid s^2+s+1$ . In particular, we can call $(r,s)$ the descendant of $(s,t)$ if $r \leq s$ .

If $t=s$ , then $r = \frac{s^2+s+1}{s} = s+1+\frac{1}{s}$ . Since $r$ is an integer, then $s=1$ . But this means that $r=3>s$ , so $(1,1)$ does not have any descendants. If $t=s+1$ , then $r = \frac{s^2+s+1}{s+1} = s+\frac{1}{s+1}$ which obviously cannot be an integer. If $t \geq s+2$ , then $r = \frac{s^2+s+1}{t} \leq \frac{s^2+s+1}{s+2} = s-\frac{s-1}{s+2} \leq s$ since $s-1 \geq 0$ . So $(r,s)$ is a descendant of $(s,t)$ in this case. Also, since $gcd(s,t) = 1$ , then $s \neq t$ if $(s,t) \neq (1,1)$ . Thus, with the exception of $(1,1)$ , we have $s < t$ and $r \leq s$ , so $s+t > r+s$ , i.e. the sum of the pair of numbers in the ancestor will be greater than that in its descendant. This is important because it means that for any pair $(s,t)$ such that $1 \leq s \leq t$ , $t \mid s^2+s+1$ and $s \mid t^2+t+1$ , it is possible to generate its chain of descendants (with decreasing sum of the pair of numbers) till we reach $(1,1)$ .

We have proven that each pair $(s,t)$ (satisfying $1 \leq s \leq t$ , $t \mid s^2+s+1$ and $s \mid t^2+t+1$ ), with the exception of $(1,1)$ , has exactly one descendant $(\frac{s^2+s+1}{t},s)$ . Now we suppose a descendant $(r,s)$ of an ancestor $(s,t)$ has another ancestor $(s,T)$ . Then we have $\frac{s^2+s+1}{T} = \frac{s^2+s+1}{t}$ , so we can easily see that $T = t$ . Thus, each pair $(r,s)$ (satisfying $1 \leq r \leq s$ , $s \mid t^2+t+1$ and $r \mid s^2+s+1$ ) has exactly one ancestor as well. Specifically, this ancestor is $(s,\frac{s^2+s+1}{r})$ . This is important because it means that from any pair $(r,s)$ such that $1 \leq r \leq s$ , $s \mid t^2+t+1$ and $r \mid s^2+s+1$ , we can re-construct its unique ancestor, which is $(s,\frac{s^2+s+1}{r})$ .

Now, it is possible to list all the $(s,t)$ satisfying $1 \leq s \leq t$ , $t \mid s^2+s+1$ and $s \mid t^2+t+1$ using the ancestor-descendant relationships and starting from the descendant $(1,1)$ . In particular, we are only looking at the pairs $(s,t)$ where both $s$ and $t$ are prime and where $t < 1000$ . Since the pairs will only get larger and larger, we can stop when the larger number of the pair exceeds $1000$ . The pairs are: $(1,1), (1,3), (3,13), (13,61), (61,291)$ and $(291,1393)$ . Since $1$ and $291=3\cdot97$ are not primes, then the only valid pairs $(p,q)$ are $(3,13)$ and $(13,61)$ .

Combining the results we have for both cases, we have $(p,q)=(2,7),(3,13),(5,31),(13,61)$ and $(17,307)$ . The sum of all $q$ is thus $7+13+31+61+307=419$ .

If $p = 2$ , then the only possible $q$ is $q = 7$ , so we will consider this solution and from now on take $p, q$ as odd primes.

$q \mid (p - 1)(p^2 + p + 1)$ . Since they are primes, and $q > p$ , it follows that $q \mid p^2 + p + 1$ , or $kq = p^2 + p + 1$ , where $k$ is an integer, and also is relatively prime with $p$ . Now we have 2 cases:

First case: $p \mid q - 1$ . Substituting for $q$ , we get $p \mid \frac{p^2 + p + 1}{k} - 1$ now, because $(k, p) = 1$ , it follows that $p \mid 1 - k$ . The only solution is $k = 1$ . Substituting in the other equation gives: $q = p^2 + p + 1$ . We test all small primes p, and see that only for $p \in {3, 5, 17}$ , $p^2 + p + 1$ is also a prime, so $q \in {13, 31, 307}$

[Note: This solution doesn't justify why we cannot have $k=p+1, 2p+1, \ldots$ This follows from observing that since $q \geq p+1$ , thus $k= \frac {p^2+p+1}{q} < p+1$ , which is hinted at in the second case. -Calvin]

Second case: $p \mid q^2 + q + 1$ . Lets omit the fact that they must be primes, just consider them as odd integers, find all solutions, and then check for the primes.
$k^2 + k + 1 = \left( \frac{p^2 + p + 1}{q} \right) ^2 + \frac{p^2 + p + 1}{q} + 1 \equiv \frac{q^2 + q + 1}{q^2} \equiv 0 \pmod p$ . If $p > 2$ it follows that: $k = \frac{p^2 + p + 1}{q} \leq \frac{p^2 + p + 1}{p+2} = p - 1 + \frac{4}{p+2} < p$ . From the last $2$ statements it follows that if $(p, q)$ is a solution to the system, with $q > p > 2$ , then $\left( \frac{p^2 + p + 1}{q} , p\right)$ is a smaller solution. Reducing the solutions this way, they will all trace to the solution with $p = 1$ , that is $(1, 3)$ . So we can start from $(1, 3)$ and increase the solution to get the pairs: $(1, 3), (3, 13), (13, 61), (61, 291), (291, 1393), \ldots$ . The first one does not contain only primes, we already have the 2nd solution, the third solution is primes, the fourth is not a prime since 291 is a multiple of 3, and the rest will yield $q > 1000$ .

So the solutions are: ${7, 13, 31, 307, 61}$ .

We will solve this by finding the two families of solutions to $p \mid q^3 - 1$ and $q \mid p^3 - 1$ .

Suppose we have a solution. Then $q \mid (p-1)(p^2+p+1)$ . But $q \nmid (p-1)$ since $q > p$ , so $q \mid p^2+p+1$ .

Our two families will arise from $p \mid q-1$ and $p \mid q^2 + q + 1$ respectively.

Case 1: $p \mid q-1$

We will show that, in this case, $q = p^2 + p + 1$ . Indeed, suppose not; then $qr = p^2 + p + 1$ for some $r$ . But $q$ is 1 mod $p$ , and so is the RHS, hence $r$ is. But that means that $q$ and $r$ are both at least $p + 1$ , so $qr \geq p^2 + 2p + 1$ , contradiction.

This is one family; $(p,q)$ such that $q = p^2 + p + 1$ . It is easy to see that this works, provided that both $p$ and $q$ are prime.

For the solutions with $q \leq 1000$ , we need simply check all primes $p \leq 32$ . This is not a difficult check, and results in the list (2,3,5,17) for $p$ , and (7,13,31,307) correspondingly for $q$ .

Case 2: $p \mid q^2 + q + 1$

Let us instead consider positive integer solutions to $x \mid y^2 + y + 1$ and $y \mid x^2 + x + 1$ . We will find that solutions to the original relation correspond to solutions to this one, where x and y are both prime. Let $z = \frac{y^2 + y + 1}{x}$ . Note that by the first relation, $z$ is an integer and $z \mid y^2 + y + 1$ .

Also, working modulo $y$ , $z = \frac{1}{x}$ , and so $z$ is the other root to the equation $t^2 + t + 1 \equiv 0$ mod $y$ . Hence, if $(x,y)$ solved the relation, then so will $(z,y)$ .

I claim that all solutions are a pair of consecutive terms in the sequence 1,1,3,13,61,291,... (clearly all further terms are greater than 1000), where $u_{n-1}u_{n+1} = u_n^2 + u_n + 1$ . Indeed, suppose we have a solution outside that sequence, $(x,y)$ , with $x \geq y$ . Take the solution with smallest $x + y$ . If $x = y$ , then it is easy to see that they must both equal 1, contradiction (as (1,1) is in the sequence). Otherwise, $z,y$ is a solution (from above), but with smaller sum, contradiction.

Hence, all solutions are pairs of consecutive terms in that sequence which are both prime. But the only such pairs with $q \leq 1000$ are (3,13) and (13,61), introducing a fifth solution, as we’ve already found (3,13).

Hence, $q \in \{7,13,31,61,307\}$ , with sum 419.

Because $p<q$ , $q$ cannot divide $p-1$ , so $q \mid p^2+p+1$ . For $p \mid q^3-1$ two cases exist.

Case 1. $p\mid q-1$ . Suppose $q=pk+1$ . Because $q\mid p^2+p+1$ , we have

$q\mid p^2k+pk+k=p(pk+1)+pk-p+k=p(pk+1)+(pk+1)+k-p-1$

So, $q=pk+1$ must divide $k-p+1$ . Because $q\leq p^2+p+1,$ $k \leq \frac{p^2+p}{p},$ so $k\leq p+1$ . On the other hand, $k\geq 1$ , so $k-p-1\geq -p>-q$ . So the only way $q$ could divide $k-p-1$ is if $k-p-1=0$ . This implies that $q=p^2+p+1$ .

If $p=2$ , then $q=7$ . If $p=3$ , then $q=13$ . If $p>3$ , one can easily check that if $p \equiv 1 \pmod{6}$ , then $q \equiv 1 + 1 + 1 = 3 \pmod{6}$ , so we must have $p\equiv 5\pmod 6$ . We get pairs $(p,q)=(5,31)$ , $(17,307)$ . Note that for $p=11$ and $p=23$ the number $p^2+p+1$ is divisible by $7$ ; for $p=29$ it is divisible by $13$ (by easy calculations modulo the corresponding primes). For all other $p$ , $p\geq 35$ so the number $p^2+p+1$ is greater than $1000$ .

Case 2. $p\mid q^2+q+1$ . In this case, we consider a more general problem: find all pairs of positive integers $n<m$ , not necessarily prime, such that $n\mid m^2+m+1$ and $m\mid n^2+n+1$ . One can check that such $n$ and $m$ must be coprime. If $n^2+n+1=mk$ , then obviously $k\mid n^2+n+1$ and, a little less obviously, $n\mid k^2+k+1$ (because $k\equiv \frac{1}{m} \pmod n$ and $m^2+m+1 \equiv 0 \pmod n$ ).

Simple inequalities show that, unless $(n,m)=(1,3),$ $k<n$ . So any pair $(n,m)$ can be reduced to $(1,3)$ . Backtracking, we get the following sequence of pairs $(n,m)$ : $(1,3)\to (3,13)\to (13,61)\to (61,291)\to (291,1393)\to ...$ Out of these, $(13,61)$ is a pair of primes, not considered before, and $291$ is divisible by $3$ .

Putting this all together, we get five possible prime pairs: $(2,7),\ (3,13),\ (5,31),\ (13,61),\ (17,307)$ So the answer is $7+13+31+61+307=419$ .

int main() { int a,b,count=0,flag,c[1000]; for (a=2;a<1000;a++) { flag=0; for (b=2;b<a;b++) {
if (a%b==0) {flag=1; break; }
} if (flag == 0) {count++; c[count-1]=a; } }
int i,j,ecr=0; for (i=0;i<168;i++) { for (j=0;j<i;j++) { if ( ((c[i] c[i] c[i])-1)%c[j]==0 && ((c[j] c[j] c[j])-1)%c[i]==0) { ecr ++; cout<< c[i] <<'\n'; }
} }
cout<<ecr; return 0; }

By trial and error p = 2, q = 7 is a solution.

And for small values for p, we can find their respective q values, with small, p (p^3 - 1) is easily computable and factorizable because (p^3 - 1) = (p-1)(p^2 + p + 1), so we just need to find whether q divides (p^2 + p + 1)

Other small values of p are 3, 5, 13, 17 which corresponds to q = 13, 31, 61, 307 respectively.

Note that the sum of q is 7+13+31+61+307=419

Since the answer must range from 0 to 999. If there exist another value of q such that the final sum is less than 1000. Then 307<q<1000-419=518

Listing down the values of prime numbers in the range: {311, 313, 317, ... 499, 503, 509}, that's a total of 34 prime numbers. Do trial and error for those possible values of q gives no solution for p. So the final answer is indeed 419.

first we do some calculation: 2^3-1=7 3^3-1=26 5^3-1=124 7^3-1=342 11^3-1=1330 13^3-1=2196 17^3-1=4912 19^3-1=6856... (the others are unnessary) p^3-1=(p-1)(p^2+p+1) let q=(p^2+p+1)/k for p>31, q>1000, so p<=31. for k=1 we get (2,7),(3,13),(5,31),(17,307), let k not equal to 1, for all p<31 p^2+p+1 has prime factors range from 2 to 19, but as calculation above shows only (13,61) is a solution where k = 3 so 7+13+31+61+307=419

By satisfying the above conditions only 3 pairs are available. these are (2,7),(3,13),(5,31),(13,61),(17,307).

If $q$ divides $p^3-1$ then $\exists k \in$ Z such that $k \cdot q = p^3-1 = (p-1) \cdot (p^2+p+1)$ . As $p < q$ then $\exists h \in$ Z such that $h \cdot q = p^2 + p + 1$ .

If p divides $q^3 -1$ then $\exists r \in$ Z $r \cdot p = h^3 \cdot (q^3-1) = (p^2 + p + 1)^3 - h^3 = p^6 + 3 \cdot p^5 + ... 3 \cdot p + 1 - h^3$ , therefore $p$ divides $1 - h^3$ .

If $h=1$ :

$\begin{matrix} p \xrightarrow{\;\;\;\;\;\;} q=p^2+p+1 \\ 2 \xrightarrow{\;\;\;\;\;\;} 7\\ 3 \xrightarrow{\;\;\;\;\;\;} 13 \\ 5 \xrightarrow{\;\;\;\;\;\;} 31 \\ 7 \xrightarrow{\;\;\;\;\;\;} 57 = 3\cdot 19 \\ 11 \xrightarrow{\;\;\;\;\;\;} 133 = 7 \cdot 19 \\ 13 \xrightarrow{\;\;\;\;\;\;} 183 = 3 \cdot 61 \\ 17 \xrightarrow{\;\;\;\;\;\;} 307\\ 19 \xrightarrow{\;\;\;\;\;\;} 381 = 3 \cdot 127\\ 23 \xrightarrow{\;\;\;\;\;\;} 553 = 7 \cdot 79 \\ 29 \xrightarrow{\;\;\;\;\;\;} 871 = 13 \cdot 67 \\ 31 \xrightarrow{\;\;\;\;\;\;} 993 = 3 \cdot 331 \\ \end{matrix}$

Therefore q = 7, 13, 31, 307 and if $h = 3$ then $p = 13$ because $p$ divides $1 - h^3$ , therefore q = 61 is the only one.

$7 + 13 + 31 + 307 + 61 = 419$ .