Prime towers

Let the prime factor be $q$ . Then, we note that $n^2 - pn = n(n - p) = q^k$ for some integer $k > 0$ . Thus, $n = q^a, n - p = q^b$ , where $a, b \in \mathbb{N} \cup \{0\}$ and $a > b$ .

Thus, $p = q^a - q^b = q^b(q^{a - b} - 1)$ . Since $p$ is a prime, one of the factors is $1$ . If $q^{a - b} - 1 = 1$ , then $q = 2$ , and thus $p = 2$ . Note that if $p = 2$ , then $n = 3$ works.

If $q^b = 1$ , then $b = 0$ . Thus, $p = q^a - 1$ . If $q$ is odd, then $p$ is even, so $p = 2$ , which we stated earlier. Otherwise, $q = 2$ and thus $p$ is a Mersenne prime. The only Mersenne primes less than $1000$ are $3, 7, 31, 127$ , and it is easy to check that $n = p + 1$ works for each case. Thus, the sum of all primes $p$ satisfying the problem conditions is $2 + 3 + 7 + 31 + 127 = \boxed{170}$ .

Fun fact : The sum of the Mersenne primes $< 1000$ = The number of primes $< 1000$ !

Factoring the product as $n(n - p)$ , it's clear that $n$ must also be a prime power $i.e., n = q^k$ for $k \in \mathbb{Z}^+$ and $q$ is prime. Thus, the expression becomes $q^k(q^k - p) = q^n$ . Thus, $q^k - p = q^m \rightarrow q^k - q^m = p$ .

When $m > 0$ , then $q^m(q^{k - m} - 1)$ is prime. Thus, $m = 1$ and $q^{k - m} - 1 = 1 \rightarrow q = 2$ . This yields $p = 2$ as an answer.

