Too Primed

Suppose $N=pq$ where $p$ and $q$ are distinct primes . Now positive divisors of $N$ would be $1 , p , q, pq$ . So Sum of squares of positive divisors will be $1+p^2+q^2+(pq)^2$

Since $N | 1+p^2+q^2+(pq)^2 \implies pq|1+p^2+q^2+(pq)^2$ since $pq$ divides $(pq)^2$ so , $pq|1+p^2+q^2$

LEMMA : If $ab|1+a^2+b^2$ then $\frac{a^2+b^2+1}{ab}=3$ , and also if $(x,y)$ is a solution , then next solution would be given by $(y,\frac{y^2+1}{x})$

PROOF . Consider the ordered pair $(x,y)$ . We say that is the ordered pair with the minimum value of $x+y.$ such that $\frac{x^2+y^2+1}{xy}=k.$ , where $k.$ is some integer other than $3.$ . We can also assume without the loss of generality that $x>y.$ , because if $x=y .$ we quickly see that our only solution is $(1,1).$ , but that yields $3.$ . So $x>y.$ when $y>1.$ Now simplifying $\frac{x^2+y^2+1}{xy}=k.$ we get: $x^2-kyx+y^2+1=0.$

We see that we have a quadratic in $x.$ . We can let one root of the quadratic be x and the other root be $z.$ . Then by Vietas we have: $xz=y^2+1 \implies .z=\frac{y^2+1}{x}.$

So we see that if $(x,y).$ is a solution, then $(y,z).$ is a solution, and we know that $(y,z).$ is equivalent to $(y,\frac{y^2+1}{x})$ Now if we can prove that $x+z<x+y,.$ we will reach our desired contradiction as we assumed minimality for $x+y..$ $x+z<x+y\\ z<y\\ y^2+1<xy\\ y+1/y<x .$

Which is true by our initial assumption that $y<x.$ when $y>1.$ Hence, there is no solution such that $\frac{x^2+y^2+1}{xy}=k.$ , where $k.$ is some integer other than $3.$ . Furthermore, a solution when $k=3.$ is $(1,1) .$ , and we have already shown that if we know one solution, we can generate an infinite number of solutions by letting the solution after $(x,y) .$ be $(y,\frac{y^2+1}{x}).$

So the proof of lemma ends

so now we have $(1,1)$ as solution , now next will be $(2,5)$ then $(5,13)\\ (13,34)\\ (34,89)\\ (233,610)\\ (610,1597)\\ (1597,4181)$

Note that $1597 \cdot 4181$ exceed $10^6$ and lower prime pairs are $(89,233)$ so , $p+q =89+233=\boxed{322}$

Let $N=pq$ , where $p,q$ are distinct primes with $p<q$ .

$pq$ divides $1^2+p^2+q^2+p^2q^2$ , $pq$ divides $(p^2+1)(q^2+1)$ . Since $p$ is a prime, $p$ divides $p^2+1$ or $p$ divides $q^2+1$ . Since $p^2\equiv0\pmod{p}$ , $p^2+1\equiv1\pmod{p}$ , $p^2+1$ is not divisible by $p$ , $p$ divides $q^2+1$ . Similarly, $q$ divides $p^2+1$ . Let $p^2+1=kq$ for some natural numbers $k$ . $q=\frac{p^2+1}{k}$ , $(\frac{p^2+1}{k})^2+1\equiv0\pmod{p}$ . As $gcd(p,k)=1$ , $\frac{1}{k^2}+1\equiv0\pmod{p}$ , $k^2+1\equiv0\pmod{p}$ . By Vieta jumping, $(p,q)$ is a solution iff $(k,p)$ is a solution. Note that every solution is a deriavative of $(1,a)$ for some $a$ . [Temporarily ignore the fact that $p$ and $q$ are primes.]

