Let $d=a_1^2-a_0^2,\ b_i=a_i^2,\ c_i\in\{0, 1, \dots, k\}$ such that $a_{c_i}=i\\ b_i-b_0=b_i-b_{i-1}+b_{i-1}-b_{i-2}+\dots+b_1-b_0\equiv id\mod n\Rightarrow b_i\equiv b_0+id\mod n\\ b_0+c_0d\equiv b_{c_0}\equiv 0\mod n,\ b_0+c_1d\equiv b_{c_1}\equiv 1\mod n\\ \Rightarrow d(c_1-c_0)\equiv 1\mod n\Rightarrow\gcd(d, n)=1\\ \Rightarrow b_i\equiv b_j\iff id\equiv jd\iff i\equiv j\mod n\iff i=j$ If $n$ is not a prime, then there exists $2<l\leq m<\frac n2, l\equiv m\equiv 1\mod 2$ such that $n=lm$ If $l=m$, then $b_{c_0}\equiv b_{c_l}\mod n$ but $c_0\neq c_l$, contradiction If $l\neq m$, then let $i=\frac{m+l}2, j=\frac{m-l}2$ $i^2\equiv\frac{m^2+l^2}4+\frac{ml}2\equiv\frac{m^2+l^2}4-\frac{ml}2\equiv j^2\mod n$ $\Rightarrow b_{c_i}\equiv b_{c_j}\mod n$ but $c_i\neq c_j$, contradiction Therefore, $n$ is a prime. If $n\geq 11$ $(k+1)b_0+\frac{k(k+1)}2d\equiv b_0+b_1+\dots+b_k\equiv 0^2+1^2+\dots+k^2\equiv \frac{k(k+1)(2k+1)}6\equiv 0\mod n$ $\Rightarrow b_0+\frac{kd}2\equiv 0\mod n\Rightarrow 4b_0\equiv 4b_0+(2k+1)d\equiv d\mod n$ $\Rightarrow b_i\equiv (4i+1)b_0\mod n\Rightarrow b_k\equiv (4k+1)b_0\equiv -b_0\mod n$ $\Rightarrow\left(\frac{-1}n\right)=1\Rightarrow n\equiv 1\mod 4\Rightarrow b_{\frac k2}\equiv (2k+1)b_0\equiv 0\mod n$ $\Rightarrow\forall i<\frac k2,\ b_i\equiv (4i+1)b_0\mod n;\ \forall i>\frac k2,\ b_i\equiv 4(i-\frac k2)b_0\mod n$ $\because\left(\frac{b_0}n\right)=1$ $\therefore\forall 0\leq i\leq n-1,\ \left(\frac in\right)=1\iff i\equiv 0, 1\mod 4$ $\left(\frac 8n\right)=\left(\frac 2n\right)\left(\frac 4n\right)=-1\neq 1$, contradiction Therefore, $n\leq 7$ It is easy to know that $n=7$ is not a solution. Let $(a_0, a_1, a_2)=(2, 0, 1)$ for $n=5$; $(a_0, a_1)=(0, 1)$ for $n=3$. Therefore, $k=1, 2$.

My solution might be quite different from others Ans. $n=3, 5$ For $n=3, 5$, it is easy to find the example. Now we prove that it is impossible if $n \neq 3, 5$. Let $d$ be the common different of $a_0^2, a_1^2, \cdots a_k^2$. First we show that $n$ is not a composite number. If that does happen, let $p$ be a prime divisor of $n$. It is will-known that arithmetic sequence is periodic under the modulo $p$, and since there are exactly $\frac{p+1}{2}$ kinds of number in this sequence, hence the minimum period must be $\frac {p+1}{2}$. However, that means $a_0 = a_{\frac {p+1}{2}}$ (since $\frac {p+1}{2} > k$), $(\frac {p+1}{2}) d \equiv 0 (mod \enspace p)$, hence $d\equiv 0 (mod p)$, contradict with the fact that the minimum period is $\frac {p+1}{2}$. Now let $n=p$ be a prime number. We count the quantity $2\sum_{i=0}^{k-1} (\frac {a_i^2+d}{p})$ in two ways, where $(\frac{\bullet}{p})$ is Legendre symbol. $$2\sum_{i=0}^{k-1} (\frac {a_i^2+d}{p}) = 2\sum_{i=1}^{k} (\frac {a_i^2}{p}) = \begin{cases} 2k \qquad a_0=0 \\ 2k-2 \qquad a_0 \neq 0 \end {cases} \equiv -1, -3 \quad (mod p)$$on the other hands $$ \begin{aligned} 2\sum_{i=0}^{k-1} (\frac {a_i^2+d}{p}) &= 2\sum_{i=0}^{k} (\frac {a_i^2+d}{p}) - 2(\frac{a_k^2+d}{p}) = \sum_{i=0}^{p-1} (\frac {i^2+d}{p}) +(\frac{d}{p}) - 2(\frac {a_k^2+d}{p}) \\ &\equiv \sum_{i=0}^{p-1} (i^2+d)^{\frac {p-1}{2}}+(\frac{d}{p}) - 2(\frac {a_k^2+d}{p}) \\ &\equiv \sum_{i=0}^{p-1} \sum_{j=0}^{\frac{p-1}{2}} {{\frac{p-1}{2}}\choose {j}} i^{2j} d^{\frac {p-1}{2}-j} +(\frac{d}{p}) - 2(\frac {a_k^2+d}{p}) \\ & \equiv \sum_{j=0}^{\frac{p-1}{2}} {{\frac{p-1}{2}}\choose {j}} d^{\frac {p-1}{2}-j} \sum_{i=0}^{p-1} i^{2j} +(\frac{d}{p}) - 2(\frac {a_k^2+d}{p}) \\ & \equiv \sum_{i=0}^{p-1} i^{p-1} +(\frac{d}{p}) - 2(\frac {a_k^2+d}{p}) \\ & \equiv (-1) + (\frac{d}{p}) - 2(\frac {a_k^2+d}{p}) \\ & \equiv -4, -2, 0, 2 \quad(mod \enspace p)\end{aligned}$$Hence $p=3, 5$, as desired. $\blacksquare$

