Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$ Without using modular equivalence, show that: $\gcd(4n^2+1,24)=1$
Let $d=\gcd(4n^2+1,24)$ then we have:
$$d|24n^2+6,24n^2\ \Rightarrow\ d|6\ \Rightarrow\ d|6n^2,4n^2+1\ \Rightarrow\ d|12n^2,12n^2+3\ \Rightarrow\ d|3\ \Rightarrow\ d=1\ or\ 3$$
Using modular equivalence it's very easy to show that $d$ can't be 3,but how can I show it WITHOUT using  modular equivalence???

Theorem. $4n^2 + 1$ is not a multiple of $3$.
Proof. Since $n^2 = (-n)^2$, we need only prove this for
$n \in \mathbb W = \{0, 1, 2, \dots\}$.
Let $T = \{k\in \mathbb W : 3 | 4k^2 + 1\}$.
We need to show that $T$ is the empty set.
If we assume that $T$ is not the empty set, then it must contain a smallest member, say $s$. (This is called "The Well-Ordering Principle".) Then $s$ is the smallest member of $\mathbb W$ such that $3 \mid 4s^2 + 1$.
Note that
\begin{align}
    4\cdot 0^2 + 1 &= 1 \\
    4\cdot 1^2 + 1 &= 5 \\
    4\cdot 2^2 + 1 &= 17 \\
\end{align}
So $s-3 \in \mathbb W$ and $s-3 \not \in T$. But if $3 \mid 4s^2 + 1$ and 
$3 \not \mid 4(s-3)^2 + 1$, then
\begin{align}
    3 &\not \mid (4s^2 + 1) - (4(s-3)^2 + 1) \\
    3 &\not \mid 4(s^2 - (s-3)^2)\\
    3 &\not \mid 4(6s - 9)\\
\end{align}
But clearly $3 \mid 4(6s - 9)$. So by contradiction, $T$ is the empty set.