When $p=1$ , $p^2+1=2$ , since $q>p=1$ , $q=2$ , $a=2$ . Start at $(1,2)$ and turn $(p,q)$ into $(q,\frac{q^2+1}{p})$ continuously, we get pairs of solution $(1,2),(2,5),(5,13),(13,34),(34,89),(89,233),(233,610),...$ . Observe that $89\times233=20737<10^6$ and $233\times610=142130>10^6$ . Finally, check that $p=89, q=233$ are both primes and satisfy all the conditions given in the problem. Therefore, the sum of the positive prime divisors of $N$ is $p+q=89+233=322$ .

We need to see the nature of N first. N= n1n2 with n1 and n2 being primes. n1n2 | the sum of it's divisors squares = 1+ n1^2+ n2^2 + (n1n2)^2 So of course, n1n2 | n1^2 + n2^2 +1 From here, we get n1 | n2^2 +1 and n2 | n1^2 + 1 Assume n1>n2. We can say that n1 = (n2^2 +1) /k because n2 | n1^2+1 , n2 |((n2^2 +1) /k) ^2 +1 -> n2 | n2^4 +2 n2^2 + 1 + k2 --> n2 | k^2 +1 We already know that k | n2^2 +1 from it's definition. Because k=(n2^2+1)/n1 and n1 >=n2+1, we get k<=n. If we rename k as n3, we will get this statement: For every n1 and n2 such that n1<n2, n1|n2^2+1 and n2|n1^2+1, there will be n3 such that n3<=n2<n1, n3|n2^2+1, and n2|n3^2+1 If we repeat this step with n2 and n3, and again with n3 and n4, and again with n4 and n5, we will get n1>n2>=n3>=n4>=....>=nm>=.... Note that other than n1 and n2, others aren't necessarily prime. Note also that doing so doesn't alter the n1, and since n1 is finite, there must be time when this sequence stops decreasing, which is when nm=n(m+1) But it can only be reached when n(m+1)|nm^2+1 = n(m+1)^2+1 --> n(m+1)|1 From here, we know that n(m)=n(m+1)=1. So we know that somewhere in the sequence, 1 is involved. We can now use it to trace it back to n1. nm=1 and n(m-1) divides nm^2+1 = 2. From here, we know that the only non-1 n(m-1) possible is 2. n(m-2) can be generated from n(m-1) and nm with the formula we had earlier n(m-2) = (n(m-1)^2+1)/nm (we previously used k instead of nm, but this formula is used throughout the sequence.) We get n(m-2) = 5 Now, we can backtrace this sequence to n1, with the only possible sequence being 1 2 5 13 34 89 233 610 1597 ..... Note that if n2>1597 , n1n2>10^6. Therefore, the only possible primes in the sequence fitting as n1 and n2 are 233 and 89

$pq \mid 1 + p^2 + q^2 + (pq)^2 \\ \Leftrightarrow pq \mid 1 + p^2 + q^2 \\ \Leftrightarrow kpq = 1 + p^2 + q^2 \\ \Leftrightarrow q^2 - kpq + p^2 + 1 = 0$
$p$ and $q$ can't be equal because $p \not \mid 2p^2 + 1$ . WLOG, $q > p$ .

The second solution for $q$ to the above quadratic equation is $x_2 = kp - q = \frac{p^2 + 1}{q} \leq \frac{p^2 + 1}{p + 1} = p - 1 + \frac{2}{p+1}$ .
$x_2$ is always an integer because $x_2 = kp - q$ . $x_2$ is always positive because $\frac{p^2 + 1}{q}$ . $x_2$ is less than $p$ when $p > 1$ . So, if $(p, q)$ is a solution with $q > p >1$ , then $(\frac{p^2 + 1}{q}, p)$ is also a solution.

Reducing a solution like this, we will eventually get to the solution $(1, 1)$ [Do you know why? - Calvin], and because this operation is reversible, we can start from $(1, 1)$ , and generate all possible solutions. We get the following list: $2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025, 196418, 514229$ Every 2 consecutive numbers from this list is a solution to the equation, but since we need 2 primes, the biggest consecutive pair is $(89, 233)$ .

