I am looking into Integer Factorization and have found an interesting pattern which I cannot explain.

For a composite number $N$, where $N = PQ$.
All factors of $(P + Q)$ are found amongst the factors of $(Nx^2 + 1)$ for integer $x > 0$.

For example $5713 = 29\cdot197$
$(P + Q) = 226 = 2 \cdot 113$

The sequence $(5713 x^2 + 1)$ is:
$5714, 22853, 51418, 91409, 142826\cdots$

The unique prime factorization of this sequence is:
$2, 17, 19, 43, 47, 53, 67, 71, 73, 89, 103, 109, 113, 127, 139, 151, 163\cdots$

Note that not every prime is listed, $3, 5, 7, 11, 13\dots$ are missing.
However the prime factors of $(P + Q)$ are (in this case $2$ & $113$).

Is anyone able shed some light onto
1. Why some primes are missing from the unique prime factorization of the sequence?
2. Why the factors of $(P + Q)$ are contained in the factorization of this sequence?

Highly factorable numbers work too.
$3795 = 3 \cdot 5 \cdot 11 \cdot 23$

$(P + Q)$ can be any of $(124, 148, 188, 268, 356, 764, 1268)$ and the factors of all can be found amongst the unique prime factorization of $(3795 x^2 + 1)$.

The only example I found where this doesn't work is when N is a square (eg. $4, 9, 16$) or a multiple of a square (eg. $12, 75, 98$).

I apologize for any terminology issues, my maths knowledge is not great.
I was suggested math.stackexchange over stackoverflow.


Very nice observation! I've never seen this before, but here's a simple proof.

Suppose $p|P+Q$ where $p$ is a prime.

Then $Q = -P$ mod $p$, and $PQ = -P^2$ mod $p$.

For $p$ to factor an element of the sequence we require $p|(PQx^2 + 1)$ for some $x$. That is, $PQx^2 = -1$ mod $p$.

Combining these two relationships we obtain $$ P^2x^2 = 1 \quad mod \space p $$ which is satisifed whenever $x = \pm P^{-1}$ mod $p$

To understand why some primes are missing from the factors of the sequence, you need to learn about quadratic residues. These are covered in any introductory text on number theory. The simple answer is that for a prime $p$ to exist in the sequence, $-PQ$ must be a quadratic residue modulo $p$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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