Proof by induction, utilizing inductive assumption Show that for every natural number $n$ there exist integers $x,y$ such that
$$4x^2 + 9y^2\equiv 1\pmod{n} $$
The base case is trivial, since 1 divides anything. Assume the claim holds for some $k\in\mathbb{N}$, must show that the claim holds for $k+1$. We must find some $x', y'$ such that $4x'^2 + 9y'^2\equiv 1\pmod{k+1}$. My idea was to utilize the property:
$$\forall t\neq 0 (a\equiv b\pmod{n}\Longleftrightarrow ta\equiv tb\pmod{tn}) $$
Since  for $k$ the claim holds we have
$$4x^2+9y^2\equiv 1\pmod{k}\Longleftrightarrow (k+1)(4x^2+9y^2)\equiv k+1\pmod{k(k+1)} $$
but I don't know how to proceed (nor if this even leads anywhere), how to better apply the inductive assumption.
To elaborate:
I can do the following:
$$(4x^2 + 9y^2)k + (4x^2 + 9y^2-1) \equiv k\pmod{k(k+1)}\Longrightarrow 4x^2 + 9y^2 + z\equiv 1\pmod{k+1} $$
the inductive assumption provides that $4x^2+9y^2-1$ is divisible by $k$, but the result is not in a convincing form.
Alternative ideas for constructing proof in question are also welcome, of course. 
 A: (This is not a complete answer; merely some initial observations.)
You'll probably struggle to induct on $n$ like that. After all, knowing that $n \vert m$ (some integer $m$) tells you almost nothing about what $n+1$ divides.
Notice that $4x^2 + 9y^2 = ||2x+3y i||^2$ so it is necessary and sufficient to be able to find $x, y$ such that $$||2x+3yi||^2 \equiv 1 \pmod{n}$$
Consider $2x+3iy$ and $2\alpha + 3i\beta$.
If we multiply those together, we get $$4x\alpha -9y \beta + 6 (\alpha y+\beta x)i$$
This is of the form $2r + 3is$ if and only if $y$ or $\beta$ is even; and in that case, $s$ is also even.
Therefore if we can find $2x+3iy, 2\alpha + 3 i \beta$ such that $4x^2+9y^2 \equiv a \pmod{n}$ and $4\alpha^2+9\beta^2 \equiv b \pmod{n}$, with either $y$ or $\beta$ even, then we can find $4r^2+9s^2 \equiv ab \pmod{n}$ with $s$ even.
This is a kind of closure property which might be helpful, although it is no use in the case that $n$ is even, because then the left-hand side would always be even and the right-hand side always odd, so the "closed set" is in fact empty.
It solves the question in the case that $n$ is odd, though.
Indeed, if $n$ is odd, then for some $c \in \mathbb{N}^{>0}$ we have $4^c \equiv 1 \pmod{n}$.
Letting $x=1, y=0$ yields $4x^2+9y^2 = 4$, and we can just use the closure result above $c$ times.
Although after all this work, this is equivalent simply to putting $$x = 2^{c-1}, y=0$$
Similarly, if there is $d$ such that $9^d \equiv 1 \pmod{n}$, then we can set $$x=0, y=3^{d-1}$$
That holds if and only if $n \not \equiv 0 \pmod{3}$.
Therefore the only remaining case is when $n$ is divisible by $6$.
Letting $x=y=1$, we get $13$, so if there is $c$ such that $13^c \equiv 1 \pmod{n}$ then we are likewise done.
But this happens iff $n \not \equiv 0 \pmod{13}$.
Therefore the only remaining case is when $n$ is divisible by $6 \times 13 = 78$.