Note: We could have used the well known fact that $ab | a^2 + b^2 + 1 \Rightarrow 3ab = a^2 + b^2 + 1$ , and solve the quadratic equation, but that would have been harder to do.

[LaTeX edits - Calvin]

This is not a complete explanation because I haven't mastered Vieta Jumping yet but I will try my best.

Since $N=pq, p \ne q$ , given sum of squares of divisors of $N$ is divisible by $N$ , then $(p^2 + q^2 + 1) \bmod{(pq)} = 0$

Refer to this link ,

We get $\frac {p^2 + q^2 + 1}{pq} = 3$

Without the loss of generality, we have $p < q$

Trial and error shows that $(p,q) = (1,2), (2,5), (5,13),(13,34), (34,89), \ldots$ , I don't know how to elaborate on this.

And $1,2,5,13,34,89, \ldots$ follows the recurrence relation $a_0 = 1, a_1 = 2, a_n = 3 a_{n-1} - a_{n-2}, n \geq 2$

Continue on with the list gives $1,2,5,13,34,89,233,610,1597, \ldots$

For $p$ and $q$ prime with $pq < 10^6$ , we select two consecutive numbers in the list (which are also primes) such that they are largest.

We get $p=89,q=233 \Rightarrow p+q=322$

The sum of the positive prime divisors of $N$ is $p^2q^2 + p^2 + q^2 + 1$ , thus $\frac {p^2q^2 + p^2 + q^2 + 1}{pq}$ is an integer. While it may seem tempting to factor the numerator and split it into two cases, this is not the easiest way (in my eyes). Instead, since we know $\frac {p^2q^2}{pq}$ will be an integer, we will then have to find values of $(p, q)$ such that $p^2 + q^2 + 1$ is divisible by $pq$ . If you didn't know it already, a useful theorem to know is that if $pq$ divides $p^2 + q^2 + 1$ , the quotient is $3$ . So we get $p^2 - 3pq + q^2 + 1 = 0$ , which is a quadratic with respect to $p$ . Using the quadratic formula on the previous equation, we get $p = \frac {3q +/- \sqrt {5q^2 - 4}}{2}$ .

First, we start with the base case, where $q = 2$ . We get $(p, q) = (5, 2)$ as an answer. Trying higher primes for $q$ , we get $(5, 13), (13, 34), (34, 89)$ etc. This follows the recursion $p_0 = 2, p_1 = 5, p_n = 3p_{n-1} - p_{n-2}$ for $p \geq 2$ .

ALTERNATIVE METHOD

Odd squares can be written in the form $8T + 1$ , where $T = \frac {(a)(a+1)}{2}$ is a triangle number. When $q > 2, 5q^2 - 4$ must also be an odd square. So $5q^2 = 4a^2 + 4a + 5$ . Completing the square on the RHS we get $5q^2 = (2a + 1)^2 + 4 = (2a + 1)^2 - 5q^2 = -4$ . Let $x = 2a + 1$ . Then there is one obvious solution to this, namely $(1, 1)$ . Solving the Diophantine equation, if $(1, 1)$ is a solution then all other solutions $x, q$ are given by $\frac {(x + q \sqrt{5})}{2} = ((\frac {3 + \sqrt{5}}{2})^r (\frac {1 + \sqrt{5}}{2}$

We find solutions such that $a$ and $q$ are prime. These are consecutive pairs $2, 5, 13, 34, 89, 223 ...$ as found before.

In this recursion, the two largest consecutive terms such that they are both prime and their product is less than $10^6$ are $q = 89$ and $p = 233 \rightarrow p + q = 322$

I am sure there is a more elegant solution to this that does not involve trial and error, but I at the moment this is the best I can do.