numbers $n^2+1$ Prove that there are infinitely many natural numbers of the form $n^2+1$ such that they don't have any divisor of the form $k^2+1$ except $1$ and themselves. time allowed for this question was 45 minutes.
Problem
Source:
Tags: induction, number theory proposed, number theory
17.08.2010 20:20
Let $x_n=2^{2^n}+1,\quad n=1,2,\ldots$, and $y_n$ be the least positive divisor of $x_n$ except 1, that is representable in the form $k^2+1$. then $y_i$'s are mutually different, since $x_i$'s are mutually relatively primes. the sequence $y_1,y_2,\ldots$ satisfies the conditions of problem.
05.09.2011 19:14
dauhuong68 wrote: hi M.SH. Can you explain more ? $y_{5}$ =641 which not a $a^{2}$ +1 form try to read everything carefully. M.SH wrote: Let $x_n=2^{2^n}+1,\quad n=1,2,\ldots$, and $y_n$ be the least positive divisor of $x_n$ except 1, that is representable in the form $k^2+1$. then $y_i$'s are mutually different, since $x_i$'s are mutually relatively primes. the sequence $y_1,y_2,\ldots$ satisfies the conditions of problem.
05.09.2011 21:40
$y_i$ is not prime, it's just a positive divisor of $x_i$. read carefully.
09.11.2012 10:41
Let $X$ be the subset of the natural numbers of the form $n^2 +1$ that have no divisor of this form, except $1$ and itself. Let $Y$ be the subset of the natural numbers of the form $n^2 +1$ that have at least one divisor of this form, except $1$ and itself. If $X$ isn't infinite, it must have a largest member. We call it $x_k$ and we denote all members of $X$ as $x_1,x_2,\ldots,x_k$, with $x_1<x_2<\cdots < x_k$. By using induction, prove that each member of $Y$ has at least one divisor in $X$. Then consider $A=(x_1x_2\cdots x_k)^2 +1$. Because $A$ is larger than $x_k$ and in form $n^2+1$, $A$ must be in $Y$. But we know that all members of $Y$ must have at least on divisor in $X$, so $A$ must have one. But it is a contradiction. Mod: I have latexified it (and improved some syntax); does it not look better? Also, the solution suffers from a minor technicality - you must show that $X$ is not empty (which is trivial of course, since $2\in X$). soheil74:thanks,it seems beautiful !!!
08.11.2019 20:54
Here's a sketch of a quite different solution than the ones above. The main motivation comes from the solutions to a China TST 2015 problem, see here: https://artofproblemsolving.com/community/c6h1064571p4619843. Let $S$ be the set of those $n$ such that $n^2 + 1 \equiv 0 \pmod{k^2 + 1}$ for some $k$. The main question is: "How dense is the set $S$?"- Consider the equation $x^2 + 1 \equiv 0 \pmod{m}$. If $m$ is a prime power, this is seen to have at most two distinct solutions modulo $m$ - indeed, this statement holds for $m$ prime, and the general case follows by Hensel's lifting lemma. Therefore, if $\omega(m)$ denotes the number of distinct prime divisors of $m$, then the solution has at most $2^{\omega(m)}$ distinct solutions modulo $m$ by the Chinese remainder theorem. It is easily seen that $\omega(m) \le \log_5(m) + 2$, as all except two of $m$'s prime factors must be at least $5$. Now, the density of those $x$ for which the equation $x^2 + 1 \equiv 0 \pmod{m}$ holds is at most $$\frac{2^{\omega(m)}}{m} \le \frac{2^{\log_5(m) + 2}}{m} < \frac{1}{m^{0.501}}$$for large $m$. Therefore, the density of those $x$ for which the equation $x^2 + 1 \equiv 0 \pmod{m}$ holds for some $m$ of the form $k^2 + 1$ is at most the sum $$\sum_{k = 1}^{\infty} \frac{1}{(k^2 + 1)^{0.501}}$$(times some constant). The main point is that this sum is finite. However, we would like the sum to be less than $1$. To achieve this, instead of picking a random $x$ and hoping that none of $k^2 + 1$ divide $x^2 + 1$, pick a random $x$ divisible by the first $N$ primes for some large $N$. Now, for such $x$ the numbers $x^2 + 1$ are trivially not divisible by $k^2 + 1$ for $k < \sqrt{N}$. For this optimized choice of $x$ we see that the density of interest is at most $$\sum_{k = \sqrt{N}}^{\infty} \frac{1}{(k^2 + 1)^{0.501}}.$$This is less than $1$ for $N$ large enough, which proves that the desired $x$ actually have a positive density. Remark: The above proof is actually just a sketch of a solution. The problem is that we say that we pick "a random positive integer $x$". This isn't really well defined. What we could do is pick some large constant $C$, and investigate the number of desired $x$ at most $C$. The above idea works, but we have to consider ceiling functions here and there. However, the number of error from these ceiling functions is at most the number of primes less than $C$, which is approximately $\frac{C}{\log(C)}$ by the prime number theorem, and thus less than $\epsilon C$ for any $\epsilon > 0$, so this does not affect the densities.