The answer is $n = 3$ and $n = 5$, which is easy to verify. We will prove that any $n > 5$ fails. Assume there exists $n > 5$ which satisfies the condition. Let $d = a_1^2 - a_0^2$ and let $a_i = 0$. For any $m = 0, 1, ..., k$, we have $a_m^2 \equiv a_i^2 + (m - i)d \equiv (m - i)d \pmod{n}$, therefore $(a_0^2, a_1^2, ..., a_k^2) \equiv (-id, (-i+1)d, ..., (k - i)d) \pmod{n}$. Also, notice that $1 = 1^2 - 0^2 \equiv ld \pmod{n}$ for some $l \in \mathbb{Z}$, so $gcd(d, n) = 1$. First, we show that $n$ is prime. Assume otherwise, then let $p$ be a prime divisor of $n$. It is well-known that there are exactly $\frac{p+1}{2}$ quadratic residues modulo $p$, so by the Pigeonhole Principle, there are two different numbers $a_i^2, a_j^2$ among the numbers $a_0^2, a_1^2, ..., a_{\frac{p+1}{2}}^2$ (note that $\frac{p + 1}{2} < p < n/2 < k+1$) such that $a_i^2 \equiv a_j^2 \pmod{p}$. But $a_i^2 - a_j^2 \equiv (i - j)d \equiv 0 \pmod{p}$, so $p \mid i - j$, but $0 < i - j < \frac{p+1}{2} < p$, contradiction. If $-1$ is not a quadratic residue, then one of the numbers $-d$ and $d$ is a quadratic nonresidue, thus $(a_0^2, a_1^2, ..., a_k^2)$ can only be $(0, d, 2d, ..., kd)$ or $(-kd, -(k-1)d, ..., 0) \pmod{n}$. Either way, $0, 1, ..., k$ are either all quadratic residues or all nonresidues (since $1$ is a quadratic residue then the former is true), which means $\left(\frac{-1}{n}\right) = \left(\frac{2k}{n}\right) = \left(\frac{2}{n}\right) \left(\frac{k}{n}\right) = 1$, contradiction. So, $-1$ is a quadratic residue and $k$ is even (since $n \equiv 1 \pmod{4}$). Now, since $\max(i, k-i) \geq \frac{(k - i) + i}{2} = \frac{k}{2}$, then $a_0^2, a_1^2, ..., a_k^2$ must either contain $d, 2d, ..., \frac{kd}{2}$ or $-d, -2d, ..., -\frac{kd}{2}$. Similarly, $1, 2, ..., \frac{k}{2}$ must all be quadratic residues, and thus $n - 1, n - 2, ..., n - \frac{k}{2}$ are also quadratic residues. Also note that $0$ and $k = 2 \cdot \frac{k}{2}$ are quadratic residues (since $2 \leq \frac{k}{2}$), so there are at least $k + 2$ different quadratic residues, contradiction to the well-known fact that there are $\frac{n + 1}{2} = k + 1$. Hence, we are done.

A solution without using Legendre symbol is possible: After proving that $n$ is a prime, apply the argument here.