When $m = 0$ , then $q^k - 1 = p$ . We already have $p = 2$ as an answer, so we can assume henceforth that $p$ is odd. Then, $q$ must be even (and thus $2$ , because it's prime), making our equation $2^k - 1 = p$ . Checking for prime $k$ (this is not a requirement in the problem, but since the primality of $2^k - 1$ implies the primality of $k$ (see Mersenne primes) we can do this to somewhat simplify calculations), we find $3, 7, 31, 127$ as solutions.

(Note that $p = 2$ has two answers in $(n, p) \rightarrow (4, 2) (3, 2)$ , but this is unimportant to the problem)

In summary, the valid $p$ are $2, 3, 7, 31, 127$ whose sum is $170$ .

Before we even move on to the solution itself, I shall remark first that the most famous prime power is the Mersenne primes .

---

The most preliminary observation is that we can factorise the expression given and, as we shall soon see, this is by no means a crucial fact. Utilising the definition of a prime power, we write:

$n^2 - pn = n(n-p) = q^m$ where $m > 0$ is a positive integer.

One most direct, yet key, implication is that $n = q^k$ and $n-p = q^l$ where $k + l =m$ and $k,l \geq 0$ are integers.

Now, here's where most people would forget. The question stated:

for some integer $n$

meaning that we have to also consider cases where $n$ is negative. However, fret not, for we see that if $n$ is negative, we can instead consider $n = n - p$ to reduce it to the case where $n$ is positive.

So, let us conclude that $k > l$ .

---

Let us now notice the following, motivated by the fact that we can isolate $p$ which works to our advantage since $p$ is a prime , and thus we can limit its factors to $1$ and itself, $p$ :

$p = n - (n - p) = q^l (q^{k-l} - 1) (*)$

We shall split, intuitively, into two cases:

(i) Consider the case when $q^{k-l} = 1$ . Now, $q$ by definition is prime too, which is to our advantage, since this implies that $q = 2$ , consequently $p = 2 \Rightarrow n=3$ .

(ii) Consider if $q^l = 1$ . Then clearly $l = 0$ . So subbing this into $(*)$ we obtain that $p = q^k - 1$ . Now, it is clear that we are left with an equation with only prime variables. Recall that the only "odd" prime is $2$ (pun intended). This means if we consider parity , then if $q$ is odd $\Rightarrow p=2$ which has already been discussed in case (i). This leaves the case when $q$ is even, thus $q=2$ and $p$ is odd. As our gentle introduction in the beginning signals, $p$ is a Mersenne prime. It can easily be verified by hand (since $2^{10} = 1024 > 1000$ already) that the only Mersenne primes less than $1000$ are $3, 7, 31, 127$ . Clearly $n = p+1$ works for each case.

---

In summary, the answer that we want is: $2 + 3 +7 +31+127 = \fbox{170}$ .

We have $n(n-p)=q^m$ where each variable is defined in the problem. Now we have two cases, when the second factor on the LHS is equal to $1$ and when it isn't.

Case 1: $n-p \neq 1$

By taking $\pmod{q}$ we note that $n \equiv p \equiv 0 \pmod{q} \implies p=q$ . Also note that $n$ clearly must be of the form $q^k$ where $k$ is a positive integer. Substituting these facts into our original equation, we get $q^{k-1}-1=q^l$ where $l=m-(k+1)$ Clearly the only possible value for $q$ in this equation is $2$ which after plugging in, we find $n=4$ which does indeed work. Hence $\boxed{p=2}$ is our only solution in this case.

Case 2: $n-p=1$

In this case we see that we must have $p=q^m-1$ however, by factoring the RHS as a difference of $m$ th powers, $q^m-1=(q-1)(q^{m-1}+q^{m-2}+\cdots+1)$ we see that the only value that makes the $m-1$ factor equal to $1$ is $q=2$ . Thus $p$ is of the form $2^m-1$ . We can now find all possible $p$ by listing out the powers of $2$ that are less than $1000$ and check the numbers that are one less than them. Doing this, we find that the only possible $p$ are $\boxed{p=3,7,31,127}$ so our final answer is $2+3+7+31+127=\boxed{170}. \blacksquare$

First thing to notice here is that, for an odd p, the expression has an even value for any integer value of n. Setting n = 4 and p = 2, $n^2-pn = 8$ Thus p=2 suffices necessary requirements. From previous observation, we can say that $n^2-pn \equiv n(n-p) \equiv 0 (mod 2)$ As 2 is the only prime divisor of the expression, $n = 2^k$ and $n-p = 2^m$ for some k and m. Since p is not divisible by 2, the only possible way all these conditions hold is if n - p = 1. So, $p+1 = 2^k$ for some k. Thus we only need to check primes p such that $p = 2^k - 1, 2^k <= 1000$ By trial and error, we find all such valid primes - $3, 7,31, 127$ All the valid primes add upto $\boxed{170}$ which is the solution to the problem.

Let $n^2-pn= q^m$ , where $q$ is a prime and $m \in \mathbb{N}$ . We rewrite this as $n(n-p)=q^m$ This implies $n= q^r$ and $n-p=q^s$ for some $r, s \in \mathbb{N}$ where $r+s=m$ . The easiest way to see this is that if either one of $n, n-p$ has another prime factor, $q^m$ would also have another prime factor, which is a contradiction.

First, note that for $p=2$ , $n=3$ satisfies. We can now let $p \equiv 1 \pmod{2}$ . We have $n-p= q^s$ $\implies q^r - q^s= p$ From here it follows that $r>s$ . If $q$ is odd, $q^r-q^s$ will be even, which means $p$ is even, a contradiction. So $q$ must be even. But if $s>0$ , we again find out that $q^r-q^s$ is even, a contradiction. So $s=0$ . This means $q= 2$ and $p= q^r-1$ . The only primes satisfying the condition, thus, are the prime of the form $2^r-1$ (Mersenne primes), and any $n= 2^j$ suffices.

We can now attempt to list down the Mersenne primes $<1000$ . Since $2^{10}>1000$ , we have to check it up to $r=9$ . This calculation can somewhat be simplified by noting that if $n=ab$ for some $a,b > 1$ , $2^n= \left ( 2^{a} \right )^{b} - 1 = (2^a-1)(2^{a+b} + 2^{a+b-1} + \cdots + 2^a)$ which is composite. So we just have to check for prime $r$ 's, i.e we have to check the set $\{2, 3, 5, 7\}$ . Doing this, we find out the set $\{3, 7, 31, 127\}$ . Including the prime $2$ , their su m is $2+3+7+31+127= \boxed{170}$

Let $n^2-pn=n(n-p)=q^k$ where q is a prime. Because q is a prime we may write $n=q^r$ $(1)$ and $n-p=q^t$ $(2)$ whith $r+t=k$ and $r>t$ . Putting these equations together gives us $q^r-p=q^t \iff q^r-q^t=p \iff q^t(q^{r-t} - 1)=p$ $(3)$ . Now p is a prime so we have two cases: $q^t=1$ or $q^{r-t}-1=1$ .

If $q^t=1$ we have $t=0$ and (2) gives $n-p=q^0=1 \iff n=p+1$ . Our original equation then gives us $(p+1)(p+1-p)=q^r \iff p+1=q^r$ . We see from this equation that p and q cant both be even or both be odd. So lets first assume that p is even and q odd. That gives only one solution for p, namely p=2. If p is odd then q is even and therefore q=2. Then $p=2^r-1$ , so p is a Mersenne prime. Mersenne primes under 1000 are $p \in (3,7,31,127)$ (found this on wikipedia didn't know how to do it otherwise).

Let us now assume $q^{r-t}-1=1$ . That gives $q^{r-t}=2$ so q=2 and $r-t=1$ . Plugging this into $(3)$ gives $q^t(q^{r-t}-1)=q^t=p$ so $t=1$ and therefore $r=2$ . We now put $n=q^2$ and $n-p=q$ together and find $q^2-p=q \iff p=q(q-1)$ . P is a prime so $q-1=1 \iff q=2$ so $p=2 \times 1=2$ .

From these cases we have found the answer $N=2+3+7+31+127=170$ .

First off, we set up the equation $n^2-pn=q^m$ for some prime $q$ , and some positive integer $m$ . This becomes $n^2-pn-q^m=0$ . Assume that this quadratic can be factored as $(n-a)(n+b)$ --Therefore, $b-a=p \text{ and } ab=q^m$ .

Let's plug in some numbers (ordered pairs $(b,a)$ ) to get and idea of our solutions. Try $(4,1)$ --It works. $(3,1)$ also works. As does $(4,2)$

Here's something important though: The only even prime is $2$ . Now, if we let $q \neq 2$ , we see that $q$ must be the product of two odd numbers, but the difference of two odd numbers is divisible by $2$ . Therefore the only ordered pair of two odd numbers is $(3,1)$ .

This makes the problem much easier, because $q=2$ . This automatically gives us the solutions $(8,1), (32,1), \text{ and } (128,1)$ .

So far I have assumed $a=1$ What if $a \neq 1$ ? Well if that's the case then:

• $a$ cannot be even because $q$ is a power of 2 (besides $(4,2)$ , so the difference will be divisible by $2$
• $a$ cannot be odd because the product of $a$ and $b$ would not be a prime power anymore

Therefore, our only valid pairs are $(4,1),(4,2),(3,1),(8,1),(32,1), \text{ and } (128,1)$ which implies our valid primes are $2,3,7,31,127 \implies \text{ Our sum is } \boxed{170}$

Motivation: Since the highest degree of this equation was $2$ , I started to think of quadratics and Vieta's immediately. Then I examined the parities of the equation to see if it would help. It worked, so I solved from there.

Look at the cases n^2 - np = n*(n - p) being either odd or even.

If it is odd then neither n nor (n - p) can be even. This means n must be odd, and thus p must be even in order for (n - p) to be odd. The only even prime is 2, so we are then looking for solutions to n (n - 2) = q^m with n odd. Now by the Fundamental Theorem of Arithmetic this will require that both n and (n - 2) are powers of an odd prime p, (as n (n - p) is odd). But since n and (n - 2) differ by only 2 we cannot have both being different powers of the same odd prime q, and so we will find no solutions in this case.

If n (n - p) is even then for this to equal a prime power the prime power must be a power of 2, as all other prime powers are odd. Thus we are looking for primes p such that there exists some n such that n (n - p) = 2^q for some positive integer q. By the Fundamental Theorem of Arithmetic this means that n and (n - p) must be powers of 2. We can rule out n = 1 and n = 2. For n = 2^2 = 4 we have that 4*(4 - 2) = 8 = 2^3, and thus p = 2 is a solution. Since we don't need to look at p = 2 we are looking for odd primes only now, and since n is a positive power of 2 this means that (n - p) will be odd and also a power of 2. This is only possible if n - p = 1. Thus we are looking for primes p that are of the form p = 2^q - 1. Going through the possible values of q gives us the solutions, in addition to 2, of 3, 7, 31 and 127.

The sum is then 2 + 3 + 7 + 31 + 127 = 170, and so 170 is the solution.

We know that $n^ {2} - pn = n(n-p)$ . Now, lets work with the two possible cases:

I. If $p$ is even ( $2$ ), then:

a) If $n$ is even, then $n(n-p) = even * even$ , which is a possibility.

b) If $n$ is odd, then $n(n-p) = odd * odd$ , which is a possibility.

II. If $p$ is odd, then:

a) If $n$ is even, then $n(n-p) = even * odd$ , and this is possible only for $n-p = 1$ .

