# 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.

• An idea is that $z$ is expressible in a way that combines with the rest of the $4x^2 + 9y^2$ into a desired form, but so far haven't been able to come up with anything. Commented Mar 22, 2016 at 11:22
• 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. Commented Mar 22, 2016 at 11:25
• I was afraid of something like that :< Commented Mar 22, 2016 at 11:26
• Do you insist on using induction, or are you allowed to use some other metrod? Commented Mar 22, 2016 at 11:27
• Hint: If $6\nmid n$, then $2$ or $3$ is invertible mod $n$, and the result is direct. Commented Mar 22, 2016 at 11:52

(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$.