Proof without legendre symbol. $n=3, 5$ makes the equation correct. Suppose $n \geq 7$. Claim. $n$ is a prime number. pf> Let $p$ be a prime divisor of $n$(which has to be odd). Suppose $p<n$. Because $n$ is odd, $p\leq {n \over 3}<k$. Consider $\{a_0 ^2 , a_1 ^2, \cdots ,a_{p+1 \over 2} ^2 \}$. By pigeon hole principle, there exists $0\leq i < j \leq {p-1 \over 2}$ such that $a_i ^2 \equiv a_j ^2 \pmod p$ ($\because$ the number of quadratic residue of $\pmod p$ is ${p+1 \over 2}$, including $0$). Then, $\delta =a_1 ^2 - a_0 ^2 \rightarrow 0 \equiv a_j ^2 - a_i ^2 \equiv (j-i)\delta \pmod p$. $0<j-i \leq {p+1 \over 2}<p$, which means $p \mid \delta$. Then, $a_0 ^2 \equiv a_1 ^2 \equiv \cdots$, which is a contradiction by $0^2 \equiv 1^2 \pmod p$. Let $n=p$, $a_0 ^2 = a$, $a_1 ^2 -a_0 ^2 = d$. Then, the quadratic residues of $\pmod p$ are equal to $\{a, a+d, \cdots, a+{p-3 \over 2}d\}$. It is clear that sum of quadratic residues and the sum of squares of quadratic residues are equal to 0 $\pmod p$ if $p>5$. (Use the primitive root and the sum of geometric series) So, $\{a, a+d, \cdots, a+{p-3 \over 2}d\}$ should be so. (sum) $\equiv {p-1 \over 2}a + {(p-1)(p-3) \over 8}d \equiv 0 \pmod p \rightarrow a+{p-3 \over 2}d \equiv 0 \pmod p$ (sum of squares) $\equiv {p-1 \over 2}a^2 + {(p-1)(p-3) \over 4}ad + {(p-3)(p-1)(p-2) \over 24}d^2 \equiv 0 \pmod p \rightarrow a^2+{p-3 \over 2}ad+{(p-3)(p-2) \over 12}d^2 \equiv 0$ By combining two results, we get $d \equiv 0 \pmod p$, which can't be true because $1 \not\equiv 0 \pmod p$ .

Thw following is the solution w/o using any properties of quadratic residues that a contestant sent to me: After proving n is a prime number. I provide another solution without Legendre symbol. $(a_1+a_0)(a_1-a_0) \equiv (a_2+a_1)(a_2-a_1) \equiv \dots \equiv (a_k+a_{k-1})(a_k-a_{k-1})$ (mod $n)$ We claim that the numbers of the set $S=\{a_i\pm a_{i-1}\mid 1\leq i \leq k \}$ are "almost" distinct under mod n. The only exception is $a_{i-1}=0,a_i+a_{i-1}\equiv a_i-a_{i-1}$ (mod $n)$(If $a_k=0$,there is no exception.) <pf> Assume there exist $i\neq j$ such that $a_i+a_{i-1} \equiv a_j\pm a_{j-1}$(mod $n)$,then $a_i-a_{i-1} \equiv a_j \mp a_{j-1}$(mod $n)$. Add two,we have $a_i\equiv a_j($mod $n)$,contradiction. Similarly,there doesn't exist $i\neq j$ such that $a_i-a_{i-1} \equiv a_j\pm a_{j-1}$(mod $n)$. Apparently,when $a_{i-1}\neq 0,a_i+a_{i-1}\not\equiv a_i-a_{i-1}$ (mod $n)$. Noticed that there can't exist $i\neq j$ such that $a_i+a_{i-1}\equiv -(a_j\pm a_{j-1})$ (mod $n)$. Like the argument in the claim, it implies $a_i\equiv -a_j $(mod $n)$ but $a_i,a_j \in \{0,1,...,k\}$,contradiction. Assume $a_{i-1}=0$,the claim shows that $S$ equals $\{-k,-(k-1),\dots,-1,1,\dots,k\}$ removes $-a_i$. For all $s \neq i$,we have $-(a_s+a_{s-1})$ have to appear in the $S$ ,however,it cannot be $a_j\pm a_{j-1} \forall j\neq i$. Therefore,$-(a_s+a_{s-1})\equiv a_s-a_{s-1} $(mod $n)$,which implies $a_s=0.$ When $k\geq 3$,we always can find $s\neq t$ such that $a_s=a_t=0$,contradiction. Hence,$k \leq 2$.

I don't see why we need to bother with $n$ being prime or not. Let $p$ be the index such that $a_p=0$. Then the squares $0^2,1^2,2^2,\dots,k^2$ modulo $n$ are (up to order) just \[-pd,-(p-1)d,\dots,-d,0,d,2d,\dots,qd\]where $q=k-p$ and $d$ is the common difference. Now $1=1^2$ is on that list, so $d$ must be coprime to $n$. If $q \ge 1$, then $d$ is a quadratic residue and hence also $-p,-(p-1),\dots,-1,0,1,2,\dots,q$ (and there can't be more). If $q=0$, $-d$ is a quadratic residue and hence also $0,1,2,\dots,k$ (and again there can't be more). So if $p=0$ or $q=0$, we must have $k=1$ since otherwise $2$ and hence $2k$ is a quadratic residue not on that list. Similarly, if $p,q>0$, then $-1$ is a quadratic residue and hence the list is symmetric so that $p=q=\frac{k}{2}$. But then $k=2$ since otherwise again $2$ and hence $k=2 \cdot \frac{k}{2}$ is a quadratic residue not on that list. Hence only $k=1$ and $k=2$ are possible.