Yes. Note that all we have to do is show that for all positive integers $k$, there exists an integer $x$ such that $13^k | x^2+1$. Prove this using induction. The base case is easy (take $x=5$). If for some $k=l$ we have $13^l | x^2+1$, let $y=x+13^l \cdot z$. Then $13^{l+1} | y^2 + 1 \iff 13^{l+1} | x^2+1+2xz13^l$. If we let $x^2+1 = t \cdot 13^l$ then it becomes $13 | t + 2xz$. It is obvious that we can find such an integer $z$, as $13$ does not divide $2x$. (this is basically Hensel Lemma )

Hensel's Lemma and even Legendre symbols imply the result.

Actually, since there are primitive roots $\mod 13^k$ for all $k$, the fact that $(-1)^{\frac{\phi(13^k)}{2}} = (-1)^{6 \cdot 13^{k-1}} \equiv 1 \pmod{13^k}$ implies that the equation $x^2 \equiv -1 \pmod{13^k}$ has solutions, and as stated before that solves the problem.

Can someone explain why the primitive roots implies solutions?

DragonFire1024 wrote: Can someone explain why the primitive roots implies solutions? Let g be the primitive root, then its order is $\phi(13^k)$. By the definition of order, $g^{\phi(13^k)/2} \not \equiv 1 \mod 13^k$ but $(g^{\phi(13^k)/2})^2 \equiv 1 \mod 13^k$. Since $x^2 \equiv 1 \mod 13^k$ has exactly two solutions, the only possibility is that $g^{\phi(13^k)/2} \equiv -1 \mod 13^k$.

Just Hensel's Lemma .Woohoo

It suffices to show that for all $k\in\mathbb{N}$, there exists a positive integer $x$ so that $13^k|x^2+1$. Let $f(x)=x^2+1$. $x=5$ obviously works for $k=1$. So by Hensel's Lemma, there exists a such $x$ for $k=2$. Since $13\nmid f'(x)$ if $13|f(x)$, we can repeatedly use Hensel's Lemma, to show by induction that there exists a such $x$ for all $k\in\mathbb{N}$.

Cliam: for all $k \in N$ there exists a positive integer $b_k$ so that $13^k|(b_k)^2+1$ it is easier to prove than induction. $$a_k = c_k \cdot 13^k + b_k$$$c_k$ is chosen to be greater than $a_{k-1}$.

The answer is positive. Let $a_k=b_k^2$, then we must have that $b_k^2 \equiv -1 \pmod{13^k}$. implying that $ord_{13^k} b_k = 4$. Claim: $2$ is a primitive root of $13^k$, for all natural $k$. Proof: Notice that $2$ is already a primitive root $\pmod{13}$, then we know that if $13^k \mid 2^t-1$, we have that $12\mid t$. Let $12t = ord_{13^k} 2 \leq \varphi(13^k) = 13^{k-1}12$, then by LTE, we have that: $$v_{13}(2^{12t}-1)=v_{13}(2^{12}-1)+v_{13}(t) \geq k$$giving us that $v_{13}(t) \geq k-1 $. Thus we have that $t=13^{z}t'$,where $z \geq k-1$, plugging this into $12t \leq 13^{k-1}.12$, we get that $t=13^{k-1}$, thus $ord_{13^k}2 = \varphi(13^k)$; implying that for any $k$, $2$ is a primitive root $\pmod{13^k}$. $\blacksquare$ Using the claim, we can set $b_k=2^{13^{k-1}3}$, thus giving us that $a_k=2^{13^{k-1}6}$.

Does this work? Consider the following rephrased problem. Quote: Does there exist a strictly increasing infinite sequence of positive integers $a_1, a_2, a_3, ...$ such that for all $k\in \mathbb{Z}^+$ we have that $13^k | a_k^2+1$? We will use induction. Base case: We can take $a_1=5$. Induction step: Suppose that we have, for some $k$ and $n$, $a_k^2+1=13^kn$. It suffices to show that there is an $m$ such that $a_{k+1}^2+1=13m\cdot13^k$. Letting $a_{k+1}=a_k+13^kc$ for some $c$, we obtain: $$13m-2a_kc=n+13^k,$$and by a slightly stronger Bezout's Lemma there are $c$ and $m$ such that this is true.

(Essentially Hensel Lemma) Consider $f(x)=x^2+1$. Let $b_1=5$. Note that: $13 | f(b_1) = b_1^2+1$ and $13 \nmid f'(b_1)$. Due to Hensel's lemma, there exists a sequence $b_k$ such that: $13^k|b_k^2+1$. Taking $a_k = b_k^2$, we are done.

By Legendre, $\left(\dfrac{a}{p^k}\right)=1$ $\iff$ $\left(\dfrac{a}{p}\right)=1$, that is, $\left(\dfrac{-1}{13^k}\right)=1$ $\iff$ $\left(\dfrac{-1}{13}\right)=1$. Like $13\equiv1\pmod{4}$, this is valid. Finally, $\forall k\in \mathbb{Z}^+$ $\ni x/$ $13^k|x^2+1$, for $x\in \mathbb{Z}$