b) If $n$ is odd, then $n(n-p) = odd * even$ , which is impossible.

Lets pay special attention to II-a. It is possible only if $n-p=1$ . That means that $n$ is even, and the only way an even number can be expressed into a prime power is if it can be expressed as $2^ {k}$ . We know that $p < 1000$ , so we'll check from $2^{1}$ to $2^{9}$ ( $2, 4, 8, 16, 32, 64, 128, 256, 512$ ). For all of them, we substract $1$ , and if it is prime, then it's a valid $p$ . With $2$ is the only case we can add $1$ (because $2$ is prime). We find the primes $2, 3, 7, 31, 127$ , whose sum is $\boxed {170}$ .

Note that

$n(n-p)=q^m$

If $n$ odd number, then $p$ are odd number so $n-p<n$ such that $n(n-p) \neq q^m$

So that, $n$ even number and power prime. So, $n=2^k$

Now, check

$p=n-1$ , $n=2^k$

$p=(2,3,7,31,127)$

So, the answer is:

$p=2+3+7+31+127=\fbox{170}$

If it is odd then neither n nor (n - p) can be even. This means n must be odd, and thus p must be even in order for (n - p) to be odd. The only even prime is 2, so we are then looking for solutions to n (n - 2) = q^m with n odd. Now by the Fundamental Theorem of Arithmetic this will require that both n and (n - 2) are powers of an odd prime p, (as n (n - p) is odd). But since n and (n - 2) differ by only 2 we cannot have both being different powers of the same odd prime q, and so we will find no solutions in this case.

