Do there exist numbers of the form $n^2+1$ with arbitrarily many prime factors?

102 Views Asked by At

This is actually two questions:
1.Do there exist numbers of the form $n^2+1$ with arbitrarily many unique prime factors?
2.Do there exist numbers of the form $n^2+1$ with arbitrarily many prime factors?
I think an approach using gaussian primes might help, $$n^2+1=(n+i)(n-i)$$ let $n=c^2$ $$(c^2 + i)(c^2-i)...$$ but from here I haven't managed to make anything productive out of this approach.
Note: the primes in the question are normal natural number primes.

2

There are 2 best solutions below

0
On BEST ANSWER

I will elaborate what Ravi said for you.

$n_i^2\equiv -1\pmod{p_i}$ has a solution if $-1$ is a quadratic residue. A known formula is $$\bigg(\frac{-1}{p}\bigg)=(-1)^\frac{p-1}{2}$$ thus, if and only if $p\equiv 1\pmod{4}$ $-1$ is a quadratic residue.

(search up quadratic residues and laws for more information).

Now simply consider $n$ according to the Chinese Remainder Theorem.

3
On

Yes and yes. In fact, given any finite set of primes $p_i \equiv 1 \pmod 4$, there exists an integer $n$ such that $n^2 + 1$ is divisible by all of the $p_i$. Proof: each of the congruences $n_i^2 \equiv -1 \pmod{p_i}$ individually has two solutions modulo $p_i$; choose one of the two for each $i$, and use the Chinese Remainder Theorem to find an $n$ congruent to each $n_i$ modulo $p_i$.