If n (n - p) is even then for this to equal a prime power the prime power must be a power of 2, as all other prime powers are odd. Thus we are looking for primes p such that there exists some n such that n (n - p) = 2^q for some positive integer q. By the Fundamental Theorem of Arithmetic this means that n and (n - p) must be powers of 2. We can rule out n = 1 and n = 2. For n = 2^2 = 4 we have that 4*(4 - 2) = 8 = 2^3, and thus p = 2 is a solution. Since we don't need to look at p = 2 we are looking for odd primes only now, and since n is a positive power of 2 this means that (n - p) will be odd and also a power of 2. This is only possible if n - p = 1. Thus we are looking for primes p that are of the form p = 2^q - 1. Going through the possible values of q gives us the solutions, in addition to 2, of 3, 7, 31 and 127.

The sum is then 2 + 3 + 7 + 31 + 127 = 170, and so 170 is the solution.

Since $n(n-p)=q^m$ , we have $n=q^{m_1}, n-p=q^{m_2}$ , for $m_1+m_2=m$ . Thus $p=q^{m_2}(q^{m_1-m_2}-1)$ . $p$ being prime means that $m_2=0$ and $q^{m_1}-1$ is prime, or $m_2=1$ and $q^{m_1-m_2}-1=1$ . The latter case has only one solution $p=2$ . The former case requires $q=2$ and $p=2^{m_1}-1$ being prime. Enumerating $m_1$ from 2 to 10 yields $p=2,3,7,31,127$ .